Content

• Limitation of Arrays
• Working of LinkedList
• Singly LinkedList
  • Insertion in Singly LinkedList
  • Display Singly LinkedList
  • Deletion in Singly LinkedList
• Some Common Doubts
• Doubly LinkedList
  • Insertion in Doubly LinkedList
  • Display Doubly LinkedList
• Reversal of LinkedList
• Circular LinkedList
  • Insertion in Circular LinkedList
  • Display Circular LinkedList
  • Deletion in Circular LinkedList

Limitation of Arrays

Arrays have a fixed size determined during their creation. Once the size is set, it cannot be easily changed. This limitation can cause problems when you need to store a variable number of elements or when you don’t know the exact size of the data beforehand.

When using arrays, you may encounter the following issues:

• Fixed Size: Arrays have a fixed size that needs to be declared in advance. If you exceed the allocated size, you may encounter buffer overflow errors or data loss.
• Memory Wastage: If you allocate a large size for an array but only use a small portion of it, the remaining memory goes unused, resulting in memory wastage.
• Insertion and Deletion: Inserting or deleting an element in an array requires shifting elements to accommodate the change. This operation can be time-consuming, especially for large arrays or when elements need to be inserted or deleted frequently.
• Contiguous Memory: Arrays need contiguous memory locations to store elements. In situations where contiguous memory is not available, arrays cannot be used efficiently.

Now, let’s move on to the working of a linked list.

Working of LinkedList

A linked list is a data structure that consists of a sequence of nodes, where each node contains a data element and a reference (or link) to the next node in the sequence. The last node’s reference is typically set to nullptr (or null in some languages) to indicate the end of the list.

Unlike arrays, linked lists do not require contiguous memory allocation, and their size can dynamically change during program execution. Each node in a linked list contains two components: the data and the link.

The link (or pointer) points to the next node in the sequence. This linking mechanism allows traversing the entire list by following the links from one node to another.

Linked lists offer flexibility in terms of insertion and deletion, as these operations can be performed without shifting other elements. However, accessing an element at a specific index in a linked list requires traversing the list from the beginning until reaching the desired index.

Singly LinkedList

A singly linked list is the simplest form of a linked list. Each node in a singly linked list contains a data element and a link to the next node. The last node’s link points to nullptr (or null in some languages) to indicate the end of the list.

Here’s an example of a Node structure for a singly linked list in C++:

1
2
3
4

struct Node {
    int data;
    Node* next;
};

In the above structure, data represents the data stored in the node, and next is a pointer to the next node in the list.

To visualize a singly linked list, consider the following example:

List:  [data1] -> [data2] -> [data3] -> nullptr

In the above example, each node contains a data element, and the arrow indicates the link from one node to another. The last node’s link points to nullptr, indicating the end of the list.

Insertion in Singly LinkedList

To insert a new node in a singly linked list, you need to consider two scenarios: inserting at the beginning and inserting at the end or in the middle of the list.

1. Insertion at the Beginning

To insert a new node at the beginning of a singly linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• Set the next pointer of the new node to the current first node.
• Update the head pointer to point to the new node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void insertAtBeginning(Node** head, int data) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // Set the next pointer of the new node to the current first node
    newNode->next = *head;
    
    // Update the head pointer
    *head = newNode;
}

2. Insertion at the End or in the Middle:

To insert a new node at the end or in the middle of a singly linked list, you need to traverse the list until you reach the desired position. Follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• Traverse the list until you reach the desired position.
• Update the next pointers accordingly to insert the new node.

Here’s an example implementation in C++ for inserting at the end:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void insertAtEnd(Node** head, int data) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // Set the next pointer of the new node to nullptr
    newNode->next = nullptr;
    
    // If the list is empty, make the new node the head
    if (*head == nullptr) {
        *head = newNode;
        return;
    }
    
    // Traverse to the last node
    Node* current = *head;
    while (current->next != nullptr) {
        current = current->next;
    }
    
    // Update the next pointer of the last node
    current->next = newNode;
}

Display Singly LinkedList

To display the elements of a singly linked list, you can traverse the list starting from the head node and print the data of each node until you reach the end of the list.

