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.