A linked list is a linear data structure and plays important role in data structures and algorithms in which the elements are not stored in consecutive memory locations. Instead, a linked list's components are connected using pointers, as shown in the image below:
 |
| Linked List |
Here is an Example of a Singly Linked List Implementation in C++:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = nullptr;
}
void add(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
void print() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
list.add(5);
list.add(3);
list.add(9);
list.print();
return 0;
}
This implementation defines two classes: Node and LinkedList. Node represents a node in the linked list, and LinkedList represents the list itself. The Node class has two member variables: data, which stores the value associated with the node, and next, which points to the next node in the list.
The 'LinkedList' class has one member variable: head, which points to the first node in the list. The add method adds a new node to the end of the list, and the print method prints out the list's contents.
In the 'main' function, we create a new 'LinkedList' object, add three nodes to it, and print out the contents of the list.
Singly Linked List implementation in C++, With Additional Methods for Inserting and Deleting Nodes:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = nullptr;
}
// Add a new node to the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
// Insert a new node at the given position
void insert(int data, int position) {
Node* newNode = new Node(data);
if (position == 0) {
newNode->next = head;
head = newNode;
} else {
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; i++) {
current = current->next;
}
if (current != nullptr) {
newNode->next = current->next;
current->next = newNode;
}
}
}
// Delete the node at the given position
void remove(int position) {
if (head == nullptr) {
return;
}
if (position == 0) {
Node* temp = head;
head = head->next;
delete temp;
} else {
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; i++) {
current = current->next;
}
if (current != nullptr && current->next != nullptr) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
}
// Get the value of the node at the given position
int get(int position) {
Node* current = head;
for (int i = 0; i < position && current != nullptr; i++) {
current = current->next;
}
if (current != nullptr) {
return current->data;
} else {
return -1; // Return -1 to indicate an invalid position
}
}
// Print the contents of the list
void print() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
list.append(5);
list.append(3);
list.append(9);
list.print();
list.insert(7, 1);
list.print();
list.remove(2);
list.print();
std::cout << list.get(1) << std::endl;
return 0;
}
This implementation includes four additional methods:
append: Adds a new node to the end of the list
insert: Inserts a new node at the given position
remove: Deletes the node at the given position
get: Returns the value of the node at the given position
In the main function, we create a new LinkedList object, add three nodes to it using append, print out the contents of the list, insert a new node at position 1 using insert, print the contents of the list again, delete the node at position 2 using remove, print the contents of the list again, and finally print the value of the node at position 1 using get.
This implementation uses a for loop to traverse the list when inserting, deleting, or getting the value of a node at a specific position. It also checks for invalid positions and handles them by returning -1 for get or doing nothing for insert and remove.
Note that this implementation is for a singly linked list, where each node has a pointer to the next node but not to the previous node. If you need a doubly linked list, where each node has pointers to both the next and previous nodes, you would need to modify this implementation accordingly.
Here's an Example of a Doubly Linked List Implementation in C++:
#include <iostream>
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int data) {
this->data = data;
this->prev = nullptr;
this->next = nullptr;
}
};
class LinkedList {
private:
Node* head;
Node* tail;
public:
LinkedList() {
head = nullptr;
tail = nullptr;
}
// Add a new node to the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
// Insert a new node at the given position
void insert(int data, int position) {
Node* newNode = new Node(data);
if (position == 0) {
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
} else {
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; i++) {
current = current->next;
}
if (current != nullptr) {
newNode->prev = current;
newNode->next = current->next;
if (current->next != nullptr) {
current->next->prev = newNode;
} else {
tail = newNode;
}
current->next = newNode;
}
}
}
// Delete the node at the given position
void remove(int position) {
if (head == nullptr) {
return;
}
if (position == 0) {
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
} else {
tail = nullptr;
}
delete temp;
} else {
Node* current = head;
for (int i = 0; i < position && current != nullptr; i++) {
current = current->next;
}
if (current != nullptr) {
current->prev->next = current->next;
if (current->next != nullptr) {
current->next->prev = current->prev;
} else {
tail = current->prev;
}
delete current;
}
}
}
// Get the value of the node at the given position
int get(int position) {
Node* current = head;
for (int i = 0; i < position && current != nullptr; i++) {
current = current->next;
}
if (current != nullptr) {
return current->data;
} else {
return -1; // Return -1 to indicate an invalid position
}
}
// Print the contents of the list
void print() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
list.append(5);
list.append(3);
list.append(9);
list.print();
list.insert(7, 1);
list.print();
list.remove(2);
list.print();
std::cout << list.get(1) << std::endl;
return 0;
This implementation is similar to the singly linked list implementation, but each node has pointers to both the previous and next nodes. The `append` function adds a new node to the end of the list, and the `insert` function inserts a new node at the given position. The `remove` function deletes the node at the given position, and the `get` function returns the value of the node at the given position.
Note that this implementation still checks for invalid positions and handles them by returning -1 for `get` or doing nothing for `insert` and `remove`.
Also note that in this implementation, we have to be careful to update the prev and next pointers correctly when inserting or removing a node, since we need to maintain the doubly linked structure of the list.
Here's an Example Usage of the Doubly Linked List Implementation:
int main() {
LinkedList list;
list.append(5);
list.append(3);
list.append(9);
list.print();
list.insert(7, 1);
list.print();
list.remove(2);
list.print();
std::cout << list.get(1) << std::endl;
return 0;
}
This code creates a new doubly linked list, appends three nodes to it with values 5, 3, and 9, and then prints the contents of the list. It then inserts a new node with value 7 at position 1, prints the contents of the list again, removes the node at position 2, prints the contents of the list again, gets the value of the node at position 1 and prints it, and finally exits. The output of this program should be:
5 3 9
5 7 3 9
5 7 9
7
Finally, it's worth noting that there are many variations and extensions of linked lists that can be used to solve different problems. For example, a circular linked list is a variation of a linked list where the last node points back to the first node, forming a loop. This can be useful in some situations where we want to iterate over a list indefinitely.
Another example is a doubly linked circular list, which is a combination of the doubly linked list and the circular linked list. This can be useful in situations where we want to iterate over a list both forwards and backwards indefinitely.
Linked lists can also be used to implement other data structures and algorithms, such as stacks and queues. In a stack, elements are added and removed from the top of the list, while in a queue, elements are added to the back and removed from the front of the list. By using a linked list to implement these data structures, we can easily add and remove elements from the appropriate end of the list in constant time.
In summary, linked lists are a fundamental data structure in computer science and are used extensively in many applications. They provide a flexible and efficient way to store and manipulate collections of data, and can be extended in many ways to suit different needs.
0 Comments