AlgoDaily - Linked Lists

Home > 30 days c++ course > 30 days c++ course > Linked Lists

Welcome to the world of Linked Lists!

Linked lists are linear data structures that store elements in a non-contiguous manner. Unlike arrays, which store elements in contiguous memory locations, linked lists use nodes to hold the elements and pointers to connect the nodes.

Let's take a look at the advantages of linked lists over arrays:

1. Dynamic Size: Linked lists can grow or shrink dynamically based on the number of elements added or removed. This makes linked lists more flexible compared to arrays, which have a fixed size.

2. Efficient Insertion and Deletion: Inserting or deleting elements in a linked list is more efficient compared to arrays. In linked lists, you just need to update the pointers, while in arrays, you need to shift elements to make space for the new element or fill the gap created by the deleted element.

3. Flexibility in Memory Management: Linked lists allow for efficient memory management. The elements can be stored anywhere in memory, and the nodes can be scattered across different locations. This allows for efficient memory allocation and utilization.

So, as you can see, linked lists offer several advantages over arrays. They are especially useful in scenarios where the size of the data is not known beforehand or when efficient insertion and deletion operations are required.

Now, let's dive deeper into the implementation of linked lists in C++. Take a look at the code snippet below:

xxxxxxxxxx
 
#include <iostream>
using namespace std;
​
int main() {
  // Linked List implementation
  // ... code here
​
  return 0;
}

Let's test your knowledge. Click the correct answer from the options.

What is a major advantage of linked lists over arrays?

Click the option that best answers the question.

Dynamic size
Random access
Fixed size
Constant time insertion

Welcome to the world of Linked Lists!

In this lesson, we will dive into implementing a linked list class and performing basic operations like insertion and deletion.

To get started, let's create a Node class that will represent each element of the linked list. Each node will contain a data value and a pointer to the next node.

TEXT/X-C++SRC

1#include <iostream>
2
3class Node {
4public:
5    int data;
6    Node* next;
7
8    Node(int value) {
9        data = value;
10        next = nullptr;
11    }
12};
13
14int main() {
15    // Create Nodes
16    Node* node1 = new Node(1);
17    Node* node2 = new Node(2);
18    Node* node3 = new Node(3);
19
20    // Link Nodes
21    node1->next = node2;
22    node2->next = node3;
23
24    // Print Linked List
25    Node* current = node1;
26    while (current != nullptr) {
27        std::cout << current->data << " ";
28        current = current->next;
29    }
30    std::cout << std::endl;
31
32    return 0;
33}

xxxxxxxxxx
}
 
