Linked List
A linked list is a fundamental data structure used in computer science to organize and store data efficiently. Unlike arrays, linked lists consist of nodes, where each node contains data and a reference (or link) to the next node in the sequence. This structure allows for dynamic memory allocation and efficient insertions and deletions, making linked lists highly versatile and useful for various applications.
Comparison with Arrays
Linked lists and arrays are both used to store collections of elements, but they have key differences that affect their performance and usage:
-
Memory Allocation:
- Arrays: Use contiguous memory allocation. The size of the array is fixed at the time of its creation, which can lead to wasted memory if the array is not fully utilized or insufficient memory if it needs to be resized.
- Linked Lists: Use dynamic memory allocation. Each element (node) is allocated separately, allowing the linked list to grow or shrink in size as needed without reallocating memory for the entire structure.
-
Insertion and Deletion:
- Arrays: Inserting or deleting elements in an array requires shifting elements to maintain the order, which can be time-consuming (O(n) time complexity for both operations).
- Linked Lists: Insertion and deletion operations are more efficient (O(1) time complexity) as they involve updating pointers rather than shifting elements.
-
Access Time:
- Arrays: Provide constant-time access (O(1)) to elements using their indices, making them suitable for scenarios where frequent access to elements is required.
- Linked Lists: Require sequential access (O(n) time complexity) to reach a specific element, which can be slower compared to arrays.
Basic Terminologies Related to Linked Lists
Understanding the fundamental terminologies associated with linked lists is essential for grasping their structure and operations:
- Node: The basic unit of a linked list. Each node contains the data to be stored and a pointer (or reference) to the next node in the list.
- Head: The first node in the linked list. It serves as the entry point for accessing the list. If the linked list is empty, the head points to null.
- Tail: The last node in the linked list. In a singly linked list, the tail’s next pointer points to null, indicating the end of the list.
- Pointer/Reference: A field in each node that stores the address of the next node in the sequence. This allows the nodes to be linked together.
- Singly Linked List: A type of linked list where each node has a single pointer to the next node. This is the simplest form of a linked list.
- Doubly Linked List: A more complex form of a linked list where each node has two pointers: one to the next node and one to the previous node. This allows traversal in both directions.
- Circular Linked List: A variation of linked lists where the last node points back to the first node, forming a circular structure. This can be implemented as either a singly or doubly linked list.
Creating the Node
In a linked list, a node is the fundamental building block. Each node contains data and a pointer to the next node. Here’s how to define and create a node in C++:
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
// Creating a node with data value 10
Node* newNode = new Node(10);
Operations on Linked List
Insertion of Data
Insertion at the Beginning:
To insert a node at the beginning of a linked list, create a new node and set its next pointer to the current head. Then, update the head to this new node.
void insertAtBeginning(Node*& head, int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}
Time Complexity: O(1)
Insertion at the End:
To insert a node at the end of a linked list, traverse to the last node and set its next pointer to the new node.
void insertAtEnd(Node*& head, int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
Time Complexity: O(n)
Insertion at a Specific Position:
To insert a node at a specific position, traverse to the node just before the desired position and adjust the pointers accordingly.
void insertAtPosition(Node*& head, int val, int position) {
Node* newNode = new Node(val);
if (position == 0) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 0; temp != nullptr && i < position - 1; ++i) {
temp = temp->next;
}
if (temp == nullptr) return; // Position is out of bounds
newNode->next = temp->next;
temp->next = newNode;
}
Time Complexity: O(n)
Traversing a Linked List
To traverse a linked list means to visit each node in the list, starting from the head, and accessing its data or performing operations on it.
void traverseLinkedList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
}
Time Complexity: O(n)
Deleting Elements from a Linked List
Deleting elements from a linked list involves removing nodes from the list while maintaining the integrity of the structure.
Deletion from the Beginning:
To delete a node from the beginning of a linked list, update the head to point to the next node, and deallocate memory for the removed node.
void deleteFromBeginning(Node*& head) {
if (head == nullptr) return;
Node* temp = head;
head = head->next;
delete temp;
}
Time Complexity: O(1)
Deletion from the End:
To delete a node from the end of a linked list, traverse to the second-to-last node, update its next pointer to null, and deallocate memory for the last node.
void deleteFromEnd(Node*& head) {
if (head == nullptr || 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;
}
Time Complexity: O(n)
Deletion from a Specific Position:
To delete a node from a specific position, traverse to the node just before the target position, update its next pointer to skip the target node, and deallocate memory for the removed node.
void deleteAtPosition(Node*& head, int position) {
if (head == nullptr) return;
Node* temp = head;
if (position == 0) {
head = head->next;
delete temp;
return;
}
for (int i = 0; temp != nullptr && i < position - 1; ++i) {
temp = temp->next;
}
if (temp == nullptr || temp->next == nullptr) return; // Position is out of bounds
Node* nodeToDelete = temp->next;
temp->next = temp->next->next;
delete nodeToDelete;
}
Time Complexity: O(n)
Searching and Updating Values in a Linked List
Searching for a specific value in a linked list involves traversing the list and comparing each node’s data with the target value. Updating the value of a node requires locating the node with the target value and modifying its data field.
Searching for a Value:
To search for a value in a linked list, traverse the list until the target value is found or the end of the list is reached.
bool searchValue(Node* head, int target) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == target) {
return true; // Value found
}
temp = temp->next;
}
return false; // Value not found
}
Time Complexity: O(n)
Updating a Value:
To update the value of a node in a linked list, locate the node with the target value and modify its data field.
void updateValue(Node* head, int oldValue, int newValue) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == oldValue) {
temp->data = newValue; // Update value
return;
}
temp = temp->next;
}
}
Time Complexity: O(n)
Reversing a Linked List
Reversing a linked list involves changing the direction of pointers so that the last node becomes the first node, and so on.
Node* reverseLinkedList(Node* head) {
Node* prev = nullptr;
Node* current = head;
Node* nextNode = nullptr;
while (current != nullptr) {
nextNode = current->next; // Store next node
current->next = prev; // Reverse pointer
prev = current; // Move pointers one position ahead
current = nextNode;
}
return prev; // New head of the reversed list
}
Time Complexity: O(n)
Full Code Implementation of Singly Linked List
Here’s a comprehensive C++ implementation of a singly linked list, encapsulated within a class. The implementation includes various functions such as insertion, deletion, traversal, searching, updating values, and reversing the list.
#include <iostream>
using namespace std;
class LinkedList {
private:
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
Node* head;
public:
LinkedList() {
head = nullptr;
}
void insertAtBeginning(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}
void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
void insertAtPosition(int val, int position) {
Node* newNode = new Node(val);
if (position == 0) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 0; temp != nullptr && i < position - 1; ++i) {
temp = temp->next;
}
if (temp == nullptr) return; // Position is out of bounds
newNode->next = temp->next;
temp->next = newNode;
}
void deleteFromBeginning() {
if (head == nullptr) return;
Node* temp = head;
head = head->next;
delete temp;
}
void deleteFromEnd() {
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 deleteAtPosition(int position) {
if (head == nullptr) return;
Node* temp = head;
if (position == 0) {
head = head->next;
delete temp;
return;
}
for (int i = 0; temp != nullptr && i < position - 1; ++i) {
temp = temp->next;
}
if (temp == nullptr || temp->next == nullptr) return; // Position is out of bounds
Node* nodeToDelete = temp->next;
temp->next = temp->next->next;
delete nodeToDelete;
}
void traverseLinkedList() const {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
bool searchValue(int target) const {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == target) {
return true; // Value found
}
temp = temp->next;
}
return false; // Value not found
}
void updateValue(int oldValue, int newValue) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == oldValue) {
temp->data = newValue; // Update value
return;
}
temp = temp->next;
}
}
void reverseLinkedList() {
Node* prev = nullptr;
Node* current = head;
Node* nextNode = nullptr;
while (current != nullptr) {
nextNode = current->next; // Store next node
current->next = prev; // Reverse pointer
prev = current; // Move pointers one position ahead
current = nextNode;
}
head = prev;
}
int getLength() const {
int length = 0;
Node* temp = head;
while (temp != nullptr) {
length++;
temp = temp->next;
}
return length;
}
bool isEmpty() const {
return head == nullptr;
}
~LinkedList() {
Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
LinkedList list;
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
cout << "List after inserting at the end: ";
list.traverseLinkedList();
list.insertAtBeginning(5);
cout << "List after inserting at the beginning: ";
list.traverseLinkedList();
list.insertAtPosition(15, 2);
cout << "List after inserting at position 2: ";
list.traverseLinkedList();
cout << "Length of the list: " << list.getLength() << endl;
list.deleteFromBeginning();
cout << "List after deleting from the beginning: ";
list.traverseLinkedList();
list.deleteFromEnd();
cout << "List after deleting from the end: ";
list.traverseLinkedList();
list.deleteAtPosition(1);
cout << "List after deleting at position 1: ";
list.traverseLinkedList();
if (list.searchValue(20)) {
cout << "Value 20 found in the list" << endl;
} else {
cout << "Value 20 not found in the list" << endl;
}
list.updateValue(15, 25);
cout << "List after updating value 15 to 25: ";
list.traverseLinkedList();
list.reverseLinkedList();
cout << "List after reversing: ";
list.traverseLinkedList();
return 0;
}
This code defines a LinkedList class with various methods to manipulate the linked list, such as inserting, deleting, traversing, searching, updating values, reversing, checking if the list is empty, and getting the length of the list. The main function demonstrates the usage of these methods.
Doubly Linked List
A doubly linked list is an extension of a singly linked list where each node contains an additional pointer to the previous node, allowing for traversal in both directions. This bidirectional nature offers greater flexibility in certain operations compared to a singly linked list.
Creating a Node
To create a node in a doubly linked list, you need to define a class with data, a pointer to the next node, and a pointer to the previous node.
class DoublyNode {
public:
int data;
DoublyNode* next;
DoublyNode* prev;
DoublyNode(int val) {
data = val;
next = nullptr;
prev = nullptr;
}
};
// Creating a node with data value 10
DoublyNode* newNode = new DoublyNode(10);
Advantages Over Singly Linked List
Time Complexity Advantages
Circular Linked List
A circular linked list is a variation of a linked list where the last node points back to the first node, forming a circular structure. This type of list can be singly or doubly linked and offers benefits in certain scenarios, such as round-robin scheduling.
Creating a Node
To create a node in a circular linked list, you define a class similar to a regular singly or doubly linked list, but with the understanding that the next pointer of the last node points back to the head.
class CircularNode {
public:
int data;
CircularNode* next;
CircularNode(int val) {
data = val;
next = nullptr;
}
};
// Creating a node with data value 10
CircularNode* newNode = new CircularNode(10);
Advantages Over Singly Linked List
Time Complexity Advantages
Source link
lol
