You might have gotten your head around arrays, but there are many data structures you can use in programming. In some ways, a linked list is similar to an array, but there are some key differences. Discover what a linked list is, explore the different kinds of linked lists, and find out how to use one with this article.

## What is a Linked List?

Like an array, a linear list is a data structure that’s linear. But the difference lies in the way they store and access data. Whereas an array stores elements in a contiguous block of memory, a linked list contains elements as nodes, with each node pointing to the next element in the list. As such, they’re not stored contiguously, and elements are not accessed using an index. Instead, pointers are assigned to each node, which dictate the node that is next in the sequence. As with a dynamic array, linked lists can be modified by adding or removing nodes as necessary.

## What Are the Benefits?

Now we’ve covered exactly what a linked list is, you might be wondering why you’d want to use one. Here are a few advantages:

- Unless you’re using a dynamic array, the array size tends to be fixed, whereas linked lists can be increased or decreased as appropriate.
- Inserting or deleting elements requires constant time, as opposed to arrays where other elements will need to be shifted.
- Linked lists tend to be easier on your memory constraints, particularly with large volumes of data. This is because memory is only used for the nodes required, but the contiguous nature of arrays means that you may be supporting some data that you don’t need for your operations.
- It’s easier to maintain persistence of data with linked lists, as data can be serialized easier than in arrays. This makes it simpler to transmit data amongst multiple programs, or after the programs have terminated.
- Where you’ve got sparse data, that is with empty elements, an array would still store these. A linked list, however, only stores values that aren’t empty.

## What are the Different Types of Linked Lists?

There are quite a few different types of linked lists you can make use of, each with its own qualities. We’ll give a brief run-through here, and how to implement them in Python.

### Simple Linked List

