© Profit_Image / Shutterstock.com
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.
©History-Computer.com
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.
©History-Computer.com
©History-Computer.com
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.
©History-Computer.com
©History-Computer.com
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.
©History-Computer.com
©History-Computer.com
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.
