A Linked list is a data structure that can store a collection of items. All the items in a linked list are stored in the form of a chain made up of multiple nodes. Each node stores an item and also points out (links) to the next node in the chain.
Linked lists store items in a sequence similar to arrays. But unlike arrays, the items are not stored in continuous block of memory and also memory is not reserved in advance. Later on in this article, we will discuss about the benefits of using linked lists instead of using contiguous data structures like arrays.
Anatomy of a Linked List
A linked list is made up of a chain of multiple nodes. Each node can store an item/element along with the address of the next node in the sequence. For example, the illustration below is a linked list containing 3 items “A”, “B” & “C”.
You can observe that there is a node corresponding to each item stored in the linked list. Also if you look at the node holding the item “A”, it also points to the next node in the sequence which holds the item “B”. Again the node holding item “B” points to the next node in the sequence which holds the item “C”. Item “C” is the end of list, so it does not point to any other node.
The first node among the sequence of all the nodes in the linked list is termed as the “head node” and the last node in the sequence which does not point to any other node is termed as the “tail node”.
Types of Linked Lists
Singly Linked Lists
Singly linked lists are made up of nodes that are connected only in one direction. In other words, any node in a singly connected linked list can have the details of the next node but not the previous node. These are the simplest and least space consuming type of linked lists. Below is a sample linked list with singly connected nodes.
Doubly Linked Lists
Doubly linked lists are made up of nodes that are connected in two directions. In other words, any node in a doubly connected linked list has both the details of next node and the previous node. This type of linked list consume extra space for storing the information about prevous nodes, but by doing so they improve performance of many algorithms. Below is a sample linked list with doubly connected nodes.
Circular Linked Lists
If the last/tail node in a single or doubly connected linked list is connected to the head, it becomes a circular linked list. Circular linked list can be created from singly connected or doubly connected linked list.
Implementation of Linked List
Implementation of Singly Connected Linked List
# Implementation of Linked List Data Structure in Python
# Class to store an item and a next node
class Node:
def __init__(self, item):
self.item = item
self.next = None
# Now let us create a linked list and test it
# We need to create the nodes first
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
# Let us now chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4
# node1 is the head node in the linked list
# let's print all the items using head node
cnode = node1
while cnode != None:
print(cnode.item, end=" ")
cnode = cnode.next
Implementation of Doubly Connected Linked List
# Implementation of Doubly Linked List Data Structure in Python
# Class to store an item and a next node
class Node:
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
# Now let us create a linked list and test it
# Let us create the nodes first
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
# Let us now chain the nodes bi-directionally
# to form a doubly linked list
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
# node1 is the head node in the linked list
# node4 is the tail node in the linked list
# let's print all the items using head node
print("Printing nodes from head to tail (proper order)")
cnode = node1
while cnode != None:
print(cnode.item, end=" ")
cnode = cnode.next
print("\nPrinting nodes from tail to head (reverse order)")
cnode = node4
while cnode != None:
print(cnode.item, end=" ")
cnode = cnode.prev
Advantages of Using Linked Lists Over Arrays
Arrays reserve certain memory before hand and consume that memory even if the array is empty. Whereas for linked lists, total memory consumed is the sum of memory consumed by all the nodes in the list. So in cases where the usage of reserved memory in arrays is less, linked lists can be a better alternative since memory is reserved on demand. But in some cases, because of the extra space required by a linked list node to store the next node info, it might end up taking more space than an array.
When the reserved memory for array is completely filled up, a larger memory has to be reserved and all the items in the array needs to be copied to the newly reserved memory, which might take time. In these scenarios, a linked list is really efficient since adding any element to the end of list is as simple as creating a new node and attaching it to the tail of linked list.
Also, since all the nodes in a linked list are chained together and each chain can be easily modified, insertions or deletions of nodes anywhere in the linked list is easy and efficient. Where as in array, all the elements towards the right of where we add/remove item has to be shifted by one position, which consumes more time.
TODO: Disadvantages
Operations that can be performed on a Linked List
Some of the basic operations that can be performed on a linked list are
- Traversing all nodes in a linked list from head to tail
- Appending a new node to the end of the list
- Prepending a new node to the beginning of the list
- Inserting a new node after a specific node in the list
- Deleting head or tail node
- Deleting a node present in between the list
We will go through each operation in the upcoming tutorials.