Linked list is a simple yet powerful data structure. Much like an array, a linked list is simply a collection of items. The difference is that linked list items are not stored contiguously in memory. Each item maintains a pointer to the next item in the list so the items can be located anywhere. This is depicted graphically below.
By convention, the first item is the list is known as the head and the last item is known as the tail. There are essentially two types of linked lists: singly linked lists (depicted above) and doubly linked lists (depicted below). As the names imply, singly linked lists maintain a single pointer to the next item. Doubly linked lists maintain a pointer to the next item as well as a pointer to the previous item.
Doubly Linked List
- Insert\Delete: $O(1)$
- Search: $O(n)$
- Enumerate: $O(n)$
Click here for build and run instructions
- Insert\Delete: Constant time operation
- Maintains Order: Maintains the order in which items are inserted
- Memory: Each item in the list must maintain an additional pointer. The total size of a linked list is the sum of the items plus the size of the pointers times the number of items.
- Cache Optimized: It is possible to create a linked list with poor spatial locality which can have profound performance implications. See the Memory Cache Hierarchy section for more details.
- Search: There is no inherit support for search operations other than examining each item individually. Additionally, unlike Arrays, linked lists cannot take advantage of Binary Search, regardless of the sort order.