Linked lists are data structures composed of nodes, where each node generally has a value and a pointer to the next node. In many cases, the linked list will also include a pointer to the first node in the chain, called the head of the list, and the last node in the chain, called the tail.
The linked list is the basis of many more complex data structures, including trees, stacks, queues, and heaps.
Linked lists are null terminated. They can be circular, where one node points to a previous node in the chain.
Complexity of Common Operations
Singly Linked List
With a tail and head pointer, inserting or deleting from the front of the list is constant time.
Inserting at the end of the list is also constant time.
However, removing from the end of the list is , because you have to find the ‘previous’ node to link it back to your newly homeless tail pointer.
Doubly Linked List
If you have a tail and head, the most common insert/delete at start/end operations are all .
Double and Single
Both share the same time complexity when it comes to finding, copying, or otherwise any operation involving a specific node in the list, .
Access/Entry
Usually, this can be called the front pointer or the head. The last one is usually called the tail. There also exists front + back pointers.
When adding a node to the end of a list, if the list had a tail pointer, you’ll need to move the tail to the end of the list.
When deleting the end of the list, we can’t just delete the tail as that would leave a dangling pointer, so that would be since we have to traverse the list.
When inserting a value into a doubly linked list, create a temporary node to the new value, point temp→prev = curr, temp→ next = curr→next, then curr→next→prev = temp and curr→next = temp.
Alternatively, add a variable here representing curr→next called like curr_n or whatever and pointe that.
To delete a value from a doubly linked list:
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
delete curr;
curr = null;Circular Singly Linked List
Complexity to remove the first element. However because it is circular moving the head of the list is and that would change the first/last element of the list in one operation.
Circular Double Linked List
Same thing goes for double linked lists though it uses more operations and lines of code.
Sentinel Nodes
Sentinel nodes are lists that contain dummy nodes at the ends of the lists which do not contain any data. They eliminate the special cases for list modifications, like insert remove first and last nodes, all the cases are implemented the same way.