10 minutes read

Linked Lists Data Structures with Algorithm and Examples

Summary:Linked lists are one of the most popular data structure which is more efficient than Array. This article explains the linked list data structure in detail with examples.

Linked lists are non-primitive linear data structures with several benefits. It stores the nodes at different memory locations and each node has reference to the next node in the memory.

They are the best alternatives to the array when the length of data items is unknown.

The linked lists are one of the most important data structures which have a lot of applications. Some other performance-optimized data structures such as tree and graphs use a linked list.

What is a Linked List Data Structure?

Linked list data structures are the collection of nodes which are connected to each other.

Singly linked list also generally known as a linked list.

The nodes contain two parts, data and reference to the next node in the memory.

The data part holds the actual data which we use and the reference pointer is to go at the next node.

Types of Linked Lists

Here are different types of linked lists which are suitable for the specific situations. We need to know them in-depth to understand them.

Singly Linked List

Singly linked lists are those in which nodes contain a reference to only the next node.

a singly Linked list node
Open ImageIt means the traversal of the singly linked list is only one way. We can only traverse forward and not backward because there is no reference to the previous node.

Whenever we simply say linked list it means we refer to the singly linked list because it is used most of the time.

Here is a pseudo-code for the node of the singly linked list.

class Node{
    Object data;
    Node nextNode;
}

The data can be of any type, it means we can also store our own custom object in the linked list. The nextNode is of type Node which refers to the next node.

Here is the python program implementation of a singly linked list.

Note: This program is only to understand the concept, we do not link nodes manually in real-life uses.

class Node:
    #Constructor
    def __init__(self, data):
        self.nextNode = None
        self.data = data

node1 = Node(5)
node2 = Node(9)
node3 = Node(13)
node4 = Node(17)

#Connect them manually (just for understanding)
node1.nextNode = node2
node2.nextNode = node3
node3.nextNode = node4

#Verify they are connected
pointer = node1
#Traverse until last node (last node has nextNode=None)
while(1):
    print(pointer.data, sep="", end="")
    # If pointer is on last node break while loop and exit
    if(pointer.nextNode is None):
        break
    #for Visual Formatting only
    print("", end=" => ")
    #Move pointer to next node
    pointer = pointer.nextNode

Output

5 => 9 => 13 => 17

Doubly Linked List

As we see that singly linked list has a disadvantage that it can only traverse in the forward direction.

Doubly linked lists contain nodes which contain three parts, reference to the previous node, data and reference to the next node.

Node of doubly linked list
Open Image

Here is a pseudo-code for the node of a doubly linked list.

class Node{
    Node previousNode;
    Object data;
    Node nextNode;
}

This is the reason that it is possible to traverse the doubly linked list in forward as well as backward direction.

Doubly linked list data structure
Open ImageThe previous node reference of the first node is set to NULL that represents it is the starting node. Similarly, the next node reference of the last node is also NULL which represent the end of the linked list.

Here is a python program just for a clear understanding of doubly linked list data structure.

class Node:
    #Constructor
    def __init__(self, data):
        self.previousNode = None
        self.data = data
        self.nextNode = None

node1 = Node(5)
node2 = Node(9)
node3 = Node(13)
node4 = Node(17)

#Connect them manually (just for understanding)
node1.nextNode = node2
node2.previousNode = node1
node2.nextNode = node3
node3.previousNode = node2
node3.nextNode = node4
node4.previousNode = node3

#Verify they are connected
pointer = node1
#Traverse until last node (last node has nextNode=None)
while(1):
    print(pointer.data, sep="", end="")
    # If pointer is on last node break while loop and exit
    if(pointer.nextNode is None):
        break
    #for Visual Formatting only
    print("", end=" => ")
    #Move pointer to next node
    pointer = pointer.nextNode
