LinkedLists
A linked list is a list of elements not contiguous in memory but ordered by each element having a link to the next element. It is a collection of nodes.
Simple LinkedList
This simple linked list represents a sequence of 3 elements (2, 4, 6).
We can create this list like above, but let’s dig into how we can create a Linked list and node class.
This is a node representing an element of type T (here, we made it generic but could use any type, Int, String, …) and a link “next” to the next node (or not in case end of the list).
This is a basic implementation of a linked list but not really efficient, except to add in the first position of the list; other operations like adding at the end, removing any nodes, …, will have a complexity of O(n) as we will need to go through all nodes in the worst case scenario.
To improve this, we could use a more efficient list by adding a tail and a previous link; let this see in the following part.
Double LinkedList
This double-linked list represents a sequence of 3 elements (2, 4, 6).
We can create this list like above, but let’s dig into how we can create a Double Linked list class and its node.
This is a node representing an element of type T (here, we made it generic but could use any type, Int, String, …) and a link “next” to the next node (or not in case end of the list) and also a link to the previous node “previous” (or not/nil in case of the head of the list).
Then a linked list is simply a pointer (or reference) to the first node “head” (it could be nil in the case of an empty list). To optimize adding at the end of the list, we can have a link to the last node, “tail”.
To add one element at the end of the list, when we don’t have the tail property, we would need to iterate over the elements until the last one. Which would have a complexity of O(n) but having the tail makes it constant O(1).
There are two options for appending to the list: if we have a tail, bind the tail and the new node together and make the tail point to the new node; otherwise, make the head and the tail point to the new node. Eventually, return the last node.
Removing any node from the list in case it is a double-linked list is done in a constant time O(1) because we have access to the previous and next one. Otherwise, we would have to iterate over the list, leading the worst-case scenario to a linear complexity O(n).
To remove any element from the list, bind the previous and the next of the node you want to remove. If the previous is nil, it means you are removing the head; you need to make the head point to the new head (next). If next is nil, it means you are at the end of the list; you need to make the tail point to the previous.
Because we will need it later articles, let’s add two functions (removeFirst and removeLast):
Because we have direct access to the head, tail, and previous, it allows us to have a constant time complexity O(1). We still need a few pointer gymnastics to clean the memory.
Iterate: To iterate over a list (using Iterator), you need to access the head of the list and then continue calling next until there is no more next. It has a linear time complexity O(n).
Time Complexity:
- append: O(1) as we use the tail element,
- remove: O(1) as we use the previous element,
- removeFirst: O(1) as we use the head element,
- removeLast: O(1) as we use the tail element,
- IsEmpty: O(1) as we use the head element.
As you can see, a minor update can improve performance.
This is how you can use a LinkedList:
