AlgoDaily - Linked Lists

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

In a linked list, each element is called a node. Each node consists of two parts: the data and a reference (also called a pointer) to the next node.

Here's an example of a simple linked list implemented using C++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4int main() {
5  // Linked List implementation
6
7  // Node structure
8  struct Node {
9    int data;
10    Node* next;
11  };
12
13  // Create nodes
14  Node* node1 = new Node;
15  Node* node2 = new Node;
16  Node* node3 = new Node;
17
18  // Assign data values
19  node1->data = 1;
20  node2->data = 2;
21  node3->data = 3;
22
23  // Connect nodes
24  node1->next = node2;
25  node2->next = node3;
26  node3->next = nullptr;
27
28  // Traversal
29  Node* current = node1;
30  while (current != nullptr) {
31    cout << current->data << ' ';
32    current = current->next;
33  }
34
35  return 0;
36}

In this example, the linked list contains three nodes: node1, node2, and node3. Each node is assigned a data value (1, 2, or 3) and a reference to the next node. The nullptr value indicates the end of the list.

To traverse the linked list, we start from the first node (node1) and print the data value. Then, we move to the next node using the reference (next) until we reach the end of the list.

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
int main() {
  // Linked List implementation
​
  // Node structure
  struct Node {
    int data;
    Node* next;
  };
​
  // Create nodes
  Node* node1 = new Node;
  Node* node2 = new Node;
  Node* node3 = new Node;
​
  // Assign data values
  node1->data = 1;
  node2->data = 2;
  node3->data = 3;
​
  // Connect nodes
  node1->next = node2;
  node2->next = node3;
  node3->next = nullptr;
​
  // Traversal
  Node* current = node1;

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

In a linked list, each element is called a __. Each node consists of two parts: the data and a reference (also called a pointer) to the next node.

Write the missing line below.

To implement a singly linked list in C++, we first define a Node class that represents each individual node in the linked list. The Node class contains two members: data, which stores the value of the node, and next, which is a pointer to the next node in the list.

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4class Node {
5public:
6    int data;
7    Node* next;
8
9    Node(int data) {
10        this->data = data;
11        next = nullptr;
12    }
13};

Next, we define a SinglyLinkedList class that contains a pointer to the head of the linked list. The SinglyLinkedList class provides methods for inserting nodes into the list and printing the list.

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4class SinglyLinkedList {
5public:
6    Node* head;
7
8    SinglyLinkedList() {
9        head = nullptr;
10    }
11
12    void insert(int data) {
13        Node* newNode = new Node(data);
14        if (head == nullptr) {
15            head = newNode;
16        } else {
17            Node* current = head;
18            while (current->next != nullptr) {
19                current = current->next;
20            }
21            current->next = newNode;
22        }
23    }
24
25    void printList() {
26        Node* current = head;
27        while (current != nullptr) {
28            cout << current->data << " ";
29            current = current->next;
30        }
31    }
32};

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
class Node {
public:
    int data;
    Node* next;
​
    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};
​
class SinglyLinkedList {
public:
    Node* head;
​
    SinglyLinkedList() {
        head = nullptr;
    }
​
    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {

Build your intuition. Is this statement true or false?

True or false swipe question for implementing a singly linked list: A singlly linked list contains a pointer to the previous node.

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

To add a new node to the linked list, follow these steps:

Create a new node with the desired data.
If the list is empty, make the new node the head of the list.
Otherwise, traverse the list to find the last node.
Insert the new node at the end of the list by setting the next pointer of the last node to point to the new node.

Here's an example of adding a new node to a singly linked list in C++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4class Node {
5public:
6    int data;
7    Node* next;
8
9    Node(int data) {
10        this->data = data;
11        next = nullptr;
12    }
13};
14
15int main() {
16  // Create the head of the list
17  Node* head = new Node(1);
18
19  // Add a new node
20  Node* newNode = new Node(2);
21
22  // Traverse the list to find the last node
23  Node* current = head;
24  while (current->next != nullptr) {
25    current = current->next;
26  }
27
28  // Insert the new node at the end of the list
29  current->next = newNode;
30
31  // Optional: Display the updated list
32  current = head;
33  while (current != nullptr) {
34    cout << current->data << " ";
35    current = current->next;
36  }
37
38  return 0;
39}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
int main() {
  // Create a new node
  Node* newNode = new Node(data);
​
  // If the list is empty, make the new node the head
  if (head == nullptr) {
    head = newNode;
  }
  // Otherwise, traverse the list to find the last node
  else {
    Node* current = head;
    while (current->next != nullptr) {
      current = current->next;
    }
    // Insert the new node at the end of the list
    current->next = newNode;
  }
​
  // Optional: Display the updated list
  Node* current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }
​
  return 0;

Build your intuition. Is this statement true or false?

Adding a new node to a linked list involves creating a new node with the desired data. This node becomes the head of the list if the list is empty. If the list is not empty, the new node is inserted at the end of the list by setting the next pointer of the last node to point to the new node.

Solution: true

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

To search for a specific value in a linked list, you can traverse the list and compare each node's data with the target value. Here's an example of how to search for a value in a singly linked list using C++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4class Node {
5public:
6    int data;
7    Node* next;
8
9    Node(int data) {
10        this->data = data;
11        next = nullptr;
12    }
13};
14
15// Function to search for a value in a linked list
16bool searchLinkedList(Node* head, int value) {
17    Node* current = head;
18    while (current != nullptr) {
19        if (current->data == value) {
20            return true;
21        }
22        current = current->next;
23    }
24    return false;
25}
26
27int main() {
28    // Create the head of the list
29    Node* head = new Node(1);
30
31    // Add nodes to the list
32    Node* node1 = new Node(2);
33    head->next = node1;
34    Node* node2 = new Node(3);
35    node1->next = node2;
36    Node* node3 = new Node(4);
37    node2->next = node3;
38    Node* node4 = new Node(5);
39    node3->next = node4;
40
41    // Search for a value in the list
42    int value = 3;
43    bool found = searchLinkedList(head, value);
44    if (found) {
45        cout << "Value " << value << " found in the linked list" << endl;
46    } else {
47        cout << "Value " << value << " not found in the linked list" << endl;
48    }
49
50    return 0;
51}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
class Node {
public:
    int data;
    Node* next;
​
    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};
​
// Function to search for a value in a linked list
bool searchLinkedList(Node* head, int value) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}
​
int main() {
    // Create the head of the list
    Node* head = new Node(1);

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

Searching a linked list involves traversing the list and comparing each node's data with the target value.

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

To delete a node from a linked list, you need to find the node with the value you want to delete and update the links to remove it from the list. The code snippet below demonstrates how to delete a node from a linked list in C++:

TEXT/X-C++SRC

1// Node class
2class Node {
3public:
4    int data;
5    Node* next;
6
7    Node(int data) {
8        this->data = data;
9        next = nullptr;
10    }
11};
12
13// Linked list class
14class LinkedList {
15public:
16    Node* head;
17
18    LinkedList() {
19        head = nullptr;
20    }
21
22    // Function to insert a node at the end
23    void insert(int data) {
24        Node* newNode = new Node(data);
25        if (head == nullptr) {
26            head = newNode;
27        } else {
28            Node* current = head;
29            while (current->next != nullptr) {
30                current = current->next;
31            }
32            current->next = newNode;
33        }
34    }
35
36    // Function to delete a node from the linked list
37    void deleteNode(int value) {
38        Node* current = head;
39        Node* previous = nullptr;
40
41        // Iterate through the list to find the node to delete
42        while (current != nullptr) {
43            if (current->data == value) {
44                // If the node to delete is the head
45                if (current == head) {
46                    head = current->next;
47                } else {
48                    previous->next = current->next;
49                }
50                delete current;
51                return;
52            }
53
54            previous = current;
55            current = current->next;
56        }
57
58        cout << "Node with value " << value << " not found" << endl;
59    }
60
61    // Function to print the linked list
62    void printList() {
63        Node* current = head;
64        while (current != nullptr) {
65            cout << current->data << " ";
66            current = current->next;
67        }
68        cout << endl;
69    }
70};
71
72int main() {
73    LinkedList list;
74
75    // Insert nodes
76    list.insert(1);
77    list.insert(2);
78    list.insert(3);
79    list.insert(4);
80
81    // Print initial list
82    cout << "Initial List: ";
83    list.printList();
84
85    // Delete a node
86    int value = 3;
87    cout << "Deleting Node with value " << value << "..." << endl;
88    list.deleteNode(value);
89
90    // Print updated list
91    cout << "Updated List: ";
92    list.printList();
93
94    return 0;
95}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Node class
class Node {
public:
    int data;
    Node* next;
​
    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};
​
// Linked list class
class LinkedList {
public:
    Node* head;
​
    LinkedList() {
        head = nullptr;
    }
​
    // Function to insert a node at the end
    void insert(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;

Build your intuition. Is this statement true or false?

Deleting a node from a linked list requires finding the node with the value you want to delete and updating the links to remove it from the list.

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

To reverse a linked list, you need to update the links between the nodes. The basic idea is to traverse the list while changing the next pointers to reverse the links.

Here is the C++ code to reverse a linked list:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Function to reverse a linked list
5void reverseList(Node* &head) {
6    Node* current = head;
7    Node* prev = nullptr;
8    Node* next = nullptr;
9
10    while (current != nullptr) {
11        next = current->next;
12        current->next = prev;
13        prev = current;
14        current = next;
15    }
16
17    head = prev;
18}
19
20int main() {
21    // Linked list nodes
22    Node* head = new Node(1);
23    Node* second = new Node(2);
24    Node* third = new Node(3);
25    Node* fourth = new Node(4);
26
27    // Connect nodes
28    head->next = second;
29    second->next = third;
30    third->next = fourth;
31
32    cout << "Original List: ";
33    printList(head);
34
35    // Reverse the list
36    reverseList(head);
37
38    cout << "Reversed List: ";
39    printList(head);
40
41    return 0;
42}

Let's go through the code step by step:

The function reverseList takes a reference to the head of the linked list as a parameter.
Inside the function, we define three pointers: current, prev, and next.
We initialize current with the head of the linked list and prev and next with nullptr.
We then iterate through the list using a while loop until current becomes nullptr.
Inside the loop, we first store the next node in the next pointer.
Then, we update the next pointer of the current node to point to the previous node.
After that, we update prev to be the current node and current to be the next node.
Once the loop ends, we update the head of the linked list to be the last node we reached (previously prev).
Finally, we print the original and reversed lists using the printList function.

The time complexity of this algorithm is O(n) as we need to traverse the entire list once to reverse it.

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Function to reverse a linked list
void reverseList(Node* &head) {
    Node* current = head;
    Node* prev = nullptr;
    Node* next = nullptr;
​
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
​
    head = prev;
}
​
int main() {
    // Linked list nodes
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);
​
    // Connect nodes
    head->next = second;
    second->next = third;

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

Reversing a linked list can be done by reversing the order of the nodes.

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

To detect whether a linked list contains a cycle, we can use the Floyd's Cycle Detection Algorithm. This algorithm makes use of two pointers, a slow pointer and a fast pointer, to traverse the linked list.

Here is the C++ code to detect a cycle in a linked list:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Function to detect a cycle in a linked list
5bool hasCycle(ListNode *head) {
6    if (head == nullptr || head->next == nullptr) {
7        return false;
8    }
9
10    ListNode *slow = head;
11    ListNode *fast = head;
12
13    while (fast != nullptr && fast->next != nullptr) {
14        slow = slow->next;
15        fast = fast->next->next;
16
17        if (slow == fast) {
18            return true;
19        }
20    }
21
22    return false;
23}
24
25int main() {
26
27    // Create a linked list with a cycle
28    ListNode *head = new ListNode(1);
29    ListNode *second = new ListNode(2);
30    ListNode *third = new ListNode(3);
31    ListNode *fourth = new ListNode(4);
32
33    head->next = second;
34    second->next = third;
35    third->next = fourth;
36    fourth->next = second; // cycle
37
38    if (hasCycle(head)) {
39        cout << "The linked list contains a cycle." << endl;
40    } else {
41        cout << "The linked list does not contain a cycle." << endl;
42    }
43
44    return 0;
45}

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
// Function to detect a cycle in a linked list
bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }
​
    ListNode *slow = head;
    ListNode *fast = head;
​
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
​
        if (slow == fast) {
            return true;
        }
    }
​
    return false;
}
​
int main() {
​
    // Create a linked list with a cycle
    ListNode *head = new ListNode(1);
    ListNode *second = new ListNode(2);

Try this exercise. Click the correct answer from the options.

Which algorithm can be used to detect whether a linked list contains a cycle?

Click the option that best answers the question.

Breadth-First Search
Depth-First Search
Floyd's Cycle Detection Algorithm
Merge Sort

Generating complete for this lesson!

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

Build your intuition. Is this statement true or false?

Build your intuition. Is this statement true or false?

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

Build your intuition. Is this statement true or false?

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

Try this exercise. Click the correct answer from the options.

Click the option that best answers the question.

Programming Categories

Popular Lessons