As you could expect, this is the simplest type of linked list, where you can only traverse the list in one direction. Each pointer points to the next node, with the final node pointing to nothing, or NULL. This is also known as a singly linked list. The code to implement a simple linked list in Python is as follows:

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def add(self, data): new_node = Node(data) if self.head is None: self.head = new_Node else: current_node = self.head while current_node.next is not None: current_node = current_node.next current_node.next = new_node def remove(self, data): if self.head is None: return if self.head.data == data: self.head = self.head.next return current_node = self.head while current_node.next is not None: if current_node.next.data == data: current_node.next = current_node.next.next return def display(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next my_list = LinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(2) my_list.display

### Explanation

This is a fairly extensive block of code, but not too hard to understand.

First, we’re defining the “Node” and “LinkedList” classes. The “Node” class represents a node in the list, each with a pointer (indicated by “self.next”). The list is represented by “LinkedList”, and we’ve implemented a header node, which allows for easier insertion or deletion of elements.

The “add” function indicates that a new node is to be added to the end of the list. If the list is empty, then the header node is set to the new node created. If it’s not empty, then the list is traversed until the last node and points this toward the new node.

The “remove” function works by removing the first node in the list. If this is the header node, then the next node becomes the header node. If the head node does not have the given data, then the list is traversed to find it. Once it finds the node with the given data, its “next” attribute is set to the node after this, which removes this node from the list.

“Display” traverses the list and prints the data found at each node.

The data within the list is defined with the “LinkedList” class at the end, with nodes of data values 1, 2, and 3. Node 2 has been removed to show the removal process, and both lists are printed for the output. Check out the screenshot for how this works.

### Doubly Linked List

This is similar to a simple list, except traversal can happen in both directions, forwards and backwards. To implement this, we can use the following code:

class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None self.tail = None def add(self,data): new_node = Node(data) if self.head is None: self.head = new_node self.tail = new_node else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node def remove(self, data): current_node = self.head while current_node is not None: if current_node.data == data: if current_node.prev is not None: current_node.prev.next = current_node.next else: self.head = current_node.next if current_node.next is not None: current_node.next.prev = current_node.prev else: self.tail = current_node.prev return current_node = current_node.next def display(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next my_list = DoublyLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(3) my_list.display()

### Explanation

A lot of the code in this example is similar, but there are some differences.

We define the “Node” class in a similar way, but there are references to the previous node as well as the next node this time. Similarly, the ”DoublyLinkedList” class represents the list but has instances functioning as both the head and tail of the list.

Like before, the “add” function adds a new node to the end of the list. But if the list is empty, then both the head and tail are set to this new node. When the list isn’t empty, the “prev” attribute of the new node is set to the current tail, and the “next” attribute of the current tail to the new node, and the tail is changed to the new node.

The “remove” function removes the first node in the list with the given data. The “prev” and “next” attributes of adjacent nodes are updated to avoid the current node, effectively removing it from the list. If the node in question is the head or tail, then this attribute is also updated to reflect this.

Lastly, the “display” and “my_list” functions are largely the same, but this time we’ve removed the node with data value 3. The screenshots illustrate the code execution.

### Circular Linked Lists

Another type of linked list is a circular list. As the name suggests, this is a list where there is no “end”. The end node is connected back to the start node. An example is seen with the following code:

class Node: def __init__(self, data): self.data = data self.next = None class CircularLinkedList: def __init__(self): self.head = None def add(self, data): new_node = Node(data) if self.head is None: self.head = new_node new_node.next = self.head else: current_node = self.head while current_node.next is not self.head: current_node = current_node.next current_node.next = new_node new_node.next = self.head def remove(self,data): if self.head is None: return if self.head.data == data: current_node = self.head while current_node.next is not self.head: current_node = current_node.next current_node.next = self.head.next self.head = self.head.next else: current_node = self.head while current_node.next is not self.head: if current_node.next.data == data: current_node.next = current_node.next.next return current_node = current_node.next def display(self): if self.head is None: return current_node = self.head while True: print(current_node.data) current_node = current_node.next if current_node is self.head: break my_list = CircularLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display()

### Explanation

There are a few key differences here. The “new_node.next = self.head” means that the new node that’s added is the last node in the list, and points back to the head of the list, which is the first node.

The “while current_node.next is not self.head” line is used to traverse the linked list and add elements. Because there is no true end, like with the singly linked list, we have to check if the current node is the head node, rather than if it is simply non-zero. This is to avoid changing the head node.

The “new_node.next = self.head” code ensures that the node added to the list is connected with the head node.

The “remove” function works similarly in that, if the given data is contained within the first node, this is removed and the next node becomes the new head node. If the head node doesn’t contain the given data, the list is traversed as before, until the data is found. The “next” attribute is then assigned to the node after this one, which skips this node. Overall, the function is the same, but the implementation is a little more elaborate due to the circular nature of the list.

The “display” function is also very much the same, except that we must check we’re starting at the head node, and break the traversal once we reach this point again.

### Double Circular Linked Lists

Since we’ve looked at singly, doubly, and circular linked lists, it only makes sense to finish with a double circular linked list. Quite the mouthful, but not quite elusive. Expectedly, this refers to a circular linked list that we can traverse in both the forward and backward directions. The implementation of this type of list can be illustrated as such:

class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class DoubleCircularLinkedList: def__init__(self): self.head = None def add(self, data): new_node = Node(data) if self.head is None: new_node.next = new_node new_node.prev = new_node self.head = new_node else: last_node = self.head.prev last_node.next = new_node new_node.prev = last_node new_node.next = self.head self.head.prev = new_node def remove(self,data): if self.head is None: return current_node = self.head while current_node.data != data: current_node = current_node.next if current_node == self.head: return if current_node == self.head: self.head = current_node.next current_node.prev.next = current_node.next current_node.next.prev = current_node.prev def display(self): if self.head is None: return current_node = self.head while True: print(current_node.data) current_node = current_node.next if current_node == self.head: break my_list = DoubleCircularLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display()

### Explanation

The key difference between a double circular linked list and a standard circular linked list is that, as before with the non-circular linked list, the double list points each node to the previous as well as the next node. This is achieved by updating the “prev” and “next” attributes of the last node and the new node when adding a node. When removing a node, these attributes of the removed node and adjacent nodes need to be updated. If you’re removing the head node, then the pointers of the last node need to be updated to reflect this.

## Wrapping Up

Many types of linked lists can be used as an alternative to arrays, such as when you need to insert and delete elements regularly or have memory constraints. Although arrays perform faster when it comes to certain operations, linked lists aren’t without their unique benefits, so it’s useful to understand how they work.