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++:
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
}
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;
Are you sure you're getting this? 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.
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.
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
}
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) {
Are you sure you're getting this? 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++:
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
}
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++:
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
}
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);
Try this exercise. 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++:
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
}
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:
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
, andnext
. - We initialize
current
with the head of the linked list andprev
andnext
withnullptr
. - We then iterate through the list using a while loop until
current
becomesnullptr
. - 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 andcurrent
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
}
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;
Try this exercise. 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:
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
}
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);
Are you sure you're getting this? 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!