Linked lists are one of the linear data structures like arrays but they are non-linear in storing their elements i.e. they do not store in a continuous manner such as arrays. In this blog we will be talking about:

• What are Linked Lists (Other than the definition)
• Initialization and Traversal
• Important Operations (Insertion && Deletion)
• What are its types

What are Linked Lists?

Linked Lists are linear and non-linear at the same time. With their storage being not in sequential manner, they are non-linear but then how they are counted with other linear data structures like arrays, stacks or queues.

They do store the data at different places in a memory but in a sequential manner. How? They use pointers. With each element they store the pointer to the next element and in this way the elements are stored in a sequential manner but the locations can be far away from the previous element.

But what's the point of storing in such a manner?

Like in arrays, the elements are stored in a sequential manner but the memory is limited and the processes of insertion and deletion takes more time.

And linked list helps in such a way that they have no problem with the memory limitations and is efficient while handling insertion or deletion than arrays.

Initializing && Traversing a Linked List:

We will be making a class for a Node in a Linked List which will have:

1. Data of the element

2. Pointer to the next element.

class Node{
    public:
        int data;
        Node* next;

        //to introduce new nodes with their data
        Node(int x){
            data = x;
            next = NULL;
        }
};

Calling them in the main function:

int main()
{
    //Intialising the head element.
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    /*
        It looks like
        1->2->3->4->5->NULL
        ⬆
      (head)
    */

    //A temporary node to traverse the linked list
    Node* curr = head;

    //traversing the linked list
    while(curr != NULL){
        cout<<curr->data<<" ";

        //iterating to the next element
        curr = curr->next;
    }
    return 0;
}
// O/P: 1 2 3 4 5

And that's how you initialize and traverse the Linked List.

It's Operations

Insertion and Deletion are two of the main operations on a Linked List. These operations can be done at three locations in a Linked List:

1. At the beginning.

2. At a particular position.

3. At the end.

➡ Insertion:

⭐At the beginning:

When we are adding an element at the beginning, there are few points to handle:

• The new element should have a pointer to next element (former head element).

• Changing the head of the list

Example:

Linked List: 1->2->3->4->5, New Element: 6

New Linked List: 6->1->2->3->4->5

In this, we changed new element(6) pointer to next element(1) and head points to 6 now.

Node* insertAtBeginning(Node* head){
    //Declaring a new Node
    Node* temp = new Node(5);

    //Pointer for next element
    temp->next = head;

    //Making the new element, head of the list
    head = temp;

    //return the new head;
    return head;
}

⭐At particular position:

When we are adding an element at a particular position, there are few points to handle:

• Keep the position one less than the desired position to handle pointers.

• The new element should have a pointer to next element.

• The previous element should now point to the new element.

We keep a count element and current node to add the element in the list.

Example:

Linked List: 1->2->3->4->5 New Element: 6

New Linked List: 1->2->3->6->4->5

In this, we changed new element(6) pointer to next element(4) and previous element(3) points to 6 now.

Node* insertAtPosition(Node* head, int pos){
    //Declaring a new Node
    Node* temp = new Node(6);

    //Node to keep check on current element
    Node* curr = head;

    //Count to check position
    int count = 1;
    while(count<pos && curr != NULL){
        count++;
        curr = curr->next;
    }

    if(count == pos){
        //points to handle
        temp->next = curr->next;
        curr->next = temp;
    }

    return head;
}

⭐At the end:

When we are adding an element at the end, there are few points to handle:

• The new element should have a pointer to NULL.

• The new element should have a pointer to new element.

It's quite similar to the operation of inserting at a particular position.

Example:

Linked List: 1->2->3->4->5 New Element: 6

New Linked List: 1->2->3->4->5->6

In this, we changed new element(6) pointer to NULL and previous element(5) points to 6 now.

Node* insertAtEnd(Node* head){
    //Declaring a new Node
    Node* temp = new Node(6);

    //Node to keep check on current element
    Node* curr = head;

    //Traversing till 5 only and not to NULL
    while(curr->next != NULL){
        curr = curr->next;
    }

    //points to handle
    curr->next = temp;
    temp->next = NULL;

    return head;
}

