The linked list data structure is one of the simplest and most fundamental data structures and has a wide range of applications. Some more advanced data structures may use linked lists internally depending upon the implementation strategy. Having full knowledge and understanding of this fundamental data structure is important for any serious programmer or computer science student. In this article, we'll discuss some of the places linked lists are used, the types of linked lists and their benefits & drawbacks, how to code linked lists, and provide example linked list implementations in multiple programming languages.
Linked Lists
A linked list is a data structure which holds each value of the list in a node, and each node points to the next node in the list. If a node is the last element in the list, its next reference will be null. The first node in the list can be called the head node. A few common use cases for linked lists includes:
- Queues: a linked list can be used to implement an efficient queue: a type of object which elements are removed in the same order their inserted.
- Stacks: stacks are a type of object which remove the most recent items added before removing older ones. Linked lists can be an efficient option for implementing a stack.
- Math with large numbers: linked lists are used by some libraries which allow for mathematical operations on very large numbers
- State of History: a linked list, used as a stack, can represent a type of history state, such as a website's breadcrumb, state of navigation in an application, etc.
- Visual Rendering: a game engine might use a linked list to order the elements which need to be rendered to the screen.
The examples above constitute only a few of the many use cases for linked lists.
Types of Linked Lists
There are a few variations of linked lists. All of these variations share the core functionalities described above, but some variations are better suited to different use cases:
- Singly Linked List: the standard type of linked list as described above.
- Singly Linked List with a Tail Reference: this is an implementation detail more so than it is a variation. It is a linked list implementation which has one additional reference to the tail: the last item in the list, to facilitate list operations.
- Doubliy Linked List: a linked list where the nodes have references next and previous. This can reduce the number of traversals in the list but requires double the number of node references.
- Circular Linked List: a linked list where the last node points back to the first node in its next property.
Linked Lists Variations vs Arrays
In the table below, we'll compare different types of operations to see how well arrays vs different types of linked lists perform when executing those operations. If you're not familiar with Big O notation: n represents the number of elements, O(n) means the operation takes n steps, and O(1) means the operation takes a small number of steps, regardless of how large n is.
Insert Element at Beginning | Append Element to End | Access the 1st Element | Access the nth Element | Access the Last Element | Space Requirement | |
---|---|---|---|---|---|---|
Array | O(n) | O(1) | O(1) | O(1) | O(1) | O(n) => n reference to values |
Singly Linked List | O(1) | O(n) | O(1) | O(n) | O(n) | O(n) => n nodes in memory, n-1 references to other nodes, and n reference to values |
Singly Linked List with Tail | O(1) | O(1) | O(1) | O(n) | O(1) | O(n) => n nodes in memory, n references to other nodes, and n reference to values |
Doubly Linked List with Tail | O(1) | O(1) | O(1) | O(n) | O(1) | O(n) => n nodes in memory, 2n references to other nodes, and n reference to values |
Circular Linked List | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) => n nodes in memory, n references to other nodes, and n reference to values |
Coding a Linked List
To implement a linked list, we will need to keep track of the nodes of the list in some manner. In our implementation, we will create a node class and a linked list class. The node class will keep track of its own value and next-node reference, and the linked list class will handle operations such as unshift and removeLast. In the code below, we've implemented the singly linked list with support for these operations. To facilitate some of the operations, we will keep a reference to the last node of the list as tail. This extra reference enables us to add elements to the end of the list in a single operation, without the need to iterate over the entire list from head to get to the last element. Lastly, if you are not familiar with generics, the "T" means that we can use any type of data we want, such as an int, string, or custom class.
The full list of operations supported by this linked list are:
- append: put a new element at the end of the list
- unshift: put a new element at the beginning of the list and shift the rest over by one position
- removeFirst: remove the first element from the array and return its value
- removeLast: remove the last element from the array and return its value
Coding a Doubly Linked List
In this implementation, we will need to modify the node class to hold a reference to the next node and previous node. This will require twice as many references, but will also enable us to perform the access last element and append element to end operations in O(1) instead of O(n), because we now have a reference to the previous node, and thus no longer need to iterate through the entire list to get to that point.
Coding a Circular Linked List
The implementation for a circular linked list is very similar to singly linked list implementation above. The only differences between these two implementations are:
- The last node in the linked list will point back to the first node with its next property.
- Instead of keeping track of the head and tail, we can keep track of the tail only, as the head reference will be stored in the next property of the tail.
- When appending a node, we will need to update next references are updated properly to preserve the circular property.
Since this implementation is almost exactly the same as that of a singly linked list, we have omitted it for brevity.