A linked list is a linear data structure consisting of a sequence of elements, called nodes, where each node stores both data and a reference (or pointer) to the next node in the sequence.
• Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic memory allocation and efficient insertion and deletion of elements at any position in the list.
Declaration of linked List:
In Java, you can declare a linked list by defining a class that represents the nodes of the linked list and another class that represents the linked list itself.
Here’s a basic example:
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
private Node head;
public LinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// Other methods for the linked list (e.g., display, delete, search) can be added here
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
// Display the linked list
Node current = list.head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
// Output: 1 2 3
}
}
OUTPUT:
1 2 3
In this example:
- The
Node
class represents a node in the linked list. It contains a data field to store the value of the node and a next field to reference the next node in the list. - The
LinkedList
class represents the linked list itself. It contains a reference to the head node, which is the starting point of the list. - The
add
method adds a new node with the given data to the end of the list. - Other methods for the linked list (e.g., display, delete, search) can be added to the
LinkedList
class as needed. - In the
main
method, we create an instance of theLinkedList
class, add some elements to it, and then display the elements of the linked list.
Advantages of linked list:
Here are the key advantages of Linked list:
- Dynamic Memory Allocation: Linked lists allow for dynamic memory allocation, meaning they can grow or shrink in size as needed. This flexibility is particularly useful when the size of the data structure is not known in advance or varies dynamically during program execution.
- Efficient Insertion and Deletion: Insertion and deletion operations in linked lists are generally more efficient compared to arrays, especially for inserting or deleting elements in the middle of the list. Linked lists only require adjusting pointers, while arrays may require shifting elements to accommodate the change.
- No Wasted Space: Unlike arrays, where memory may be allocated but remain unused if the array size exceeds the required capacity, linked lists do not suffer from wasted space due to over-allocation. Each node in a linked list only consumes as much memory as necessary for its data and pointers.
- Dynamic Size: Linked lists can easily accommodate changes in size without requiring expensive resizing operations or reallocation of memory. This makes them suitable for applications where the size of the data structure varies dynamically over time.
- Ease of Insertion at the Beginning: Inserting an element at the beginning of a linked list is a constant-time operation, regardless of the list size. This is in contrast to arrays, where inserting an element at the beginning may require shifting all existing elements.