Linked List

Definition

A Linked List is a linear data structure included in the Java Collections Framework (under java.util.LinkedList) where elements are stored in nodes. Unlike arrays, where elements are stored in contiguous memory locations, each node in a linked list contains the data and a reference (pointer) to the next node in the sequence, allowing for non-contiguous memory allocation.

Main Content

1. Node Structure

• A node is the fundamental building block of a linked list.
• Every node consists of two parts: the "Data" (the actual value) and the "Next" (a reference to the subsequent node).

[ Data | Next ] -> [ Data | Next ] -> null

2. Types of Linked Lists

• Singly Linked List: Each node points only to the next node, moving in a unidirectional flow.
• Doubly Linked List: Each node contains two pointers, one to the next node and one to the previous node, allowing bidirectional traversal.

3. Java LinkedList Implementation

• The LinkedList class in Java implements both the List and Deque interfaces.
• It allows for null elements and provides methods to manipulate data from both ends of the list efficiently.

Working / Process

1. Insertion Process

• Identify the position where the new node needs to be inserted.
• Update the "Next" reference of the new node to point to the current successor, and update the previous node's "Next" pointer to point to the new node.

2. Deletion Process

• Locate the node intended for deletion by traversing the list.
• Change the "Next" pointer of the preceding node to skip the deleted node and point directly to the successor of the deleted node.

3. Traversal Process

• Start at the "Head" node, which acts as the entry point of the list.
• Follow the "Next" reference of each node sequentially until the reference points to null, indicating the end of the list.

Advantages / Applications

• Dynamic Size: Unlike arrays, linked lists can grow or shrink in size during runtime without needing to reallocate memory.
• Efficient Insertions/Deletions: Adding or removing elements does not require shifting other elements, making it faster for frequent modification operations.
• Implementation of Collections: It is the ideal structure for implementing Stacks, Queues, and Graphs due to its flexible pointer-based architecture.

Summary

• A Linked List is a collection of nodes where each element links to the next, offering dynamic memory management.
• It excels in operations involving frequent insertions and deletions compared to standard arrays.
• The Java LinkedList class provides a versatile implementation that supports both list and deque functionalities.
• Important terms to remember: Node, Head, Pointer, Traversal, and Dynamic Allocation.