Article on DSA Topic: Linked List
What is a Linked List?
A linked list is a linear data structure where each element, called a node, contains two parts:
- Data: The value stored in the node.
- Pointer: A reference to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations. This allows for efficient insertions and deletions.
Why Use a Linked List?
Linked lists are useful because:
- They allow for dynamic memory allocation.
- They provide efficient insertions and deletions compared to arrays.
- They can easily grow in size without requiring a large block of memory.
Types of Linked Lists
- Singly Linked List: Each node points to the next node.
- Doubly Linked List: Each node points to both the next and the previous node.
- Circular Linked List: The last node points to the first node, forming a circle.
Singly Linked List
What is a Singly Linked List?
A singly linked list is a type of linked list in which each node contains two parts:
- Data: The value stored in the node.
- Pointer: A reference to the next node in the sequence.
In a singly linked list, each node points to the next node in the list, and the last node points to nullptr
indicating the end of the list.
Why Use a Singly Linked List?
Singly linked lists are useful because:
- They allow for dynamic memory allocation.
- They provide efficient insertions and deletions compared to arrays.
- They can easily grow in size without requiring a large block of contiguous memory.
Basic Operations on Singly Linked Lists
- Insertion: Adding a new node to the list.
- Deletion: Removing a node from the list.
- Traversal: Visiting each node in the list.
- Search: Finding a node with a given value.
1. Insertion
Insertion can be performed at the beginning, at the end, or at a given position in the list.
- C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// Function to insert a node at the beginning of the list
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
head = newNode;
}
// Function to insert a node at the end of the list
void insertAtEnd(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Function to insert a node at a specific position in the list
void insertAtPosition(Node*& head, int position, int newData) {
if (position < 1) {
cout << "Position should be >= 1." << endl;
return;
}
if (position == 1) {
insertAtBeginning(head, newData);
return;
}
Node* newNode = new Node();
newNode->data = newData;
Node* temp = head;
for (int i = 1; i < position - 1 && temp != nullptr; ++i) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Position is out of bounds." << endl;
delete newNode;
} else {
newNode->next = temp->next;
temp->next = newNode;
}
}
// Function to print the list
void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
insertAtEnd(head, 40);
printList(head);
insertAtPosition(head, 2, 25);
printList(head);
insertAtPosition(head, 1, 5);
printList(head);
insertAtPosition(head, 7, 50); // Inserting at the end
printList(head);
insertAtPosition(head, 10, 60); // Position out of bounds
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
head = newNode;
}
// Function to insert a node at the end of the list
void insertAtEnd(int newData) {
Node newNode = new Node(newData);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
// Function to insert a node at a specific position in the list
void insertAtPosition(int position, int newData) {
if (position < 1) {
System.out.println("Position should be >= 1.");
return;
}
if (position == 1) {
insertAtBeginning(newData);
return;
}
Node newNode = new Node(newData);
Node temp = head;
for (int i = 1; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null) {
System.out.println("Position is out of bounds.");
} else {
newNode.next = temp.next;
temp.next = newNode;
}
}
// Function to print the list
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
list.insertAtEnd(40);
list.printList();
list.insertAtPosition(2, 25);
list.printList();
list.insertAtPosition(1, 5);
list.printList();
list.insertAtPosition(7, 50); // Inserting at the end
list.printList();
list.insertAtPosition(10, 60); // Position out of bounds
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function to insert a node at the end of the list
def insert_at_end(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
else:
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = new_node
# Function to insert a node at a specific position in the list
def insert_at_position(self, position, new_data):
if position < 1:
print("Position should be >= 1.")
return
if position == 1:
self.insert_at_beginning(new_data)
return
new_node = Node(new_data)
temp = self.head
for _ in range(1, position - 1):
if temp is None:
break
temp = temp.next
if temp is None:
print("Position is out of bounds.")
else:
new_node.next = temp.next
temp.next = new_node
# Function to print the list
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
list = LinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
list.insert_at_end(40)
list.print_list()
list.insert_at_position(2, 25)
list.print_list()
list.insert_at_position(1, 5)
list.print_list()
list.insert_at_position(7, 50) # Inserting at the end
list.print_list()
list.insert_at_position(10, 60) # Position out of bounds
list.print_list()
2. Deletion
Deletion can be performed at the beginning, at the end, or at a given position in the list.
- C++
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
head = newNode;
}
void deleteAtBeginning(Node*& head) {
if (head == nullptr) return;
Node* temp = head;
head = head->next;
delete temp;
}
void deleteAtEnd(Node*& head) {
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(Node*& head, int position) {
if (position < 1 || head == nullptr) {
cout << "Position out of bounds." << endl;
return;
}
if (position == 1) {
deleteAtBeginning(head);
return;
}
Node* temp = head;
for (int i = 1; i < position - 1 && temp != nullptr; ++i) {
temp = temp->next;
}
if (temp == nullptr || temp->next == nullptr) {
cout << "Position out of bounds." << endl;
return;
}
Node* nodeToDelete = temp->next;
temp->next = nodeToDelete->next;
delete nodeToDelete;
}
void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
deleteAtBeginning(head);
printList(head);
insertAtBeginning(head, 40);
insertAtBeginning(head, 50);
printList(head);
deleteAtEnd(head);
printList(head);
insertAtBeginning(head, 60);
insertAtBeginning(head, 70);
printList(head);
deleteAtPosition(head, 3);
printList(head);
deleteAtPosition(head, 1);
printList(head);
deleteAtPosition(head, 10); // Position out of bounds
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
head = newNode;
}
// Function to delete a node at the beginning of the list
void deleteAtBeginning() {
if (head == null) return;
Node temp = head;
head = head.next;
temp = null; // Java garbage collector will take care of deletion
}
// Function to delete a node at the end of the list
void deleteAtEnd() {
if (head == null) return;
if (head.next == null) {
head = null;
return;
}
Node temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
}
// Function to delete a node at a specific position in the list
void deleteAtPosition(int position) {
if (position < 1 || head == null) {
System.out.println("Position out of bounds.");
return;
}
if (position == 1) {
deleteAtBeginning();
return;
}
Node temp = head;
for (int i = 1; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null || temp.next == null) {
System.out.println("Position out of bounds.");
return;
}
Node nodeToDelete = temp.next;
temp.next = temp.next.next;
nodeToDelete = null; // Java garbage collector will take care of deletion
}
// Function to print the list
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
list.deleteAtBeginning();
list.printList();
list.insertAtBeginning(40);
list.insertAtBeginning(50);
list.printList();
list.deleteAtEnd();
list.printList();
list.insertAtBeginning(60);
list.insertAtBeginning(70);
list.printList();
list.deleteAtPosition(3);
list.printList();
list.deleteAtPosition(1);
list.printList();
list.deleteAtPosition(10); // Position out of bounds
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function to delete a node at the beginning of the list
def delete_at_beginning(self):
if self.head is None:
return
self.head = self.head.next
# Function to delete a node at the end of the list
def delete_at_end(self):
if self.head is None:
return
if self.head.next is None:
self.head = None
return
temp = self.head
while temp.next.next is not None:
temp = temp.next
temp.next = None
# Function to delete a node at a specific position in the list
def delete_at_position(self, position):
if position < 1 or self.head is None:
print("Position out of bounds.")
return
if position == 1:
self.delete_at_beginning()
return
temp = self.head
for _ in range(1, position - 1):
if temp is None:
break
temp = temp.next
if temp is None or temp.next is None:
print("Position out of bounds.")
else:
temp.next = temp.next.next
# Function to print the list
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
list = LinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
list.delete_at_beginning()
list.print_list()
list.insert_at_beginning(40)
list.insert_at_beginning(50)
list.print_list()
list.delete_at_end()
list.print_list()
list.insert_at_beginning(60)
list.insert_at_beginning(70)
list.print_list()
list.delete_at_position(3)
list.print_list()
list.delete_at_position(1)
list.print_list()
list.delete_at_position(10) # Position out of bounds
list.print_list()
3. Traversal
Traversal involves visiting each node in the list and performing an action on it, such as printing the node's data.
- Example: Printing All Elements Traverse from the head to the end of the list, printing each node's data.
- C++ Code
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
head = newNode;
}
void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
public void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
head = newNode;
}
public void printList() {
Node node = head;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
list = LinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
4. Search
Search involves finding a node with a given value.
-
Example: Searching for a Value Traverse from the head to the end of the list, comparing each node's data with the target value.
-
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
head = newNode;
}
bool search(Node* head, int target) {
Node* current = head;
while (current != nullptr) {
if (current->data == target) {
return true;
}
current = current->next;
}
return false;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
int target = 20;
if (search(head, target)) {
cout << "Element found." << endl;
} else {
cout << "Element not found." << endl;
}
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
public void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
head = newNode;
}
public boolean search(int target) {
Node current = head;
while (current != null) {
if (current.data == target) {
return true;
}
current = current.next;
}
return false;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
int target = 20;
if (list.search(target)) {
System.out.println("Element found.");
} else {
System.out.println("Element not found.");
}
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def search(self, target):
current = self.head
while current:
if current.data == target:
return True
current = current.next
return False
if __name__ == "__main__":
list = LinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
target = 20
if list.search(target):
print("Element found.")
else:
print("Element not found.")
Doubly Linked List
What is a Doubly Linked List?
A doubly linked list is a type of linked list in which each node contains three parts:
- Data: The value stored in the node.
- Next Pointer: A reference to the next node in the sequence.
- Previous Pointer: A reference to the previous node in the sequence.
In a doubly linked list, each node points to both its next and previous nodes, allowing traversal in both directions.
Why Use a Doubly Linked List?
Doubly linked lists are useful because:
- They allow for efficient insertions and deletions compared to arrays.
- They provide bidirectional traversal of the list.
- They can easily grow in size without requiring a large block of contiguous memory.
Basic Operations on Doubly Linked Lists
- Insertion: Adding a new node to the list.
- Deletion: Removing a node from the list.
- Traversal: Visiting each node in the list.
- Search: Finding a node with a given value.
1. Insertion
Insertion can be performed at the beginning, at the end, or at a given position in the list.
- C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
newNode->prev = nullptr;
if (head != nullptr) {
head->prev = newNode;
}
head = newNode;
}
void insertAtEnd(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = nullptr;
if (head == nullptr) {
newNode->prev = nullptr;
head = newNode;
return;
}
Node* last = head;
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
void insertAtPosition(Node*& head, int position, int newData) {
if (position < 1) {
cout << "Position should be >= 1." << endl;
return;
}
if (position == 1) {
insertAtBeginning(head, newData);
return;
}
Node* newNode = new Node();
newNode->data = newData;
Node* temp = head;
for (int i = 1; i < position - 1 && temp != nullptr; ++i) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Position is out of bounds." << endl;
delete newNode;
} else {
newNode->next = temp->next;
if (temp->next != nullptr) {
temp->next->prev = newNode;
}
temp->next = newNode;
newNode->prev = temp;
}
}
void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
insertAtEnd(head, 40);
printList(head);
insertAtPosition(head, 2, 25);
printList(head);
insertAtPosition(head, 1, 5);
printList(head);
insertAtPosition(head, 7, 50); // Inserting at the end
printList(head);
insertAtPosition(head, 10, 60); // Position out of bounds
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyLinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
// Function to insert a node at the end of the list
void insertAtEnd(int newData) {
Node newNode = new Node(newData);
newNode.next = null;
if (head == null) {
newNode.prev = null;
head = newNode;
return;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = newNode;
newNode.prev = last;
}
// Function to insert a node at a specific position in the list
void insertAtPosition(int position, int newData) {
if (position < 1) {
System.out.println("Position should be >= 1.");
return;
}
if (position == 1) {
insertAtBeginning(newData);
return;
}
Node newNode = new Node(newData);
Node temp = head;
for (int i = 1; i < position - 1 && temp != null; ++i) {
temp = temp.next;
}
if (temp == null) {
System.out.println("Position is out of bounds.");
return;
}
newNode.next = temp.next;
if (temp.next != null) {
temp.next.prev = newNode;
}
temp.next = newNode;
newNode.prev = temp;
}
// Function to print the list
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
list.insertAtEnd(40);
list.printList();
list.insertAtPosition(2, 25);
list.printList();
list.insertAtPosition(1, 5);
list.printList();
list.insertAtPosition(7, 50); // Inserting at the end
list.printList();
list.insertAtPosition(10, 60); // Position out of bounds
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
# Function to insert a node at the end of the list
def insert_at_end(self, new_data):
new_node = Node(new_data)
if self.head is None:
new_node.prev = None
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
new_node.prev = last
# Function to insert a node at a specific position in the list
def insert_at_position(self, position, new_data):
if position < 1:
print("Position should be >= 1.")
return
if position == 1:
self.insert_at_beginning(new_data)
return
new_node = Node(new_data)
temp = self.head
for _ in range(1, position - 1):
if temp is None:
return
temp = temp.next
if temp is None:
print("Position is out of bounds.")
return
new_node.next = temp.next
if temp.next:
temp.next.prev = new_node
temp.next = new_node
new_node.prev = temp
# Function to print the list
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
list = DoublyLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
list.insert_at_end(40)
list.print_list()
list.insert_at_position(2, 25)
list.print_list()
list.insert_at_position(1, 5)
list.print_list()
list.insert_at_position(7, 50) # Inserting at the end
list.print_list()
list.insert_at_position(10, 60) # Position out of bounds
list.print_list()
2. Deletion
Deletion can be performed at the beginning, at the end, or at a given position in the list.
- C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
newNode->prev = nullptr;
if (head != nullptr) {
head->prev = newNode;
}
head = newNode;
}
void deleteAtBeginning(Node*& head) {
if (head == nullptr) return;
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
delete temp;
}
void deleteAtEnd(Node*& head) {
if (head == nullptr) return;
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node* last = head;
while (last->next != nullptr) {
last = last->next;
}
if (last->prev != nullptr) {
last->prev->next = nullptr;
} else {
head = nullptr;
}
delete last;
}
void deleteAtPosition(Node*& head, int position) {
if (position < 1 || head == nullptr) {
cout << "Position out of bounds." << endl;
return;
}
if (position == 1) {
deleteAtBeginning(head);
return;
}
Node* temp = head;
for (int i = 1; i < position && temp != nullptr; ++i) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Position out of bounds." << endl;
return;
}
if (temp->next != nullptr) {
temp->next->prev = temp->prev;
}
if (temp->prev != nullptr) {
temp->prev->next = temp->next;
}
delete temp;
}
void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
deleteAtBeginning(head);
printList(head);
deleteAtEnd(head);
printList(head);
deleteAtPosition(head, 1);
printList(head);
deleteAtPosition(head, 1); // Position out of bounds
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyLinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
// Function to delete a node at the end of the list
void deleteAtEnd() {
if (head == null) return;
Node last = head;
while (last.next != null) {
last = last.next;
}
if (last.prev != null) {
last.prev.next = null;
} else {
head = null;
}
last.prev = null;
}
// Function to delete a node at a specific position in the list
void deleteAtPosition(int position) {
if (position < 1 || head == null) {
System.out.println("Position out of bounds.");
return;
}
if (position == 1) {
head = head.next;
if (head != null) {
head.prev = null;
}
return;
}
Node temp = head;
for (int i = 1; i < position && temp != null; ++i) {
temp = temp.next;
}
if (temp == null || temp.next == null) {
System.out.println("Position out of bounds.");
return;
}
temp.prev.next = temp.next;
if (temp.next != null) {
temp.next.prev = temp.prev;
}
}
// Function to print the list
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
list.deleteAtEnd();
list.printList();
list.deleteAtPosition(2);
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
# Function to delete a node at the end of the list
def delete_at_end(self):
if self.head is None:
return
last = self.head
while last.next:
last = last.next
if last.prev:
last.prev.next = None
else:
self.head = None
last.prev = None
# Function to delete a node at a specific position in the list
def delete_at_position(self, position):
if position < 1 or self.head is None:
print("Position out of bounds.")
return
if position == 1:
self.head = self.head.next
if self.head:
self.head.prev = None
return
temp = self.head
for _ in range(1, position - 1):
if temp is None:
return
temp = temp.next
if temp is None or temp.next is None:
print("Position out of bounds.")
return
if temp.next.next:
temp.next.next.prev = temp
temp.next = temp.next.next
# Function to print the list
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
list = DoublyLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
list.delete_at_end()
list.print_list()
list.delete_at_position(2)
list.print_list()
3. Traversal
Traversal involves visiting each node in the list and performing an action on it, such as printing the node's data.
-
Example: Printing All Elements Traverse from the head to the end of the list, printing each node's data.
-
C++
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
newNode->prev = nullptr;
if (head != nullptr) {
head->prev = newNode;
}
head = newNode;
}
void printList(Node* node) {
Node* last;
while (node != nullptr) {
cout << node->data << " ";
last = node;
node = node->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyLinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
// Function to print the list
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
# Function to print the list
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
list = DoublyLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
4. Search
Search involves finding a node with a given value.
- Example: Searching for a Value Traverse from the head to the end of the list, comparing each node's data with the target value.
- C++
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = head;
newNode->prev = nullptr;
if (head != nullptr) {
head->prev = newNode;
}
head = newNode;
}
bool search(Node* head, int target) {
Node* current = head;
while (current != nullptr) {
if (current->data == target) {
return true;
}
current = current->next;
}
return false;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
int target = 20;
if (search(head, target)) {
cout << "Element found." << endl;
} else {
cout << "Element not found." << endl;
}
return 0;
}
- Java
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyLinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
// Function to search for an element in the list
boolean search(int target) {
Node current = head;
while (current != null) {
if (current.data == target) {
return true;
}
current = current.next;
}
return false;
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
int target = 20;
if (list.search(target)) {
System.out.println("Element found.");
} else {
System.out.println("Element not found.");
}
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
# Function to search for an element in the list
def search(self, target):
current = self.head
while current:
if current.data == target:
return True
current = current.next
return False
if __name__ == "__main__":
list = DoublyLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
target = 20
if list.search(target):
print("Element found.")
else:
print("Element not found.")
Circular Linked List
What is a Circular Linked List?
A circular linked list is a type of linked list where the last node points back to the first node, forming a circle. This means that the list can be traversed starting from any node and eventually returns to the starting node.
Why Use a Circular Linked List?
Circular linked lists are useful because:
- They allow for continuous traversal of the list.
- They can be useful in applications where the list needs to be cyclically rotated.
- They are beneficial in implementing circular queues and buffers.
Types of Circular Linked Lists
- Singly Circular Linked List: Each node points to the next node and the last node points to the first node.
- Doubly Circular Linked List: Each node points to both the next and previous nodes, and the last node points back to the first node and vice versa.
Basic Operations on Circular Linked Lists
- Insertion: Adding a new node to the list.
- Deletion: Removing a node from the list.
- Traversal: Visiting each node in the list.
- Search: Finding a node with a given value.
1. Insertion
Insertion can be performed at the beginning, at the end, or at a given position in the list.
- C++
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
// Function to insert a node at the end of the circular linked list
void insertAtEnd(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
newNode->next = nullptr;
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
// Function to insert a node at a specific position in the circular linked list
void insertAtPosition(Node*& head, int position, int newData) {
if (position < 1) {
cout << "Invalid position." << endl;
return;
}
Node* newNode = new Node();
newNode->data = newData;
if (position == 1) {
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
return;
}
Node* temp = head;
for (int i = 1; i < position - 1 && temp != nullptr; ++i) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Invalid position." << endl;
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to print the circular linked list
void printList(Node* head) {
if (head == nullptr) return;
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtEnd(head, 30);
insertAtPosition(head, 2, 40); // Inserting at position 2
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
Node head;
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
newNode.next = head;
temp.next = newNode;
head = newNode;
}
// Function to insert a node at the end of the circular linked list
void insertAtEnd(int newData) {
Node newNode = new Node(newData);
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
// Function to insert a node at a specific position in the circular linked list
void insertAtPosition(int position, int newData) {
if (position < 1) {
System.out.println("Invalid position.");
return;
}
Node newNode = new Node(newData);
if (position == 1) {
if (head == null) {
newNode.next = newNode;
head = newNode;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
newNode.next = head;
temp.next = newNode;
head = newNode;
}
return;
}
Node temp = head;
for (int i = 1; i < position - 1 && temp != null; ++i) {
temp = temp.next;
}
if (temp == null) {
System.out.println("Invalid position.");
return;
}
newNode.next = temp.next;
temp.next = newNode;
}
// Function to print the circular linked list
void printList() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtEnd(30);
list.insertAtPosition(2, 40); // Inserting at position 2
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the circular linked list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
temp = self.head
while temp.next != self.head:
temp = temp.next
new_node.next = self.head
temp.next = new_node
self.head = new_node
# Function to insert a node at the end of the circular linked list
def insert_at_end(self, new_data):
new_node = Node(new_data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
# Function to insert a node at a specific position in the circular linked list
def insert_at_position(self, position, new_data):
if position < 1:
print("Invalid position.")
return
new_node = Node(new_data)
if position == 1:
if self.head is None:
new_node.next = new_node
self.head = new_node
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
new_node.next = self.head
temp.next = new_node
self.head = new_node
return
temp = self.head
for i in range(1, position - 1):
if temp is None:
print("Invalid position.")
return
temp = temp.next
new_node.next = temp.next
temp.next = new_node
# Function to print the circular linked list
def print_list(self):
if self.head is None:
return
temp = self.head
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.head:
break
print()
if __name__ == "__main__":
list = CircularLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_end(30)
list.insert_at_position(2, 40) # Inserting at position 2
list.print_list()
2. Deletion
Deletion can be performed at the beginning, at the end, or at a given position in the list.
- C++
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
}
// Function to delete a node at the beginning of the circular linked list
void deleteAtBeginning(Node*& head) {
if (head == nullptr) return;
if (head->next == head) {
delete head;
head = nullptr;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
Node* tempHead = head;
head = head->next;
temp->next = head;
delete tempHead;
}
}
// Function to delete a node at the end of the circular linked list
void deleteAtEnd(Node*& head) {
if (head == nullptr) return;
if (head->next == head) {
delete head;
head = nullptr;
} else {
Node* temp = head;
Node* prev = nullptr;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head;
delete temp;
}
}
// Function to delete a node at a specific position in the circular linked list
void deleteAtPosition(Node*& head, int position) {
if (head == nullptr || position < 1) return;
if (position == 1) {
deleteAtBeginning(head);
return;
}
Node* temp = head;
Node* prev = nullptr;
for (int i = 1; i < position && temp->next != head; ++i) {
prev = temp;
temp = temp->next;
}
if (temp == head) return;
prev->next = temp->next;
delete temp;
}
// Function to print the circular linked list
void printList(Node* head) {
if (head == nullptr) return;
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
deleteAtEnd(head);
printList(head);
deleteAtBeginning(head);
printList(head);
deleteAtPosition(head, 1); // Deleting node at position 1
printList(head);
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
Node head;
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
newNode.next = head;
temp.next = newNode;
head = newNode;
}
// Function to delete a node at the beginning of the circular linked list
void deleteAtBeginning() {
if (head == null) return;
if (head.next == head) {
head = null;
return;
}
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
Node tempHead = head;
head = head.next;
temp.next = head;
tempHead = null;
}
// Function to delete a node at the end of the circular linked list
void deleteAtEnd() {
if (head == null) return;
if (head.next == head) {
head = null;
return;
}
Node temp = head;
Node prev = null;
while (temp.next != head) {
prev = temp;
temp = temp.next;
}
prev.next = head;
temp = null;
}
// Function to delete a node at a specific position in the circular linked list
void deleteAtPosition(int position) {
if (head == null || position < 1) return;
if (position == 1) {
deleteAtBeginning();
return;
}
Node temp = head;
Node prev = null;
for (int i = 1; i < position && temp.next != head; ++i) {
prev = temp;
temp = temp.next;
}
if (temp == head) return;
prev.next = temp.next;
temp = null;
}
// Function to print the circular linked list
void printList() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
list.deleteAtEnd();
list.printList();
list.deleteAtBeginning();
list.printList();
list.deleteAtPosition(1); // Deleting node at position 1
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the circular linked list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
temp = self.head
while temp.next != self.head:
temp = temp.next
new_node.next = self.head
temp.next = new_node
self.head = new_node
# Function to delete a node at the beginning of the circular linked list
def delete_at_beginning(self):
if self.head is None:
return
if self.head.next == self.head:
self.head = None
return
temp = self.head
while temp.next != self.head:
temp = temp.next
temp_head = self.head
self.head = self.head.next
temp.next = self.head
temp_head = None
# Function to delete a node at the end of the circular linked list
def delete_at_end(self):
if self.head is None:
return
if self.head.next == self.head:
self.head = None
return
temp = self.head
prev = None
while temp.next != self.head:
prev = temp
temp = temp.next
prev.next = self.head
temp = None
# Function to delete a node at a specific position in the circular linked list
def delete_at_position(self, position):
if self.head is None or position < 1:
return
if position == 1:
self.delete_at_beginning()
return
temp = self.head
prev = None
for i in range(1, position):
prev = temp
temp = temp.next
if temp == self.head:
return
prev.next = temp.next
temp = None
# Function to print the circular linked list
def print_list(self):
if self.head is None:
return
temp = self.head
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.head:
break
print()
if __name__ == "__main__":
list = CircularLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
list.delete_at_end()
list.print_list()
list.delete_at_beginning()
list.print_list()
list.delete_at_position(1) # Deleting node at position 1
list.print_list()
3. Traversal
Traversal involves visiting each node in the list and performing an action on it, such as printing the node's data.
-
Example: Printing All Elements Traverse from the head to the end of the list, printing each node's data.
-
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
}
void printList(Node* head) {
if (head == nullptr) return;
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
printList(head);
return 0;
}
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
Node head;
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
newNode.next = head;
temp.next = newNode;
head = newNode;
}
// Function to print the circular linked list
void printList() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.printList();
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the circular linked list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
temp = self.head
while temp.next != self.head:
temp = temp.next
new_node.next = self.head
temp.next = new_node
self.head = new_node
# Function to print the circular linked list
def print_list(self):
if self.head is None:
return
temp = self.head
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.head:
break
print()
if __name__ == "__main__":
list = CircularLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
list.print_list()
4. Search
Search involves finding a node with a given value.
Example: Searching for a Value
Traverse from the head to the end of the list, comparing each node's data with the target value.
- C++ Code
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node();
newNode->data = newData;
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
}
bool search(Node* head, int target) {
if (head == nullptr) return false;
Node* current = head;
do {
if (current->data == target) {
return true;
}
current = current->next;
} while (current != head);
return false;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 10);
insertAtBeginning(head, 20);
insertAtBeginning(head, 30);
int target = 20;
if (search(head, target)) {
cout << "Element found." << endl;
} else {
cout << "Element not found." << endl;
}
return 0;
}
- Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
Node head;
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
newNode.next = head;
temp.next = newNode;
head = newNode;
}
// Function to search for a target value in the circular linked list
boolean search(int target) {
if (head == null) return false;
Node current = head;
do {
if (current.data == target) {
return true;
}
current = current.next;
} while (current != head);
return false;
}
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
int target = 20;
if (list.search(target)) {
System.out.println("Element found.");
} else {
System.out.println("Element not found.");
}
}
}
- Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the beginning of the circular linked list
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
temp = self.head
while temp.next != self.head:
temp = temp.next
new_node.next = self.head
temp.next = new_node
self.head = new_node
# Function to search for a target value in the circular linked list
def search(self, target):
if self.head is None:
return False
current = self.head
while True:
if current.data == target:
return True
current = current.next
if current == self.head:
break
return False
if __name__ == "__main__":
list = CircularLinkedList()
list.insert_at_beginning(10)
list.insert_at_beginning(20)
list.insert_at_beginning(30)
target = 20
if list.search(target):
print("Element found.")
else:
print("Element not found.")
Applications of Linked Lists
- Implementation of Stacks and Queues: Linked lists are used to implement stack and queue data structures.
- Dynamic Memory Allocation: They are used in memory management to allocate and deallocate memory dynamically.
- Graph Representation: Adjacency lists in graph theory are implemented using linked lists.
- Symbol Table Management: In compilers, linked lists are used to manage symbol tables.