#include <iostream>
​
class Node {
public:
    int data;
    Node* next;
​
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
​
int main() {
    // Create Nodes
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
​
    // Link Nodes
    node1->next = node2;
    node2->next = node3;
​
    // Print Linked List
    Node* current = node1;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }

Let's test your knowledge. Fill in the missing part by typing it in.

In a linked list, each element is represented by a ___ that contains data and a pointer to the next element.

Write the missing line below.

Now let's implement a method to search for an element in a linked list. We'll traverse through the linked list and compare the data value of each node with the target value we want to search. If we find a match, we'll return true, indicating that the element is present in the linked list. If we reach the end of the list without finding a match, we'll return false to indicate that the element is not present.

Here's the C++ code for implementing the search operation:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Linked List Node
5class Node {
6public:
7    int data;
8    Node* next;
9
10    Node(int value) {
11        data = value;
12        next = nullptr;
13    }
14};
15
16// Linked List Class
17class LinkedList {
18public:
19    Node* head;
20
21    LinkedList() {
22        head = nullptr;
23    }
24
25    // Insertion at the Beginning of the Linked List
26    void insert(int value) {
27        Node* newNode = new Node(value);
28        newNode->next = head;
29        head = newNode;
30    }
31
32    // Search for an Element in the Linked List
33    bool search(int value) {
34        Node* current = head;
35        while (current != nullptr) {
36            if (current->data == value) {
37                return true;
38            }
39            current = current->next;
40        }
41        return false;
42    }
43};
44
45int main() {
46    // Create a Linked List
47    LinkedList list;
48    list.insert(3);
49    list.insert(2);
50    list.insert(1);
51
52    // Search for an Element
53    int searchValue = 2;
54    bool isFound = list.search(searchValue);
55    if (isFound) {
56        cout << "Element " << searchValue << " is present in the Linked List." << endl;
57    } else {
58        cout << "Element " << searchValue << " is not present in the Linked List." << endl;
59    }
60
61    return 0;
62}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
class Node {
public:
    int data;
    Node* next;
​
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
​
// Linked List Class
class LinkedList {
public:
    Node* head;
​
    LinkedList() {
        head = nullptr;
    }
​
    // Insertion at the Beginning of the Linked List
    void insert(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;

Let's test your knowledge. Is this statement true or false?

In a linked list, the time complexity for searching for an element in the worst-case scenario is O(n), where n is the number of elements in the linked list.

Press true if you believe the statement is correct, or false otherwise.

To insert an element into a sorted linked list while maintaining the order, we need to find the correct position for the new element based on its value. We can then insert the new element at that position.

Here's the C++ code for implementing the insertion in a sorted linked list:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Linked List Node
5class Node {
6public:
7    int data;
8    Node* next;
9
10    Node(int value) {
11        data = value;
12        next = nullptr;
13    }
14};
15
16// Linked List Class
17class LinkedList {
18public:
19    Node* head;
20
21    LinkedList() {
22        head = nullptr;
23    }
24
25    // Insertion in a Sorted Linked List
26    void insertSorted(int value) {
27        Node* newNode = new Node(value);
28        if (head == nullptr || value < head->data) {
29            newNode->next = head;
30            head = newNode;
31        } else {
32            Node* current = head;
33            while (current->next != nullptr && current->next->data < value) {
34                current = current->next;
35            }
36            newNode->next = current->next;
37            current->next = newNode;
38        }
39    }
40};
41
42int main() {
43    // Create a Linked List
44    LinkedList list;
45    list.insertSorted(3);
46    list.insertSorted(1);
47    list.insertSorted(2);
48
49    // Print the Linked List
50    Node* current = list.head;
51    while (current != nullptr) {
52        cout << current->data << " ";
53        current = current->next;
54    }
55    cout << endl;
56
57    return 0;
58}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
class Node {
public:
    int data;
    Node* next;
​
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
​
// Linked List Class
class LinkedList {
public:
    Node* head;
​
    LinkedList() {
        head = nullptr;
    }
​
    // Insertion in a Sorted Linked List
    void insertSorted(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr || value < head->data) {
            newNode->next = head;

Build your intuition. Click the correct answer from the options.

In the context of insertion in a sorted linked list, which of the following options correctly describes the process?

A) The new element is always inserted at the beginning of the linked list.

B) The new element is inserted at the end of the linked list.

C) The new element is inserted at the correct position in the linked list while maintaining the sorted order.

D) The new element is inserted randomly at any position in the linked list.

Click the option that best answers the question.

A) The new element is always inserted at the beginning of the linked list.
B) The new element is inserted at the end of the linked list.
C) The new element is inserted at the correct position in the linked list while maintaining the sorted order.
D) The new element is inserted randomly at any position in the linked list.

To reverse a linked list, we can use a three-pointer approach. We initialize three pointers: prev, current, and next. Initially, prev and next are set to nullptr and current is set to the head of the linked list.

We then iterate through the linked list, updating the next pointer of the current node to point to the previous node. This way, we reverse the direction of the links.

