Introduction
A
linked list
is a linear data structure where elements, called
nodes, are stored in separate memory locations and connected using references
(pointers).
1. What is Linked List Data Structure in Java?
A Linked List is a linear data structure where elements (nodes) are linked using pointers. Unlike arrays, linked lists do not require a contiguous memory location. Each node contains:
- Data: The actual value stored in the node.
- Pointer: A reference to the next node in the sequence.
Unlike arrays, linked lists provide dynamic memory allocation, making them efficient for insertions and deletions. However, they require additional memory for storing pointers.
1.1 Types of Linked Lists
Linked lists can be categorized into different types based on how nodes are linked together. Each type has its own structure and use case.
- Singly Linked List: Each node contains data and a pointer to the next node in the sequence.
- Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node, allowing traversal in both directions.
- Circular Linked List: The last node points back to the first node, forming a circular structure. This can be singly or doubly linked.
1.2 Advantages of Linked Lists
Linked lists offer several benefits over arrays, making them suitable for certain applications where dynamic memory allocation and efficient modifications are required.
- Efficient insertions and deletions: Unlike arrays, linked lists do not require shifting elements when inserting or deleting elements.
- Dynamic memory allocation: They grow and shrink as needed, avoiding unnecessary memory usage.
- Faster reorganization: Data structures like stacks and queues can be implemented efficiently using linked lists.
1.3 Disadvantages of Linked Lists
Despite their advantages, linked lists also have some downsides, primarily due to their pointer-based structure.
- Extra memory overhead: Each node requires additional space for storing pointers, increasing memory consumption.
- Slower search operations: Unlike arrays, linked lists do not allow direct access to elements, requiring sequential traversal.
- More complex implementation: Managing pointers and memory allocation makes linked lists harder to implement compared to arrays.
Each node contains: Data: The actual value. Pointer (next): A reference to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing dynamic memory allocation and efficient insertions/deletions without shifting elements.
2. Structure of a Node
In Java, we can define a node as:
3. Basic Operations
In a manually implemented linked list, we typically create a LinkedList class that manages operations.
a. Insert at Beginning
- Create a new node.
- Point the new node’s next to the current head.
- Make the new node the new head.
b. Insert at End
- Traverse to the last node.
- Point its next to the new node.
c. Insert in the Middle
- Traverse to the position.
- Adjust pointers so the new node fits in.
d. Delete a Node
- Update the next reference of the previous node to skip the target node.
- Special case: deleting the head.
e. Display the List
- Traverse from head to tail, printing each node’s data.
4. Example: Manual Linked List Implementation
CustomLinkedList.java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class CustomLinkedList {
Node head;
// Insert at beginning
void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// Insert at end
void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) temp = temp.next;
temp.next = newNode;
}
// Insert at position
void insertAtPosition(int data, int position) {
if (position == 0) {
insertAtBeginning(data);
return;
}
Node newNode = new Node(data);
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null) return; // Position out of bounds
newNode.next = temp.next;
temp.next = newNode;
}
// Delete by value
void deleteByValue(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node temp = head;
while (temp.next != null && temp.next.data != data) {
temp = temp.next;
}
if (temp.next != null) {
temp.next = temp.next.next;
}
}
// Searches for a node with the given value in the linked list.
boolean search(int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) return true;
temp = temp.next;
}
return false;
}
// Reverses the linked list.
public void reverse() {
Node prev = null, current = head, next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
// Display
void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("null");
}
}
class LinkedListDemo {
public static void main(String[] args) {
CustomLinkedList list = new CustomLinkedList();
// Insert elements
list.insert(10);
list.insert(20);
list.insert(30);
System.out.println("Initial Linked List:");
list.display(); // Output: 10 -> 20 -> 30 -> null
// Insert at the beginning
list.insertAtBeginning(5);
System.out.println("After inserting 5 at the beginning:");
list.display(); // Output: 5 -> 10 -> 20 -> 30 -> null
// Insert at a specific position
list.insertAtPosition(15, 2);
System.out.println("After inserting 15 at position 2:");
list.display(); // Output: 5 -> 10 -> 15 -> 20 -> 30 -> null
// Delete a node by value
list.deleteByValue(20);
System.out.println("After deleting 20:");
list.display(); // Output: 5 -> 10 -> 15 -> 30 -> null
// Search for an element
System.out.println("Searching for 15: " + list.search(15)); // Output: true
// Reverse the linked list
list.reverse();
System.out.println("After reversing the linked list:");
list.display(); // Output: 30 -> 15 -> 10 -> 5 -> null
}
}
Post a Comment