Linked List with C++
A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a pointer to the next node in the sequence. Linked lists are commonly used in computer programming to implement dynamic data structures.
Linked List Node
To implement a linked list in C++, we first define a struct to represent a node:
1
2
3
4
struct Node {
int data;
Node* next;
};
The Node
struct has two members: data
, which stores the value of the node, and next
, which stores a pointer to the next node in the sequence.
Linked List Class
We can then define a class to represent a linked list:
1
2
3
4
5
6
7
8
9
class LinkedList {
private:
Node* head;
public:
LinkedList();
void insert(int data);
void remove(int data);
void display();
};
The LinkedList
class has a private member head
, which stores a pointer to the first node in the sequence. The class also has three public member functions:
insert(int data)
: Inserts a new node with the given data at the end of the linked list.remove(int data)
: Removes the first node in the sequence with the given data.display()
: Displays the values of all nodes in the sequence.
We can implement these member functions as follows:
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
LinkedList::LinkedList() {
head = nullptr;
}
void LinkedList::insert(int data) {
Node* new_node = new Node;
new_node->data = data;
new_node->next = nullptr;
if (head == nullptr) {
head = new_node;
} else {
Node* curr = head;
while (curr->next != nullptr) {
curr = curr->next;
}
curr->next = new_node;
}
}
void LinkedList::remove(int data) {
if (head == nullptr) {
return;
}
if (head->data == data) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* curr = head;
while (curr->next != nullptr) {
if (curr->next->data == data) {
Node* temp = curr->next;
curr->next = curr->next->next;
delete temp;
return;
}
curr = curr->next;
}
}
void LinkedList::display() {
Node* curr = head;
while (curr != nullptr) {
std::cout << curr->data << " ";
curr = curr->next;
}
std::cout << std::endl;
}
In the insert
function, we first create a new node with the given data, and set its next
pointer to nullptr
. If the linked list is empty, we set head
to the new node. Otherwise, we traverse the linked list until we reach the last node, and set its next
pointer to the new node.
In the remove
function, we first handle the case where the node to be removed is the first node in the sequence. If head
contains the data, we delete head
, set head
to head->next
, and return. Otherwise, we traverse the linked list until we find the node to be removed, delete it, and set the previous node’s next
pointer to the next node.
In the display
function, we traverse the linked list and print the value of each node.
Usage
To use the LinkedList class, we can create an instance of the class and call its member functions as needed:
1
2
3
4
5
6
7
8
9
10
int main() {
LinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.display(); // Output: 1 2 3
list.remove(2);
list.display(); // Output: 1 3
return 0;
}
In this example, we create a LinkedList
object called list
, and insert three nodes with values 1, 2, and 3. We then display the contents of the linked list using the display
function, which outputs “1 2 3”. We then remove the node with value 2 using the remove
function, and display the updated contents of the linked list, which outputs “1 3”.
Conclusion
In this article, we learned how to implement a linked list data structure in C++. Linked lists are a powerful tool for managing dynamic data, and can be used in a variety of programming applications. By understanding the basics of linked lists and how to implement them in C++, you can improve your programming skills and build more complex and efficient programs.