Linked List
Introduction
Similarly to an array, a linked list is a linear sequence of elements. The order of elements in an array is given by their position in a contiguous memory block. Contrastingly, the order of elements in a linked list is maintained by each element holding a reference to the next (see figure 1).
A linked list itself is a simple structure. It holds only a reference to the head; the first element in the linked list.


Common use cases include the implementation of stacks and queues, or to handle collisions in a hash table.
Advantages & Disadvantages
Advantages
 Inserting or deleting from the beginning of a linked list is very efficient and has a time complexing of O(1) (or constant time). The same implies if we already have a reference to the element we want to insert after.
 It is a dynamic data structure and can be resized at runtime, unlike an array which is given a fixed sized.
 Due to its dynamic nature, no memory is wasted by reserving memory.
Disadvantages
 More memory is required for each element compared to an array, as each requires a pointer to the next to be stored alongside its data.
 Accessing a node at a given index has a time complexity of O(n) (or linear time), as we have to traverse the list to find it. Random access is not possible because data is not stored in contiguous memory.
 Traversing a list in reverse is not possible unless a doublylinked list is used, which requires further memory.
Operations
Prepending
Prepending is a simple operation involving adding a new element to the head of the linked list. To prepend a new element, we give its pointer a reference to the element at the head. The head’s pointer is then updated to reference the the new element (see figure 2).
Code example:


Prepending is inexpensive and has a time complexing of O(1). This compares to O(n) time complexity for the same operation on an array, where n is the array length. This is because an array has to shift the existing elements to make room for the new one.
Inserting After a Node
Given a reference to an existing element in a linked list, inserting a new value involves a similar procedure to prepending (see figure 3). The pointer of the new element is given a reference to the node positioned after the target node. The target node’s pointer is then given a reference to the new node.
Code example:


As we already have a reference to the the node we want to insert after, this operation also has a time complexity of O(1). Again, a similar operation on an array would have O(n) time complexity, where n is the number of elements after the insert position.
Appending
Appending to a linked list is conceptually simple; it involves pointing the last element to the new one (see figure 4). To do this we must traverse the linked list until we find an element with a null pointer (the last element), before pointing it to the new element.
Code example:


Appending is less efficient than prepending or inserting after particular node, because we have to traverse the entire linked list. This means the time complexity is O(n), where n is the length of the linked list.
Deleting the Head
Deleting the head simply involves changing the node referenced at the head to the next one in the sequence (see figure 5).
Code example:


Like prepending, removing an element from the head is very efficient and has a time complexity of O(1). The same operation on an array involves shifting the elements positioned after the one being removed. This gives a time complexity of O(n), where n is the number of elements to be shifted.
Deleting a Value
Deleting a value involves traversing the linked list. On each iteration, we check if the value of the next element is the one we want to delete. When the value is encountered, the pointer of the current element is updated to reference the element after the next (see figure 6).
Code example:


The time complexity of deleting a value is O(n), where n is the number of elements we have to traverse.
Accessing by Index
To access an element by its index, we traverse through the elements using their pointers, tracking the number of elements visited until we reach the desired index (see figure 7).
In the below the example, the number of elements visited is tracked by decrementing the requested index.


The time complexity for this operation is O(n), where n is the number of elements to traverse. This is this is less efficient than the same operation on an array, which has a time complexity of O(1). Because an array is stored in contiguous memory, any index can be accessed quickly by using an offset from the location of the first element.
Finding a Value
To find a value, the linked list is traversed via the pointers until we reach the node that contains the desired value and return it (see figure 8).
Code example:


Like with an array, this operation has O(n) time complexity. With both structures, elements have to be traversed until the desired value is found.
Summary
A linked list has an advantage over similar data structures for operations such as inserting and deleting. This can be useful for implementing such things as stacks and queues. Its disadvantages include that it is inefficient to access elements by index and that it requires more memory.
Some key operations were discussed and examples were given for how to implement them. The full code example can be found on Github.