Here’s an example implementation in C++:

1
2
3
4
5
6
7
8
9

void displayLinkedList(Node* head) {
    // Traverse the list and print each node's data
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

In the above code, we start with the head node and print the data of each node until we reach the end of the list (i.e., when the next pointer becomes nullptr).

Now that we’ve covered insertion and display in a singly linked list, let’s move on to deletion in a singly linked list.

Deletion in Singly LinkedList

To delete a node from a singly linked list, you need to consider two scenarios: deleting the first node and deleting a node in the middle or at the end of the list.

1. Deletion of the First Node:

To delete the first node of a singly linked list, follow these steps:

• Check if the list is empty. If it is, there’s nothing to delete.
• Update the head pointer to point to the next node.
• Free the memory allocated to the deleted node. Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void deleteFirstNode(Node** head) {
    if (*head == nullptr) {
        cout << "List is empty. Nothing to delete." << endl;
        return;
    }
    
    // Store the reference to the first node
    Node* temp = *head;
    
    // Update the head pointer to the next node
    *head = (*head)->next;
    
    // Free the memory of the deleted node
    delete temp;
}

2. Deletion of a Node in the Middle or at the End:

To delete a node in the middle or at the end of a singly linked list, you need to traverse the list until you reach the node to be deleted. Follow these steps:

• Check if the list is empty. If it is, there’s nothing to delete.
• Traverse the list until you find the node to be deleted and its previous node.
• Update the next pointer of the previous node to skip the node to be deleted.
• Free the memory allocated to the deleted node.

Here’s an example implementation in C++ for deleting a node with a given value:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void deleteNodeWithValue(Node** head, int value) {
    if (*head == nullptr) {
        cout << "List is empty. Nothing to delete." << endl;
        return;
    }
    
    Node* current = *head;
    Node* previous = nullptr;
    
    // Traverse until the node to be deleted is found
    while (current != nullptr && current->data != value) {
        previous = current;
        current = current->next;
    }
    
    // If the node was not found
    if (current == nullptr) {
        cout << "Node not found in the list." << endl;
        return;
    }
    
    // Update the next pointer of the previous node to skip the node to be deleted
    if (previous != nullptr) {
        previous->next = current->next;
    } else {
        // If the node to be deleted is the first node, update the head pointer
        *head = current->next;
    }
    
    // Free the memory of the deleted node
    delete current;
}

Now, let’s address some common doubts you might have before moving on to the next topic.

Some Common Doubts

1. Q: How can I access an element at a specific index in a singly linked list?

   A: Unlike arrays, accessing an element at a specific index in a singly linked list requires traversing the list from the beginning until you reach the desired index. Start with the head node and follow the next pointers until you reach the desired position.

2. Q: Can a singly linked list contain duplicate values?

   A: Yes, a singly linked list can contain duplicate values. Each node in the list holds its own data value, so it is possible to have multiple nodes with the same data.

3. Q: How do I find the length of a singly linked list?

   A: To find the length of a singly linked list, traverse the list from the head node while keeping a count of the number of nodes visited. Increment the count for each node until you reach the end of the list.

4. Q: Can I delete multiple nodes with the same value in a singly linked list?

   A: Yes, you can delete multiple nodes with the same value in a singly linked list. To do so, continue traversing the list and deleting nodes with the desired value until no more occurrences are found.

5. Q: What happens to the memory of a deleted node in a singly linked list?

   A: When a node is deleted from a singly linked list, the memory allocated to that node is freed. It can be reused for other purposes.

These are some common doubts that beginners often have regarding singly linked lists. If you have any more specific questions or doubts, feel free to ask in the comment section.

Now, let’s move on to the next topic: doubly linked lists.

Doubly LinkedList

A doubly linked list is a type of linked list where each node contains a data element, a pointer to the next node, and a pointer to the previous node. This bidirectional linking allows traversal in both forward and backward directions.

Here’s an example of a Node structure for a doubly linked list in C++:

1
2
3
4
5

struct Node {
    int data;
    Node* next;
    Node* prev;
};

In the above structure, data represents the data stored in the node, next is a pointer to the next node, and prev is a pointer to the previous node.

To visualize a doubly linked list, consider the following example:

List:  nullptr <- [data1] <-> [data2] <-> [data3] -> nullptr

In the above example, each node contains a data element, and the double arrows indicate the bidirectional links between nodes. The prev pointer of the first node and the next pointer of the last node are set to nullptr to indicate the beginning and end of the list, respectively.

Doubly linked lists provide more flexibility compared to singly linked lists. They allow efficient traversal in both directions but require additional memory to store the prev pointers.

Next, let’s explore insertion in a doubly linked list.

Insertion in Doubly LinkedList

Insertion in a doubly linked list can be performed in a similar manner to a singly linked list. You need to consider three scenarios: inserting at the beginning, inserting at the end, and inserting in the middle of the list.

1. Insertion at the Beginning:

To insert a new node at the beginning of a doubly linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• Set the next pointer of the new node to the current first node.
• Set the prev pointer of the new node to nullptr.
• Update the prev pointer of the current first node to point to the new node.
• Update the head pointer to point to the new node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void insertAtBeginning(Node** head, int data) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // Set the next pointer of the new node to the current first node
    newNode->next = *head;
    
    // Set the prev pointer of the new node to nullptr
    newNode->prev = nullptr;
    
    // Update the prev pointer of the current first node
    if (*head != nullptr) {
        (*head)->prev = newNode;
    }
    
    // Update the head pointer
    *head = newNode;
}