print("\nTraverse in Reverse")
#Reverse Traverse
while(1):
    print(pointer.data, sep="", end="")
    # If pointer is on last node break while loop and exit
    if(pointer.previousNode is None):
        break
    #for Visual Formatting only
    print("", end=" <= ")
    #Move pointer to next node
    pointer = pointer.previousNode

Output:

5 => 9 => 13 => 17 Traverse in Reverse 17 <= 13 <= 9 <= 5

Circular Linked List

Circular linked lists are similar to the singly linked list except the last node is connected to the first node because the next node reference of the last node refers to the first node (see the picture). It forms a circular path.

singly circular linked list
Open ImageDoubly linked lists can also be circular. Here is the picture that demonstrates the concept.

doubly Circular linked list data structure
Open ImageIt means the previous node reference of the first node points to the last node of the linked list and the next node reference of the last node points to the first node.

Here is a Python program for implementation of doubly circular linked list data structure.

class Node:
    #Constructor
    def __init__(self, data):
        self.previousNode = None
        self.data = data
        self.nextNode = None

node1 = Node(5)
node2 = Node(9)
node3 = Node(13)
node4 = Node(17)

#Connect them manually (just for understanding)
node1.previousNode = node4
node1.nextNode = node2
node2.previousNode = node1
node2.nextNode = node3
node3.previousNode = node2
node3.nextNode = node4
node4.nextNode = node1
node4.previousNode = node3

#Verify they are connected
n=20
pointer = node1
while(n is not 0):
    print(pointer.data, end="=>")
    pointer = pointer.nextNode
    n = n-1

The output of the above code will be:

5=>9=>13=>17=>5=>9=>13=>17=>5=>9=>13=>17=>5=>9=>13=>17=>5=>9=>13=>17=>

Advantages Of Linked List

Dynamic Size

Whenever we need to add new data we can simply add a new node. The length of the linked list is not fixed, it is dynamic.

This is an advantage over an array. Because we need to define the length of the array at its initialization and it is not easy to change it.

No wastage of Memory

Because the length is not fixed, there is no wastage of memory. We add new node only when we need to store some data.

We can relate this with an array, the length of the array is fixed which means it occupies that space in memory. If we do not use that, the array will still hold it and it will go waste.

Efficient Insertion and Deletion

Insertion and deletion only require to change the reference of the next node (and previous node) to the new node.

In array, the insertion and deletion are much more costly because all the elements need to shift from their original position.

Drawbacks of Linked List

Accessing Element

The linked list does not support indexing. We cannot get data by their index position.

Each time we need to traverse the linked list and reach to a certain position to extract the data.

Extra Memory Requirement

Some extra memory is required with each node to hold the reference of the next node and previous node in case of doubly and circular linked list.

When to use Linked Lists?

Linked lists are very helpful in the situations when we need to add and remove data frequently. It is also used as an alternative of the array when the length of data is unknown.

The LInked list is dynamic so we can easily add new nodes.

Here are some example use cases which use linked list data structure.

Browser Previous and next button: It will be efficient to use a linked list to implement a back and forward button in a doubly-linked list as we can easily access the previous and next node.

Songs in Playlist: The user can frequently add and remove songs from his playlist. It will be efficient to implement linked list because insertion and deletion are less costly.

Undo and Redo functionality: Linked lists can also be used to implement undo and redo functionality in any program.

Summary

It was all about the linked list. Here is a quick summary of the most important points described above.

  • A linked list is a good alternative to the array when the length of data is unknown.
  • Linked lists are made up of nodes which contain the data and reference to the next node.
  • Linked list are of three types:
    • Singular Linked List
    • Doubly Linked List
    • Circular Linked List
  • Dynamic size, efficient memory use and cheap insertion and deletion are advantages of the linked list.
  • Linked lists have a disadvantage of accessing element and extra memory for pointers that hold the reference to the next and previous node.
  • Use a linked list when you need frequent insertion and deletion.

If you have any problem let me know in the comments.

Join Our Youtube Channel

Subscribe