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.
Complexity of Common Operations
Singly Linked list
With a tail and head pointer, inserting or deleting from the front of the list is O(1) constant time. Inserting at the end of the list is also O(1) constant time.
However, removing from the end of the list is O(n), 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 O(1).
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, O(n).