2. Insertion at the End:

To insert a new node at the end of a doubly linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• Set the next pointer of the new node to nullptr.
• Traverse the list until you reach the last node.
• Set the next pointer of the last node to the new node.
• Set the prev pointer of the new node to the last node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void insertAtEnd(Node** head, int data) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // Set the next pointer of the new node to nullptr
    newNode->next = nullptr;
    
    // If the list is empty, make the new node the head
    if (*head == nullptr) {
        newNode->prev = nullptr;
        *head = newNode;
        return;
    }
    
    // Traverse to the last node
    Node* current = *head;
    while (current->next != nullptr) {
        current = current->next;
    }
    
    // Update the next pointer of the last node and the prev pointer of the new node
    current->next = newNode;
    newNode->prev = current;
}

3. Insertion in the Middle:

To insert a new node in the middle of a doubly linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• Traverse the list until you reach the desired position.
• Set the next pointer of the new node to the next node.
• Set the prev pointer of the new node to the current node.
• Update the next pointer of the current node to point to the new node.
• Update the prev pointer of the next node to point to the new node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void insertInMiddle(Node** head, int data, int position) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // Traverse to the desired position
    Node* current = *head;
    int currentPosition = 1;
    while (currentPosition < position && current->next != nullptr) {
        current = current->next;
        currentPosition++;
    }
    
    // Update the next pointer of the new node and the prev pointer of the next node
    newNode->next = current->next;
    newNode->prev = current;
    
    // Update the next pointer of the current node and the prev pointer of the next node
    if (current->next != nullptr) {
        current->next->prev = newNode;
    }
    current->next = newNode;
}

These are the basic operations for inserting nodes in a doubly linked list. You can adapt these operations to insert nodes at specific positions as well.

Now, let’s move on to displaying the elements of a doubly linked list.

Display Doubly LinkedList

To display the elements of a doubly linked list, you can traverse the list in either the forward or backward direction, printing the data of each node as you go.

Here’s an example implementation in C++ for displaying a doubly linked list in the forward direction:

1
2
3
4
5
6
7
8
9

void displayForward(Node* head) {
    // Traverse the list and print each node's data
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

And here’s an example implementation in C++ for displaying a doubly linked list in the backward direction:

1
2
3
4
5
6
7
8
9

void displayBackward(Node* tail) {
    // Traverse the list in reverse and print each node's data
    Node* current = tail;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->prev;
    }
    cout << endl;
}

In the above code, we start with either the head node (for forward traversal) or the tail node (for backward traversal) and print the data of each node until we reach the end of the list.

These display functions allow you to visualize the elements stored in a doubly linked list in both the forward and backward directions.

