A linked list is a dynamic data structure used for organizing and storing a collection of elements. Unlike arrays, which require contiguous memory allocation, linked lists consist of nodes, each containing data and a reference to the next node in the sequence. In Java, linked lists can be implemented using classes to represent nodes and manage the overall structure.
Internal working of LinkedList
Internally, a linked list consists of nodes connected through references. The first node, known as the head, holds the initial element, and each subsequent node points to the next element in the sequence. The last node's reference is typically set to null, indicating the end of the list. Insertions and deletions involve adjusting these references to maintain the order.
Constructors in the LinkedList:
In Java, the LinkedList class provides various constructors. The default constructor initializes an empty linked list, while another constructor allows creating a linked list from a specified collection.
1. Default Constructor:
LinkedList()
Creates an empty linked list.
2. Constructor with Collection Parameter:
LinkedList(Collection<? extends E> c)
Creates a linked list containing the elements of the specified collection.
Different Ways to Implement LinkedList in Java:
1. Manual Implementation:
Developers can manually create a Node class and a LinkedList class to represent individual elements and manage the list's structure. Methods for insertion, deletion, and traversal are implemented within these classes.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
// Methods for insertion, deletion, and traversal go here
}
2. Using java.util.LinkedList:
Java provides a built-in LinkedList class in the java.util package. This class implements the List interface and offers various methods for manipulating the linked list.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(10);
linkedList.add(20);
linkedList.add(30);
// Methods for manipulation are available through the LinkedList class
}
}
Overview of linked lists in Java:
1. Node Class:
A Node class is used to represent individual elements in the linked list. It typically has two properties: a data field to store the element, and a reference (link) to the next node.
java
Copy code
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
2. LinkedList Class:
A LinkedList class manages the linked list by providing methods to add, remove, and access elements. It has a reference to the head, which points to the first node in the list.
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
// Methods to manipulate the linked list go here
}
3. Operations:
a. Insertion:
Insert at the Beginning:
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
Insert at the End:
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
b. Deletion:
Delete at the Beginning:
public void deleteAtBeginning() {
if (head != null) {
head = head.next;
}
}
Delete at the End:
public void deleteAtEnd() {
if (head == null || head.next == null) {
head = null;
return;
}
Node current = head;
while (current.next.next != null) {
current = current.next;
}
current.next = null;
}
c. Traversal:
Print Linked List:
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
4. Example Usage :
public class Main {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insertAtEnd(10);
linkedList.insertAtBeginning(5);
linkedList.insertAtEnd(20);
linkedList.printList(); // Output: 5 10 20
linkedList.deleteAtBeginning();
linkedList.printList(); // Output: 10 20
linkedList.deleteAtEnd();
linkedList.printList(); // Output: 10
}
}
This example demonstrates basic operations on a singly linked list in Java. There are variations of linked lists, such as doubly linked lists and circular linked lists, but the basic principles remain similar.
Classes Implementing the List Interface:
AbstractList: AbstractList is an abstract class providing a skeletal implementation of the List interface. It extends AbstractCollection and serves as a base for list implementations.
CopyOnWriteArrayList: CopyOnWriteArrayList is a thread-safe variant of ArrayList. It ensures thread safety by making a fresh copy of the underlying array whenever a mutative operation is performed.
AbstractSequentialList: AbstractSequentialList extends AbstractList and provides a skeletal implementation of the SequentialList interface. It is designed for classes that implement a linked list or a similar sequential access data structure.
Methods for Java LinkedList:
The LinkedList class in Java provides several methods for manipulating linked lists. Here are some commonly used methods:
1. Adding Elements:
add(E e)
addFirst(E e)
addLast(E e)
2. Removing Elements:
remove()
removeFirst()
removeLast()
3. Accessing Elements:
get(int index)
getFirst()
getLast()
4. Other Operations:
size()
isEmpty()
clear()
Example Implementation in Java:
Here's a simple example of a singly linked list in Java:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
}
public class Main {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insertAtEnd(10);
linkedList.insertAtEnd(20);
linkedList.insertAtEnd(30);
linkedList.printList(); // Output: 10 20 30
}
}
Real-world Uses of Linked Lists:
Dynamic Memory Allocation: Linked lists are suitable for scenarios where the size of the data structure is not known in advance, and dynamic memory allocation is essential.
Implementing Stacks and Queues: Linked lists are used to implement fundamental data structures like stacks and queues due to their efficient insertion and deletion operations.
Undo Functionality in Software: Linked lists can be employed to implement undo functionality in software applications, where each node represents a state, and undoing involves traversing the list backward.
Task Management Systems: In task management systems, linked lists can represent a sequence of tasks, and efficient insertion and deletion make them suitable for managing task lists.
Symbol Tables in Compilers: Symbol tables in compilers often use linked lists to manage variable and function declarations efficiently.
Linked lists offer advantages in specific scenarios, and their use depends on the requirements of the application and the operations that need to be performed on the data.
Pros of Linked Lists:
Dynamic Size:Linked lists can grow or shrink in size during program execution, making them more flexible than arrays.
Efficient Insertions and Deletions: Insertions and deletions can be performed at any position in constant time, provided the node is accessible.
No Pre-allocation of Memory: Linked lists don't require pre-allocation of memory for a specific size, allowing for more efficient memory usage.
Cons of Linked Lists:
Sequential Access Only: To access an element in a linked list, you need to traverse from the head to the desired node sequentially. Random access is not as efficient as in arrays.
Extra Memory: Each element in a linked list requires additional memory to store the reference (link) to the next node, leading to increased overhead.
Cache Issues: Linked lists may have poor cache performance due to scattered storage locations for elements.