Linked Lists

Linked lists are a collection of nodes, each of which have a value and a pointer to the next node in the list. These are typically refered to as value and next. The first node in the linked list is refered to as the head, and the last node is the tail who's next pointer points to null. Linked lists differ from arrays in that since they use pointers to link values, they do not need to occupy contiguous memory.

Complexity

• Accessing head - O(1)
• Accessing tail - O(n)
• Accessing middle - O(n)
• Inserting/removing head - O(1)
• Inserting/removing tail - O(n)
• Inserting/removing middle - O(n)
• Searching - O(n)

Doubly Linked Lists

These are very similar to a singularly linked list, only that each node also has a prev pointer pointing to the previous node. For the head, this is set to null. The complexity is mostly the same as the singularly linked list as well, only operations on the tail are O(1) time.