Linear Data Structures

Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence.

Each node holds its own data and the address of the next node hence forming a chain like structure.

Linked Lists are used to create trees and graphs.

Advantages of Linked Lists
  • They are a dynamic in nature which allocates the memory when required.
  • Insertion and deletion operations can be easily implemented.
  • Stacks and queues can be easily executed.
  • Linked List reduces the access time.
Disadvantages of Linked Lists
  •  The memory is wasted as pointers require extra memory for storage.
  • No element can be accessed randomly; it has to access each node sequentially.
  • Reverse Traversing is difficult in linked list.
Applications of Linked Lists
  • Linked lists are used to implement stacks, queues, graphs, etc.
  • Linked lists let you insert elements at the beginning and end of the list.
  • In Linked Lists we don't need to know the size in advance.

 

Types of Linked Lists

 There are 3 different implementations of Linked List available, they are:

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List

Let's know more about them and how they are different from each other.

1.  Singly Linked List

 A linked list is a way to store a collection of elements. Like an array these can be character or integers. Each element in a linked list is stored in the form of a node.

Node:

A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.

Linked List:

A linked list is formed when many such nodes are linked together to form a chain. Each node points to the next node present in the order. The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.

2.  Doubly Linked List

 Doubly linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.

 

The two links help us to traverse the list in both backward and forward direction. But storing an extra link requires some extra space.

Implementation of Doubly Linked List

 

First we define the node.

 

Now we define our class Doubly Linked List. It has the following methods:

  • add_front: Adds a new node in the beginning of list
  • add_after: Adds a new node after another node
  • add_before: Adds a new node before another node
  • add_end: Adds a new node in the end of list
  • delete: Removes the node
  • forward_traverse: Traverse the list in forward direction
  • backward_traverse: Traverse the list in backward direction

Operations in Doubly Linked List

 i)  Insert Data in the beginning

  1.  The prev pointer of first node will always be NULL and next will point to front.
  2. If the node is inserted is the first node of the list then we make front and end point to this node.
  3. Else we only make front point to this node.

ii) Insert Data before a Node

Let’s say we are inserting node X before Y. Then X’s next pointer will point to Y and X’s prev pointer will point the node Y’s prev pointer is pointing. And Y’s prev pointer will now point to X. We need to make sure that if Y is the first node of list then after adding X we make front point to X.

iii) Insert Data after a Node

Let’s say we are inserting node Y after X. Then Y’s prev pointer will point to X and Y’s next pointer will point the node X’s next pointer is pointing. And X’s next pointer will now point to Y. We need to make sure that if X is the last node of list then after adding Y we make end point to Y.

iv) Insert Data in the end

  1. The next pointer of last node will always be NULL and prev will point to end.
  2. If the node is inserted is the first node of the list then we make front and end point to this node.
  3. Else we only make end point to this node.

v) Remove a Node

Removal of a node is quite easy in Doubly linked list but requires special handling if the node to be deleted is first or last element of the list. Unlike singly linked list where we require the previous node, here only the node to be deleted is needed. We simply make the next of the previous node point to next of current node (node to be deleted) and prev of next node point to prev of current node. Look code for more details.

vi) Forward Traversal

Start with the front node and visit all the nodes until the node becomes NULL.

vii) Backward Traversal

 Start with the end node and visit all the nodes until the node becomes NULL.

3.  Circular Linked List

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.

               

Application of Circular Linked List

  • The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
  • Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance
  • Circular Linked List can also be used to create Circular queue.  In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have its next point to the Head of the List. In Linear linked list the last Node simply holds NULL in its next pointer.

So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.

i. Insertion at the Beginning

 Steps to insert a Node at beginning:

  1. The first Node is the Head for any Linked List.
  2. When a new Linked List is instantiated, it just has the Head, which is Null.
  3. Else, the Head holds the pointer to the first Node of the List.
  4. When we want to add any Node at the front, we must make the head point to it.
  5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL (in case of new List) or the pointer to the first Node of the List.
  6. The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.

ii. Insertion at the End

 Steps to insert a Node at the end:

  1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
  2. If the Linked List is not empty then we find the last node, and make it' next to the new Node, and make the next of the newly added Node point to the Head of the List.

iii. Deleting a Node from the List

Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.

To remove any Node from the list, we need to do the following:

  1. If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.
  2. If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted. And update the next pointer of the Last Node as well.
  3. If the Node is at the end, then remove it and make the new last node point to the head.