Now it's time to talk about the Deletion operation at the three positions.

➡ Deletion:

⭐From the beginning:

When we are removing an element from the beginning, there are few points to handle:

• The second element should be the head of the linked list now.

• Free the memory of first element of the list.

The above can be handled by using a temporary node.

Example:

Linked List: 1->2->3->4->5->6 Element to be deleted: 1

New Linked List: 2->3->4->5->6

In this, we changed head pointer to next element(2) and free memory of 1.

Node* deleteFromBeginning(Node* head){
    //Temporary node to keep check on head element
    Node* temp = head;

    //Move head to next element
    head = head->next;

    //Free the first node
    free(temp);

    return head;
}

⭐From particular position:

When we are removing an element from a particular position, there are few points to handle:

• Reach the desired element by keep the track of count.

• The previous element (of the yet to be deleted element) should now point to the next element.

This can be done by keeping a node to the current and previous element.

Example:

Linked List: 1->2->3->4->5->6 Element to delete: 4

New Linked List: 1->2->3->5->6

In this, we changed previous element(3) pointer to next element(5) and free current element(4) from memory.

Node* deleteFromPosition(Node* head, int pos){
    //Node to keep check on current and previous element
    Node* curr = head, *prev;
    int count = 1;

    //traversing the LL to the desired element 
    while(count<pos && curr->next != NULL){
        count++;

        //keeping a check on current and previous element
        prev = curr;
        curr = curr->next;
    }

    //points to handle 
    prev->next = curr->next;

    free(curr);

    return head;
}

⭐From the end:

When we are removing an element from the end, there are few points to handle:

• It should be given the same points as deletion from particular position.

• The second-last element now points to NULL.

Example:

Linked List: 1->2->3->4->5->6 Element to be deleted: 6

New Linked List: 1->2->3->4->5->NULL

In this, we changed removed element(6) and previous element(5) points to NULL now.

Node* deleteFromEnd(Node* head){
    //Node to keep check on current and previous element
    Node* curr = head, *prev;

    //traversing the LL to the last element 
    while(curr->next != NULL){
        //keeping a check on current and previous element
        prev = curr;
        curr = curr->next;
    }

    //points to handle 
    prev->next = NULL;

    free(curr);

    return head;
}

Types of Linked Lists

We will talk about two types of Linked Lists:

• Doubly Linked Lists

• Circular Linked Lists

• Doubly Linked Lists: The Linked Lists we have learnt about so far are also called Singly Linked Lists. Now, it gets easy to know what are Doubly Linked Lists. These are the lists with two pointers one pointing to the next element and other to the previous element.

A representation of Doubly Linked List:

    1<->2<->3<->4<->5<->6

It's an enhanced version of singly linked lists as now we can move forwards and backwards. In this, we don't have to be at the previous element to insert and delete the desired element, it can be done from both ways unlike singly linked lists.

But it require more space for that extra pointer and the process of insertion or deletion is not as much efficient as in singly linked lists.

1. Circular Linked Lists: Circular Linked Lists are Singly Linked Lists only but with last element pointing back to the first element.

    1->2->3->4->5->6
    ⬆              ⬇
     ⬅ ⬅ ⬅ ⬅  ⬅

As each element always have a successor, one needs to be cautious while traversing them or traversal can go on forever.

Their best use case is in managing computing resources and implementing stacks and queues.

Points to Remember

So, we have covered a lot about Linked Lists, here's a quick summary to revise up the points:

• Linked Lists are linear data structures but store elements in a non-linear way.

• They use pointers to store elements in sequential manner.

• They are efficient than arrays in performing Insertion and Deletion and don't have memory restrictions.

• Insertions and Deletion occur at 3 positions:

  1. At the Beginning

  2. At a particular position

  3. At the End

• There are 2 types of Linked Lists: Doubly and Circular

• Doubly Linked Lists have pointer to the forward and backward elements making it more accessible than Singly Linked Lists.

• In Circular Linked Lists, each element has a successor, even the last element. Last element points back to first element.

Now, I believe you are prepared enough to work with operations on Doubly Linked Lists on your own. Just keep in mind to work with pointers on both sides.