Now that we’ve covered doubly linked lists, let’s move on to the topic of reversing a linked list.

Reversal of LinkedList:

Reversing a linked list involves changing the direction of the links between the nodes, effectively flipping the list in the opposite direction.

To reverse a singly linked list, you need to modify the links between the nodes. Follow these steps:

• Initialize three pointers: previous (initialized as nullptr), current (initialized as the head), and next (initialized as nullptr).
• Traverse the list while updating the links:
• Set next to the node following current.
• Update the next pointer of current to point to previous.
• Move previous to current and current to next.
• Update the head pointer to point to the new first node (which was the last node in the original list).

Here’s an example implementation in C++ for reversing a singly linked list:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void reverseLinkedList(Node** head) {
    Node* previous = nullptr;
    Node* current = *head;
    Node* next = nullptr;
    
    while (current != nullptr) {
        next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    
    *head = previous;
}

After reversing the linked list, the new head becomes the previous tail, and the new tail becomes the previous head.

Next, let’s explore the concept of a circular linked list.

Circular LinkedList:

A circular linked list is a type of linked list where the last node’s next pointer does not point to nullptr but instead points back to the first node, forming a circular structure.

Here’s an example of a circular linked list:

1
2
3
4

List:  [data1] -> [data2] -> [data3] -> ... -> [dataN] ->
                                               ^        |
                                               |        v
                                             <- [data1] <-

In the above example, the last node’s next pointer points back to the first node, creating a loop that allows for continuous traversal.

The circular linked list can be either singly or doubly linked, depending on whether the nodes have a single or double link.

Now, let’s explore insertion in a circular linked list.

Insertion in Circular LinkedList:

To insert a new node into a circular linked list, you need to consider three scenarios: inserting at the beginning, inserting at the end, and inserting in the middle of the list.

1. Insertion at the Beginning:

To insert a new node at the beginning of a circular linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• If the list is empty, set the next pointer of the new node to itself.
• If the list is not empty, set the next pointer of the new node to the current first node.
• Update the next pointer of the last node to point to the new node.
• Update the head pointer to point to the new node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void insertAtBeginning(Node** head, int data) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // If the list is empty, make the new node point to itself
    if (*head == nullptr) {
        newNode->next = newNode;
    } else {
        // Set the next pointer of the new node to the current first node
        newNode->next = *head;
        
        // Traverse to the last node
        Node* current = *head;
        while (current->next != *head) {
            current = current->next;
        }
        
        // Update the next pointer of the last node
        current->next = newNode;
    }
    
    // Update the head pointer
    *head = newNode;
}

2. Insertion at the End:

To insert a new node at the end of a circular linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• If the list is empty, make the new node point to itself.
• If the list is not empty, traverse to the last node.
• Set the next pointer of the new node to the current first node.
• Update the next pointer of the last node to point to the new node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void insertAtEnd(Node** head, int data) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // If the list is empty, make the new node point to itself
    if (*head == nullptr) {
        newNode->next = newNode;
    } else {
        // Traverse to the last node
        Node* current = *head;
        while (current->next != *head) {
            current = current->next;
        }
        
        // Set the next pointer of the new node to the current first node
        newNode->next = *head;
        
        // Update the next pointer of the last node
        current->next = newNode;
    }
    
    // Update the head pointer
    *head = newNode;
}

3. Insertion in the Middle:

To insert a new node in the middle of a circular linked list, follow these steps:

• Create a new node and allocate memory for it.
• Set the data of the new node to the desired value.
• Traverse the list until you reach the desired position.
• Set the next pointer of the new node to the next node.
• Update the next pointer of the current node to point to the new node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void insertInMiddle(Node** head, int data, int position) {
    // Create a new node
    Node* newNode = new Node();
    
    // Set the data of the new node
    newNode->data = data;
    
    // Traverse to the desired position
    Node* current = *head;
    int currentPosition = 1;
    while (currentPosition < position && current->next != *head) {
        current = current->next;
        currentPosition++;
    }
    
    // Set the next pointer of the new node to the next node
    newNode->next = current->next;
    
    // Update the next pointer of the current node to point to the new node
    current->next = newNode;
}

