What is a linked list?
A linked list represents a sequential arrangement of nodes, with each node holding a data element and a pointer to the subsequent node in the list. These lists are beneficial for managing data sets of unknown size or when there is a need for frequent data insertion or removal operations.
In C++, we have the capability to establish a linked list through the creation of a node class and a linked list class. The node class is responsible for defining an individual node within the List, encompassing a data attribute and a reference to the subsequent node. On the other hand, the linked list class will feature a head pointer pointing to the initial node in the List, along with multiple functions for adding, removing, and navigating through the nodes within the List.
Here is an example of a node class in C++:
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
This node class contains a public data field named data which is an integer type, and a public pointer named next pointing to the subsequent node in the List. Additionally, it includes a constructor that assigns an initial value to the data field and configures the next pointer to point to nullptr.
Here is a demonstration of employing the node and linked list classes to establish and control a linked list in C++:
#include <iostream>
using namespace std;
// Node class
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// Linked list class
class LinkedList {
private:
Node *head;
public:
LinkedList() {
this->head = nullptr;
}
void insertAtBeginning(int data) {
Node *newNode = new Node(data);
newNode->next = head;
head = newNode;
}
void insertAtEnd(int data) {
Node *newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node *temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteAtBeginning() {
if (head == nullptr) {
return;
}
Node *temp = head;
head = head->next;
delete temp;
}
void deleteAtEnd() {
if (head == nullptr) {
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node *temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
void printList() {
Node *temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
// Create a linked list
LinkedList List;
// Insert some nodes at the beginning of the list
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
// Insert some nodes at the end of the list
list.insertAtEnd(4);
list.insertAtEnd(5);
list.insertAtEnd(6);
// Print the list
cout << "Original list: ";
list.printList();
// Delete a node at the beginning of the list
list.deleteAtBeginning();
// Print the List again
cout << "List after deleting a node at the beginning: ";
list.printList();
// Delete a node at the end of the list
list.deleteAtEnd();
// Print the List again
cout << "List after deleting a node at the end: ";
list.printList();
return 0;
}
Output:
Explanation:
This linked list class contains a private field named head that points to the initial node in the List. It also includes several public functions for adding and removing nodes at the start and end of the List, as well as for displaying the List on the screen. The application will generate a linked list, add nodes at both the start and end, remove a node from both ends, and display the List on the console.
Here is a sample illustrating the creation of a linked list in C++ employing a template class:
#include <iostream>
template <typename T>
class Node {
public:
T data;
Node *next;
Node(T data) {
this->data = data;
this->next = nullptr;
}
};
template <typename T>
class LinkedList {
private:
Node<T> *head;
public:
LinkedList() {
this->head = nullptr;
}
void insertAtBeginning(T data) {
Node<T> *newNode = new Node<T>(data);
newNode->next = head;
head = newNode;
}
void insertAtEnd(T data) {
Node<T> *newNode = new Node<T>(data);
if (head == nullptr) {
head = newNode;
return;
}
Node<T> *temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteAtBeginning() {
if (head == nullptr) {
return;
}
Node<T> *temp = head;
head = head->next;
delete temp;
}
void deleteAtEnd() {
if (head == nullptr) {
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node<T> *temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
void printList() {
Node<T> *temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
};
int main() {
// Create a linked list
LinkedList<int> list;
// Insert some nodes at the beginning of the list
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
// Insert some nodes at the end of the list
list.insertAtEnd(4);
list.insertAtEnd(5);
list.insertAtEnd(6);
// Print the list
std::cout << "Original list: ";
list.printList();
// Delete a node at the beginning
// Delete a node at the beginning of the list
list.deleteAtBeginning();
// Print the List again
std::cout << "List after deleting a node at the beginning: ";
list.printList();
// Delete a node at the end of the list
list.deleteAtEnd();
// Print the List again
std::cout << "List after deleting a node at the end: ";
list.printList();
return 0;
}
Output:
Explanation:
In the preceding code snippet, a template class Node is declared to signify an individual node within a linked list. This Node class includes a public data attribute named data of type T (with T as a template parameter) and a public pointer named next pointing to the subsequent node in the List. Additionally, it contains a constructor responsible for initializing the data field and assigning the next pointer to nullptr.
We've established a template class named LinkedList, which serves as a representation of a linked list and holds a private attribute, head, pointing to the initial node in the List. Within the LinkedList class, there are multiple public functions for adding and removing nodes at both the start and end of the List, as well as for displaying the List on the console.
The addAtStart function generates a fresh node containing the specified data and adds it to the beginning of the List, thereby adjusting the head pointer. The addAtEnd function establishes a new node with the provided data and appends it to the end of the List by navigating through it and updating the nexcpp tutorialer of the last node. The removeFromStart function eliminates the initial node in the List by updating the head pointer and releasing the memory allocated to the node. The removeFromEnd function eradicates the final node in the List by traversing the List and updating the nexcpp tutorialer of the second-to-last node. The displayList function navigates through the List and displays the data of each node on the console.
In the primary function, we instantiate the LinkedList class and invoke different functions to add and remove nodes, as well as display the List. The result displays the initial List, the List after removing a node at the start, and the List after removing a node at the conclusion.
