A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element, called a node, contains data and a pointer to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion of elements, especially when compared to arrays.
| Feature | Array-Based List | Linked List |
|---|---|---|
| Memory Allocation | Contiguous memory allocation | Dynamic memory allocation |
| Access to Elements | Direct access using index | Sequential access through pointers |
| Insertion and Deletion | Inefficient, requires shifting elements | Efficient, especially at the beginning or middle |
| Space Overhead | Fixed memory allocation | Additional memory for pointers |
| Flexibility in Size | Fixed size | Dynamic size |
| Memory Fragmentation | Can suffer from fragmentation | Less prone to fragmentation |
| Cache Efficiency | Generally more cache-friendly | Less cache-friendly due to non-contiguous memory |
#include <iostream>
struct Node {
int data; // Data stored in the node (can be any data type)
Node* next; // Pointer to the next node
// Constructor to initialize a new node
Node(int val) : data(val), next(nullptr) {} // Initialize next to null
};To manage the linked list, it's good practice to create a LinkedList class. This class will encapsulate the operations you can perform on the list.
class LinkedList {
private:
Node* head; // Pointer to the first node in the list
public:
LinkedList() : head(nullptr) {} // Constructor: initially empty list
// ... (Methods for operations like insertion, deletion, etc. will go here)
};Let's implement a method to insert a new node at the beginning of the list (often called "prepend").
void insertAtBeginning(int data) {
Node* newNode = new Node(data); // Create a new node
newNode->next = head; // Make the new node point to the current head
head = newNode; // Update head to point to the new node
}A method to print the contents of the linked list is essential for verification.
void display() {
Node* current = head; // Start from the head
while (current != nullptr) { // Traverse the list until the end
std::cout << current->data << " -> ";
current = current->next; // Move to the next node
}
std::cout << "nullptr" << std::endl; // Mark the end of the list
}Here's the complete code, combining all the parts:
#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
void insertAtBeginning(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
LinkedList myList;
myList.insertAtBeginning(10);
myList.insertAtBeginning(20);
myList.insertAtBeginning(30);
myList.display(); // Output: 30 -> 20 -> 10 -> nullptr
return 0;
}It's crucial to manage memory properly in C++. When you're finished with a linked list, you need to deallocate the memory used by the nodes to prevent memory leaks. This involves traversing the list and deleting each node. This is commonly done with a destructor in the LinkedList class. Example:
~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
head = nullptr; // Important: set head to null after deleting
}C++
#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
void insertAtBeginning(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
}
// ... (Other methods will go here)
};
int main() {
LinkedList myList;
myList.insertAtBeginning(10);
myList.insertAtBeginning(20);
myList.insertAtBeginning(30);
// ...
}
C++
void insertAfter(Node* prevNode, int data) {
if (prevNode == nullptr) {
std::cerr << "Previous node cannot be null" << std::endl;
return; // Or throw an exception
}
Node* newNode = new Node(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
C++
void insertAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) { // Empty list
head = newNode;
return;
}
Node* last = head;
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
}
C++
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
C++
Node* search(int key) {
Node* current = head;
while (current != nullptr) {
if (current->data == key) {
return current; // Found the node
}
current = current->next;
}
return nullptr; // Not found
}
C++
void reverse() {
Node* prev = nullptr;
Node* current = head;
Node* nextNode = nullptr;
while (current != nullptr) {
nextNode = current->next; // Store next node
current->next = prev; // Reverse the link
prev = current; // Move prev one step forward
current = nextNode; // Move current one step forward
}
head = prev; // Update head to the new first node
}
C++
void deleteNode(int key) {
Node* current = head;
Node* prev = nullptr;
// If head node itself holds the key
if (current != nullptr && current->data == key) {
head = current->next; // Changed head
delete current; // free memory
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (current != nullptr && current->data != key) {
prev = current;
current = current->next;
}
// If key was not present in linked list
if (current == nullptr) return;
// Unlink the node from linked list
prev->next = current->next;
delete current; // free memory
}
C++
int countNodes() {
int count = 0;
Node* current = head;
while (current != nullptr) {
count++;
current = current->next;
}
return count;
}
C++
#include <iostream>
// ... (Node structure and LinkedList class as before)
// ... (All the function definitions from above)
int main() {
LinkedList myList;
myList.insertAtBeginning(10);
myList.insertAtEnd(20);
myList.insertAfter(myList.search(10), 15); // Insert 15 after 10
myList.display(); // 10 -> 15 -> 20 -> nullptr
myList.reverse();
myList.display(); // 20 -> 15 -> 10 -> nullptr
myList.deleteNode(15);
myList.display(); // 20 -> 10 -> nullptr
std::cout << "Number of nodes: " << myList.countNodes() << std::endl; // 2
return 0;
}
Percentage: 0%
Answered Questions: 0
Correct Answers: 0