Here's the C++ code for reversing a linked list using this approach:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Linked List Node
5class Node {
6public:
7    int data;
8    Node* next;
9
10    Node(int value) {
11        data = value;
12        next = nullptr;
13    }
14};
15
16// Linked List Class
17class LinkedList {
18public:
19    Node* head;
20
21    LinkedList() {
22        head = nullptr;
23    }
24
25    // Reversing a Linked List
26    void reverseList() {
27        Node* prev = nullptr;
28        Node* current = head;
29        Node* next = nullptr;
30
31        while (current != nullptr) {
32            next = current->next;
33            current->next = prev;
34            prev = current;
35            current = next;
36        }
37
38        head = prev;
39    }
40};
41
42int main() {
43    // Create a Linked List
44    LinkedList list;
45    list.head = new Node(1);
46    list.head->next = new Node(2);
47    list.head->next->next = new Node(3);
48    list.head->next->next->next = new Node(4);
49
50    // Print the original Linked List
51    Node* current = list.head;
52    while (current != nullptr) {
53        cout << current->data << " ";
54        current = current->next;
55    }
56
57    cout << endl;
58
59    // Reverse the Linked List
60    list.reverseList();
61
62    // Print the reversed Linked List
63    current = list.head;
64    while (current != nullptr) {
65        cout << current->data << " ";
66        current = current->next;
67    }
68
69    cout << endl;
70
71    return 0;
72}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
class Node {
public:
    int data;
    Node* next;
​
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
​
// Linked List Class
class LinkedList {
public:
    Node* head;
​
    LinkedList() {
        head = nullptr;
    }
​
    // Reversing a Linked List
    void reverseList() {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;

Are you sure you're getting this? Is this statement true or false?

Reversing a linked list can be achieved efficiently using a two-pointer approach.

Press true if you believe the statement is correct, or false otherwise.

Detecting a Loop in a Linked List

To detect if a linked list has a loop, we can use the Floyd's Cycle-Finding Algorithm.

The algorithm works by using two pointers, one moving at twice the speed of the other. If there is a loop in the linked list, the faster pointer will eventually catch up to the slower pointer.

Here's the C++ code for detecting a loop in a linked list using this algorithm:

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
class Node {
public:
    int data;
    Node* next;
​
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
​
// Linked List Class
class LinkedList {
public:
    Node* head;
​
    LinkedList() {
        head = nullptr;
    }
​
    // Detecting a Loop
    bool detectLoop() {
        Node* slow = head;
        Node* fast = head;
​

Build your intuition. Click the correct answer from the options.

Which algorithm can be used to detect a loop in a linked list?

Click the option that best answers the question.

Floyd's Cycle-Finding Algorithm
Binary Search
Depth-First Search
Breadth-First Search

Merging Two Sorted Linked Lists

To merge two sorted linked lists into a single sorted list, we can use a simple algorithm. We create a new list and iterate over the two input lists concurrently, comparing the elements and adding them to the new list in the sorted order.

Here's the C++ code for merging two sorted linked lists:

SNIPPET

1#include <iostream>
2using namespace std;
3
4// Linked List Node
5struct Node {
6  int data;
7  Node* next;
8  Node(int d) : data(d), next(nullptr) {}
9};
10
11// Function to merge two sorted linked lists
12Node* mergeLinkedLists(Node* head1, Node* head2) {
13  // Create a dummy node to store the merged list
14  Node* dummy = new Node(0);
15  Node* tail = dummy;
16
17  // Merge the two lists
18  while (head1 && head2) {
19    if (head1->data <= head2->data) {
20      tail->next = head1;
21      head1 = head1->next;
22    } else {
23      tail->next = head2;
24      head2 = head2->next;
25    }
26    tail = tail->next;
27  }
28
29  // Append any remaining nodes of the first list
30  if (head1) {
31    tail->next = head1;
32  }
33
34  // Append any remaining nodes of the second list
35  if (head2) {
36    tail->next = head2;
37  }
38
39  // Return the merged list
40  return dummy->next;
41}
42
43int main() {
44  // Create two sorted linked lists
45  Node* head1 = new Node(1);
46  head1->next = new Node(3);
47  head1->next->next = new Node(5);
48
49  Node* head2 = new Node(2);
50  head2->next = new Node(4);
51  head2->next->next = new Node(6);
52
53  // Merge the two lists
54  Node* mergedHead = mergeLinkedLists(head1, head2);
55
56  // Print the merged list
57  while (mergedHead) {
58    cout << mergedHead->data << " ";
59    mergedHead = mergedHead->next;
60  }
61
62  return 0;
63}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};
​
// Function to merge two sorted linked lists
Node* mergeLinkedLists(Node* head1, Node* head2) {
  // Create a dummy node to store the merged list
  Node* dummy = new Node(0);
  Node* tail = dummy;
​
  // Merge the two lists
  while (head1 && head2) {
    if (head1->data <= head2->data) {
      tail->next = head1;
      head1 = head1->next;
    } else {
      tail->next = head2;
      head2 = head2->next;
    }
    tail = tail->next;
  }
​
  // Append any remaining nodes of the first list

Are you sure you're getting this? Click the correct answer from the options.

Which of the following is the correct algorithm to merge two sorted linked lists?

A. Create a new list and insert elements from both lists in sorted order B. Traverse one list and insert elements from the other list at the appropriate positions C. Create a new list and append elements from both lists D. Merge the two lists by inserting elements at the end of the first list

Click the option that best answers the question.

To delete a node from a linked list, we need to update the pointers of the previous and next nodes to bypass the node to be deleted.

Here's the C++ code to delete a node from a linked list:

SNIPPET

1#include <iostream>
2using namespace std;
3
4// Linked List Node
5struct Node {
6  int data;
7  Node* next;
8  Node(int d) : data(d), next(nullptr) {}
9};
10
11// Function to delete a node from a linked list
12void deleteNode(Node* node) {
13  if (node == nullptr || node->next == nullptr) {
14    return;
15  }
16
17  Node* nextNode = node->next;
18  node->data = nextNode->data;
19  node->next = nextNode->next;
20  delete nextNode;
21}
22
23int main() {
24  // Create a linked list
25  Node* head = newNode(1);
26  head->next = newNode(2);
27  head->next->next = newNode(3);
28  head->next->next->next = newNode(4);
29
30  // Delete a node
31  deleteNode(head->next->next);
32
33  // Print the modified linked list
34  Node* current = head;
35  while (current != nullptr) {
36    cout << current->data << " ";
37    current = current->next;
38  }
39
40  return 0;
41}

In this code, we first check if the node to be deleted is nullptr or its next node is nullptr. If either of these conditions is true, we return from the function since it is not possible to delete the node.

Next, we create a pointer nextNode and assign it the value of the next node of the node to be deleted. Then, we update the data of the current node with the data of the next node, and update the next pointer of the current node to point to the next node of the next node. Finally, we delete the memory allocated for the next node.

Let's test this code with a sample linked list and delete a node from it.

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};
​
// Function to delete a node from a linked list
void deleteNode(Node* node) {
  if (node == nullptr || node->next == nullptr) {
    return;
  }
​
  Node* nextNode = node->next;
  node->data = nextNode->data;
  node->next = nextNode->next;
  delete nextNode;
}
​
int main() {
  // Create a linked list
  Node* head = new Node(1);
  head->next = new Node(2);
  head->next->next = new Node(3);
  head->next->next->next = new Node(4);
​

Are you sure you're getting this? Is this statement true or false?

Deleting a node from a linked list involves updating the pointers of the previous and next nodes to bypass the node to be deleted.

Press true if you believe the statement is correct, or false otherwise.

To find the middle element of a linked list, we can use the slow and fast pointer approach. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

Here's an example C++ code to find the middle element of a linked list:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Linked List Node
5struct Node {
6  int data;
7  Node* next;
8  Node(int d) : data(d), next(nullptr) {}
9};
10
11// Function to find the middle element of a linked list
12Node* findMiddle(Node* head) {
13  if (head == nullptr) {
14    return nullptr;
15  }
16
17  Node* slow = head;
18  Node* fast = head;
19
20  while (fast != nullptr && fast->next != nullptr) {
21    slow = slow->next;
22    fast = fast->next->next;
23  }
24
25  return slow;
26}
27
28int main() {
29  // Create a linked list
30  Node* head = new Node(1);
31  head->next = new Node(2);
32  head->next->next = new Node(3);
33  head->next->next->next = new Node(4);
34  head->next->next->next->next = new Node(5);
35
36  // Find the middle element
37  Node* middle = findMiddle(head);
38
39  if (middle != nullptr) {
40    cout << "The middle element is: " << middle->data << endl;
41  } else {
42    cout << "The list is empty." << endl;
43  }
44
45  return 0;
46}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Linked List Node
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};
​
// Function to find the middle element of a linked list
Node* findMiddle(Node* head) {
  if (head == nullptr) {
    return nullptr;
  }
​
  Node* slow = head;
  Node* fast = head;
​
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
  }
​
  return slow;
}
​
int main() {
  // Create a linked list

Build your intuition. Fill in the missing part by typing it in.

To find the middle element of a linked list, we can use the ___ approach. The slow pointer moves ____ node at a time, while the fast pointer moves ____ nodes at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

Write the missing line below.

To sort a linked list, we can use various sorting algorithms such as merge sort, bubble sort, or insertion sort. Here, we will implement merge sort to sort a linked list.

The merge sort algorithm for sorting a linked list can be divided into three steps:

Divide: Divide the linked list into two halves using the fast and slow pointer technique.
Conquer: Recursively sort the two halves of the linked list using merge sort.
Merge: Merge the two sorted halves of the linked list into a single sorted list using a merge function.

Let's take a look at an example implementation of merge sort for a linked list in C++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Node definition
5struct Node {
6  int data;
7  Node* next;
8  Node(int d) : data(d), next(nullptr) {}
9};
10
11// Function to insert a new node at the beginning of the list
12void insertAtBeginning(Node** head, int value) {
13  Node* newNode = new Node(value);
14  newNode->next = *head;
15  *head = newNode;
16}
17
18// Function to print the linked list
19void printList(Node* head) {
20  Node* temp = head;
21  while (temp != nullptr) {
22    cout << temp->data << " ";
23    temp = temp->next;
24  }
25}
26
27int main() {
28  // Create a linked list
29  Node* head = nullptr;
30  insertAtBeginning(&head, 5);
31  insertAtBeginning(&head, 10);
32  insertAtBeginning(&head, 3);
33  insertAtBeginning(&head, 8);
34
35  // Print the linked list
36  cout << "Linked List: ";
37  printList(head);
38
39  return 0;
40}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Node definition
struct Node {
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};
​
// Function to insert a new node at the beginning of the list
void insertAtBeginning(Node** head, int value) {
  Node* newNode = new Node(value);
  newNode->next = *head;
  *head = newNode;
}
​
// Function to print the linked list
void printList(Node* head) {
  Node* temp = head;
  while (temp != nullptr) {
    cout << temp->data << " ";
    temp = temp->next;
  }
}
​
int main() {
  // Create a linked list
  Node* head = nullptr;

Build your intuition. Click the correct answer from the options.

Which sorting algorithm can be used to sort a linked list efficiently?

Click the option that best answers the question.

Bubble Sort
Merge Sort
Insertion Sort
Quick Sort

Generating complete for this lesson!

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Let's test your knowledge. Fill in the missing part by typing it in.

Let's test your knowledge. Is this statement true or false?

Build your intuition. Click the correct answer from the options.

Click the option that best answers the question.

Are you sure you're getting this? Is this statement true or false?

Build your intuition. Click the correct answer from the options.

Click the option that best answers the question.

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Are you sure you're getting this? Is this statement true or false?

Build your intuition. Fill in the missing part by typing it in.

Build your intuition. Click the correct answer from the options.

Click the option that best answers the question.

Programming Categories

Popular Lessons