Swift -Doubly Linked List
Review of Doubly Linked List(DLL) data structure and implementation on Swift
What is a DLL, for what and where to use him? Advantages and Disadvantages compared to dynamic Array. Implementation AddFirst, AddLast, Insert, Delete, and get Value by index methods, also you’ll find out how to get Next, Previous and Current value. How to loop through our data structure items by implementing IteratorProtocol. All of this you will find in this article, have fun and enjoy!
What is a DLL?
Doubly linked list, a data structure in computer programming. In simple words, this is a chain where each node holds the value and the references on the previous and next item. The first node of the DLL called Head and the last Tail. For example, to get value from the middle of the list we must take a head node and go through the list by calling “next” to get the next node and repeat this operation until we don’t get the middle node.
You might think “Why I need to use DLL instead of dynamic Array?” the answer is related to work with memory and complexity of the algorithm when you want to manipulate Array or DLL. This brings us to the topic of Advantages and Disadvantages DLL and Array. If you are not familiar with how Array stored in memory you can read about this here “Arrays, behind the scene”.
Advantages and Disadvantages
The main advantage of DLL is the performance efficiency or complexity of the algorithm for Insert and Delete an element to the beginning. If add the item to the beginning of the DLL the complexity algorithm will be O(1), but for Array, it will be O(n). Why? Because for DLL you only need to change the Head by creating a new Node and set Next as Head next set a new Node as a Previous for the Head. Don’t worry if it seems complicated we’ll get back to it soon. For a dynamic Array, you have to shift all the elements and not considering the case where you’d have to resize an array if it’s full.
The disadvantage of DLL that when we will want to get value by index we need to iterate through the list until we get to the needed index. The complexity of this operation will be O(n) when Array will do this by O(1).
You can compare the complexity of algorithms by the table and we can move from theory to practice.
Doubly Linked List
The class will be generic to not be independent of the value type. The class will contain Head, Tail, Selected, and Length properties. The length will be increased or reduced every time when a Node will be added or deleted.
Next need to create the Node class that also will be generic and contain Value, Next node, and Previous node.
Add First
The first added Node will be Head and Tail of the list also, immediately we can set a Head as Selected. The next added Node will take a place of the Head and the previous Head will take a place of the Tail.
Add Last
AddLast operation looks similar to the AddFirst only difference that we work with a Tail and every new added Node will be a Tail.
Insert to index
For the first need to find a Node by index. Now we can take a found Node and change the Next node of the Previous node and Previous node to the new Node. If it seems complicated the diagram can help to see the full picture:
Delete by index
For the delete operation, also the first need to find the Node that we want to delete. Next need to check if length equals 1 if yes need to clear all by set Head, Tail, and Selected as nil. Also need to check if the node to delete is Head if yes, the Next node to delete will be the new Head. Otherwise, you need to change the values of Next and Previous in the nearest nodes.
Value at index
To get Value to need to start moving forward from Head until we will not get to the asked index.
Get Current, Next and Previous value
We can add the possibility to get Next and Previous value by use helped property Selected every time when will be called next or previous computed property the Selected property will be changed and will work like a save point.
Sequence
We can improve our DLL class by implementing Sequence protocol to get possibility loop through values by use Map or for a loop.
The Sequence protocol contains only one method “makeIterator” which returns IteratorProtocol and will be called when you want to loop through values. The IteratorProtocol contains “next” method which returns the associated type Element and will be called inside a loop until the value will be nil that will stop the loop.
Now we can create one more computed property to get an array of values by using compactMap.
Enumerated
Because we implemented a protocol Sequence our list can be enumerated. What does this mean? Let’s see the documentation:
enumerated()
Returns a sequence of pairs (n, x), where n represents a consecutive integer starting at zero and x represents an element of the sequence.
If we look back to the Insert to index chapter we can see that we use the helper property counter to finding the needed node. Now we can improve our code by using the enumerated method and remove the helper property:
Conclusion
Now you know one more data structure to work with a list and now you can choose what will be better and faster to resolve your task Array or DLL. The DLL will be the perfect choice for a music player with a next and previous button, browser cache which allows you to hit the back and forward pages or card game represents a deck of cards. I hope you enjoyed reading. Source code. Good luck!
Have you checked open jobs at Just Eat Takeaway.com lately?
