What is a linked list?
A linked list is a linear data structure that consists of a sequence of nodes, where each node stores a piece of data and a reference (pointer) to the next node in the List. Linked lists are useful for storing data collections when the collection size is not known in advance or when the data is frequently inserted or deleted.
In C++, we can create a linked list by defining a node class and a linked list class. The node class will represent a single node in the List and contain a data field and a pointer to the next node. The linked list class will contain a head pointer to the first node in the List and various methods for inserting, deleting, and traversing the nodes in 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 has a public data field data of type int and a public pointer next to the next node in the List. It also has a constructor that initializes the data field and sets the nexcpp tutorialer to nullptr.
Here is an example of how to use the node and linked list classes to create and manipulate 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 has a private field head thacpp tutorials to the first node in the List and various public methods for inserting and deleting nodes at the beginning and end of the List and for printing the List to the console. This program will create a linked list, insert some nodes at the beginning and end of the List, delete a node at the beginning and end of the List, and print the List to the console.
Here is an example of how to create a linked list in C++ using 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 above code, we have defined a template class Node that represents a single node in a linked list. The Node class has a public data field data of type T (where T is a template parameter) and a public pointer next to the next node in the List. It also has a constructor that initializes the data field and sets the nexcpp tutorialer to nullptr.
We have also defined a template class, LinkedList, that represents a linked list and contains a private field head thacpp tutorials to the first node in the List. The LinkedList class has various public methods for inserting and deleting nodes at the beginning and end of the List and for printing the List to the console.
The insertAtBeginning method creates a new node with the given data and inserts it at the beginning of the List by updating the head pointer. The insertAtEnd method creates a new node with the given data and inserts it at the end of the List by traversing it and updating the last node's nexcpp tutorialer. The deleteAtBeginning method deletes the first node in the List by updating the head pointer and freeing up the memory used by the node. The deleteAtEnd method deletes the last node in the List by traversing the List and updating the nexcpp tutorialer of the second to the last node. The printList method traverses the List and prints the data of each node to the console.
In the main function, we create an instance of the LinkedList class and call the various methods to insert and delete nodes and print the List. The output shows the original List, the List after deleting a node at the beginning, and the List after deleting a node at the end.