Singly Linked List
In computer science and programming, a singly linked list is a basic data structure. It is a kind of linked list where each node, or element, has a value and a reference (or link) to the node after it in the list. This sequential nature enables effective element insertion, deletion, and traversal.
How to Create a Node in Singly Linked List?
To create a node in Singly Linked List we will use Class in C++. First we define a Class like so:
class Node {
public:
int data;
Node* link;
};Here we have defined a class called Node with two members: an integer data and a pointer link of type Node. This class represents a node in a singly linked list. The data member stores the value of the node, while the link member points to the next node in the sequence.
The next step is to insert data in the node we just created.
How to Insert Data in a Node in Singly Linked List?
To insert data in a node, and subsequently increase the number of nodes as we keep inserting data, we create a function called Create.
void create(int n) {
Node* newNode = new Node();
newNode->data = n;
newNode->link = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->link != nullptr) {
temp = temp->link;
}
temp->link = newNode;
}
}Here, a new node is created and its data member is set to the value n. The link member is initialized as nullptr, indicating that it is the last node in the list.
If the linked list is empty (i.e., head is nullptr), the newly created node becomes the head of the list.
If the linked list already has nodes, a temporary pointer temp is initialized with the address of the head node. A loop is then used to traverse the list until the last node is reached (i.e., the link of the current node is nullptr). Inside the loop, the temp pointer is updated to the next node in each iteration.
Once the loop reaches the last node, the link member of the last node is set to the newly created node, effectively connecting it at the end of the list.
Now we display the list we created.
How to Display Singly Linked List?
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->link;
}
cout << endl;
}The display function traverses the linked list and prints the data values of each node.
The function begins by initializing a temporary pointer temp with the address of the head node.
Inside the while loop, the function iterates over the linked list as long as the temp pointer is not nullptr, indicating that there are more nodes to process. Within each iteration, the value (data) of the current node is printed using cout. The temp pointer is then updated to point to the next node in the list by assigning the value of its link member.
Once the loop reaches the end of the list (i.e., temp becomes nullptr), the loop exits, and a newline character is printed using cout to separate the output from other text in the console.
Full implementation-
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* link;
};
Node* head = nullptr;
void create(int n) {
Node* newNode = new Node();
newNode->data = n;
newNode->link = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->link != nullptr) {
temp = temp->link;
}
temp->link = newNode;
}
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->link;
}
cout << endl;
}
int main() {
create(5);
create(6);
create(7);
create(8);
cout << "The linked list is: ";
display();
return 0;
}Output:
the linked list is:5 6 7 8 We can also allow users to create a linked list by taking inputs from them.
The code is as follows:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* link;
};
Node* head = nullptr;
void create(int n) {
Node* newNode = new Node();
newNode->data = n;
newNode->link = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->link != nullptr) {
temp = temp->link;
}
temp->link = newNode;
}
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->link;
}
cout << endl;
}
int main() {
int num;
char choice;
cout << "Enter values for the linked list. Press enter after each value. Press 'q' and enter to finish: " << endl;
while (cin >> num) {
create(num);
}
cout << "The linked list is: ";
display();
return 0;
}
Output:
Enter values for the linked list. Press enter after each value. Press 'q' and enter to finish:
2
3
4
5
q
The linked list is: 2 3 4 5
Delete Any Value From Singly Linked List:
Here's how we can delete any value from the linked list-
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* link;
};
Node* head = nullptr;
void create(int n) {
Node* newNode = new Node();
newNode->data = n;
newNode->link = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->link != nullptr) {
temp = temp->link;
}
temp->link = newNode;
}
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->link;
}
cout << endl;
}
void deleteNode(int value) {
if (head == nullptr) {
cout << "Linked list is empty. No nodes to delete." << endl;
return;
}
if (head->data == value) {
Node* temp = head;
head = head->link;
delete temp;
cout << "Node with value " << value << " deleted from the linked list." << endl;
return;
}
Node* prev = nullptr;
Node* current = head;
while (current != nullptr && current->data != value) {
prev = current;
current = current->link;
}
if (current == nullptr) {
cout << "Node with value " << value << " not found in the linked list." << endl;
return;
}
prev->link = current->link;
delete current;
cout << "Node with value " << value << " deleted from the linked list." << endl;
}
int main() {
create(5);
create(6);
create(7);
create(8);
cout << "Initial linked list: ";
display();
int value;
cout << "Enter the value of the node to delete: ";
cin >> value;
deleteNode(value);
cout << "Linked list after deletion: ";
display();
return 0;
}