These are the basic operations for inserting nodes in a circular linked list. You can adapt these operations to insert nodes at specific positions as well.

Next, let’s discuss how to display the elements of a circular linked list.

Display Circular LinkedList:

To display the elements of a circular linked list, you can start with the head node and traverse the list until you reach the starting point again.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void displayCircularLinkedList(Node* head) {
    // If the list is empty, print a message and return
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }
    
    // Traverse the list and print each node's data until we reach the starting point again
    Node* current = head;
    do {
        cout << current->data << " ";
        current = current->next;
    } while (current != head);
    
    cout << endl;
}

In the above code, we start with the head node and print the data of each node until we reach the starting point again (i.e., when the next pointer becomes equal to the head).

These are the basic operations and concepts related to circular linked lists.

Lastly, let’s cover the last topic of our extensive post on LinkedList the deletion in a circular linked list.

Deletion in Circular LinkedList

To delete a node from a circular linked list, you need to consider three scenarios: deleting the first node, deleting the last node, and deleting a node in the middle of the list.

1. Deletion of the First Node:

To delete the first node of a circular linked list, follow these steps:

• Check if the list is empty. If it is, there’s nothing to delete.
• Update the next pointer of the last node to skip the first node.
• Update the head pointer to point to the next node.
• Free the memory allocated to the deleted node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void deleteFirstNode(Node** head) {
    if (*head == nullptr) {
        cout << "List is empty. Nothing to delete." << endl;
        return;
    }
    
    // Store the reference to the first node
    Node* firstNode = *head;
    
    // Traverse to the last node
    Node* lastNode = *head;
    while (lastNode->next != *head) {
        lastNode = lastNode->next;
    }
    
    // Update the next pointer of the last node to skip the first node
    lastNode->next = firstNode->next;
    
    // Update the head pointer to the next node
    *head = firstNode->next;
    
    // Free the memory of the deleted node
    delete firstNode;
}

2. Deletion of the Last Node: To delete the last node of a circular linked list, follow these steps:

• Check if the list is empty. If it is, there’s nothing to delete.
• Traverse to the second-to-last node.
• Update the next pointer of the second-to-last node to point back to the first node.
• Free the memory allocated to the deleted node.

Here’s an example implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void deleteLastNode(Node** head) {
    if (*head == nullptr) {
        cout << "List is empty. Nothing to delete." << endl;
        return;
    }
    
    // Traverse to the second-to-last node
    Node* secondToLastNode = *head;
    while (secondToLastNode->next->next != *head) {
        secondToLastNode = secondToLastNode->next;
    }
    
    // Store the reference to the last node
    Node* lastNode = secondToLastNode->next;
    
    // Update the next pointer of the second-to-last node to point back to the first node
    secondToLastNode->next = *head;
    
    // Free the memory of the deleted node
    delete lastNode;
}

• Check if the list is empty. If it is, there’s nothing to delete.
• Traverse the list until you find the node to be deleted and its previous node.
• Update the next pointer of the previous node to skip the node to be deleted.
• Free the memory allocated to the deleted node.

Here’s an example implementation in C++ for deleting a node with a given value:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void deleteNodeWithValue(Node** head, int value) {
    if (*head == nullptr) {
        cout << "List is empty. Nothing to delete." << endl;
        return;
    }
    
    Node* current = *head;
    Node* previous = nullptr;
    
    // Traverse until the node to be deleted is found
    do {
        previous = current;
        current = current->next;
    } while (current != *head && current->data != value);
    
    // If the node was not found
    if (current == *head) {
        cout << "Node not found in the list." << endl;
        return;
    }
    
    // Update the next pointer of the previous node to skip the node to be deleted
    previous->next = current->next;
    
    // If the node to be deleted is the head, update the head pointer
    if (current == *head) {
        *head = current->next;
    }
    
    // Free the memory of the deleted node
    delete current;
}

These are the basic operations for deleting nodes in a circular linked list. You can adapt these operations to delete nodes with specific values or at specific positions.

With these concepts covered, you should now have a good understanding of linked lists, including singly linked lists, doubly linked lists, circular linked lists, and the operations associated with them.