Progress

Linked Lists Data Structures with Algorithm and Examples

Linked Lists Data Structures with Algorithm and 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.

linked list data structure
Singly linked list also known as 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 specific sitation. We need to know them in depth to understand them.

Singly Linked List

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

singly Linked list node

It means the traversal of singly linked list is only one way. We can only traverse forward and not backward because there is no reference to 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 singly linked list.

class Node{
    Object data;
    Node nextNode;
}

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

Here is python program implementation of singly linked list.

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

LinkedList.py
Copy
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 previous node, data and reference to next node.

Node of doubly linked list

Here is a pseudo code for the node of 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

The 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.

doublyLinkedList.py
Copy
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 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

Doubly linked lists can also be circular. Here is the picture that demonstrate the concept.

doubly Circular linked list data structure
Doubly Circular Linked List

It 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.

doublyCircularLL.py
Copy
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
Output
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 array because in array we need to define length 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 next node (and previous node) to the new node.

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

Drawbacks of Linked List

Accessing Element

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

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

Extra Memory Requirement

Some extra memory is requires 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.

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 linked list. Here is a quich 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.

Share the Post ;)

Related Posts