DSA in Java Linked-Lists

Linked Lists

A Linked List is a linear dynamic data structure that consists of a sequence of elements, called nodes, where each node contains two parts:

Data Field — Stores the actual value.

Pointer (Link) Field — Contains the address/reference of the next node in the sequence.

Unlike arrays, linked lists do not store elements in contiguous memory locations. Each node points to the next, forming a chain-like structure.

Structure of a Node (in C):

struct Node {

    int data;

    struct Node* next;

};

Types of Linked Lists:

Singly Linked List

A Singly Linked List is a type of linear data structure where each node points only to its immediate next node, thus forming a unidirectional chain. The list terminates at the node which points to NULL, indicating the end of the list.

Structure of a Node:

Each node in a singly linked list contains two parts:

1. Data Field: Stores the actual value.

2. Next Pointer Field: Holds the address of the next node in the list.

Node Definition in C:

struct Node {

    int data;

    struct Node* next;

};

Basic Operations on Singly Linked List:

Insertion:

At the Beginning
At the End
At a Specific Position

Deletion:

From the Beginning
From the End
Of a Specific Node

Traversal:

Visit each node one by one and process its data.

Searching:

Locate a node containing a given value by linear traversal.

Example Program (C Language):

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* next;

};

void printList(struct Node* n) {

    while (n != NULL) {

        printf(“%d -> “, n->data);

        n = n->next;

    }

    printf(“NULL\n”);

}

int main() {

    struct Node* head = NULL;

    struct Node* second = NULL;

    struct Node* third = NULL;

    // Allocate memory

    head = (struct Node*)malloc(sizeof(struct Node));

    second = (struct Node*)malloc(sizeof(struct Node));

    third = (struct Node*)malloc(sizeof(struct Node));

    // Assign data and links

    head->data = 10;

    head->next = second;

    second->data = 20;

    second->next = third;

    third->data = 30;

    third->next = NULL;

    printList(head);

    return 0;

}

Advantages of Singly Linked List:

Dynamic size: Memory is allocated at runtime.
Efficient Insertion/Deletion: No need to shift elements like in arrays.
Memory Utilization: Grows as needed without wastage.

Limitations of Singly Linked List:

Unidirectional Traversal: Cannot go backwards.
No Direct Access: Random access is not possible; traversal is mandatory.
Extra Memory: Requires additional space for the pointer field in every node.

Applications of Singly Linked List:

Stacks, Queues Implementation
Symbol Tables in Compilers
Dynamic Memory Allocation
Polynomial Arithmetic

Diagram of Singly Linked List:

[Data|Next] → [Data|Next] → [Data|Next] → NULL

Doubly Linked List

A Doubly Linked List is an advanced type of linked list where each node contains two pointers —

1. One pointing to the next node in the sequence.

2. Another pointing to the previous node.

Thus, traversal is possible in both forward and backward directions, unlike a singly linked list.

Structure of a Node:

Each node in a doubly linked list contains three parts:

1. Data Field: Stores the actual data.

2. Pointer to Previous Node: Points to the previous node in the list.

3. Pointer to Next Node: Points to the next node in the list.

Node Definition in C:

struct Node {

    int data;

    struct Node* prev;

    struct Node* next;

};

Basic Operations on Doubly Linked List:

Insertion:

At the Beginning
At the End
At a Specific Position

Deletion:

From the Beginning
From the End
Of a Specific Node

Traversal:

Forward Direction (Head to Tail)
Backward Direction (Tail to Head)

Searching:

Can be performed in both directions for increased efficiency.

Example Program (C Language):

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* prev;

    struct Node* next;

};

void printList(struct Node* node) {

    struct Node* last;

    printf(“Forward Traversal: “);

    while (node != NULL) {

        printf(“%d -> “, node->data);

        last = node;

        node = node->next;

    }

    printf(“NULL\n”);

    printf(“Backward Traversal: “);

    while (last != NULL) {

        printf(“%d -> “, last->data);

        last = last->prev;

    }

    printf(“NULL\n”);

}

int main() {

    struct Node* head = NULL;

    struct Node* second = NULL;

    struct Node* third = NULL;

    // Allocate nodes

    head = (struct Node*)malloc(sizeof(struct Node));

    second = (struct Node*)malloc(sizeof(struct Node));

    third = (struct Node*)malloc(sizeof(struct Node));

    // Initialize data and links

    head->data = 10;

    head->prev = NULL;

    head->next = second;

    second->data = 20;

    second->prev = head;

    second->next = third;

    third->data = 30;

    third->prev = second;

    third->next = NULL;

    printList(head);

    return 0;

}

Advantages of Doubly Linked List:

Bidirectional Traversal: Can move both forward and backward.
Efficient Deletion/Insertion: Can delete a given node directly without traversing from the head.
Flexibility: Useful in complex data structures like navigation systems, undo-redo systems.

Limitations of Doubly Linked List:

Extra Memory Overhead: Requires extra space for one additional pointer (prev) in each node.
Slightly Complex Implementation: More pointer handling than singly linked lists.
Increased Processing Time: Extra pointer updates during insertion and deletion.

Applications of Doubly Linked List:

Navigation systems (Forward/Backward browsing)
Undo/Redo functionality in word processors

Implementing complex data structures such as Deques
Music/Photo viewers with previous and next features

Diagram of Doubly Linked List:

NULL ← [Prev|Data|Next] ⇄ [Prev|Data|Next] ⇄ [Prev|Data|Next] → NULL

Circular Lists (Array & Linked Representation)

A Circular List is a linear data structure in which the last element is connected back to the first element, forming a circle-like structure.
This structure allows continuous traversal without checking the end of the list.

1. Circular Array Representation

Concept:

In a circular array, the last position is conceptually connected to the first position.
This is particularly useful in implementing circular queues.

Index calculation is done using the formula:

index = (index + 1) % size

Operations in Circular Array:

1. Insertion: At the position (rear + 1) % size.

2. Deletion: From the position (front + 1) % size.

3. Traversal: From front to rear using modulo arithmetic.

Limitations of Circular Array:

Fixed Size — cannot grow beyond its declared capacity.
Possible wastage of space if not carefully managed.

2. Circular Linked List Representation

Concept:

In a circular linked list, the next pointer of the last node points back to the first node, forming a continuous loop.
It can be implemented as either:

• Singly Circular Linked List

• Doubly Circular Linked List

Singly Circular Linked List:

• Each node points to the next node.

• The last node points to the head (first node).

Structure:

struct Node {

    int data;

    struct Node* next;

};

Diagram:

[Data|Next] → [Data|Next] → [Data|Next] → back to first node

Doubly Circular Linked List:

• Each node has two pointers:
  • One to the next node.

  • One to the previous node.

• First and last nodes are connected in both directions.

Structure:

struct Node {

    int data;

    struct Node* prev;

    struct Node* next;

};

Diagram:

First Node ⇄ Node2 ⇄ Node3 ⇄ … ⇄ Last Node ⇄ back to First Node

Basic Operations on Circular Linked List:

1. Insertion: At beginning, end, or any position.

2. Deletion: Remove any specific node or the entire list.

3. Traversal: Possible from any node due to circular connection.

Advantages of Circular Lists:

Efficient Continuous Traversal: Can start from any node and reach all others without stopping.
No NULL Pointers: Eliminates end-of-list checks.
Ideal for applications such as task scheduling, buffering, round-robin CPU scheduling.

Limitations of Circular Lists:

Complex Implementation: Requires careful pointer management.
Infinite Loops Possible: If termination conditions are not set properly, traversal may never end.

Applications of Circular Lists:

Circular Queues (in array form)
Buffer Management Systems
Round-Robin Scheduling in Operating Systems
Music or Photo Viewer Navigation
Hot Potato Game Simulation

Stack Representation using Lists

A Stack is a linear data structure that follows the Last In First Out (LIFO) principle.
When implemented using a Linked List, the elements of the stack are stored as nodes rather than in a contiguous memory block like an array.

Each node contains:

1. Data Field: Holds the actual value.

2. Pointer Field: Points to the next node in the list.

The top of the stack is represented by the head (first node) of the linked list.

Why use Lists for Stack Implementation?

Dynamic Size: Grows and shrinks at runtime without the need to define a fixed size, unlike arrays.
Efficient Push/Pop Operations: Performed at the beginning (head) of the list for constant time complexity O(1).
Memory Utilization: Allocates memory only when needed.

Structure of Node in C (for Stack using List):

struct Node {

    int data;

    struct Node* next;

};

Basic Operations:

Push (Insert an Element):

• A new node is created and inserted at the beginning of the list (top of the stack).

void push(struct Node** top, int val) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = val;

    newNode->next = *top;

    *top = newNode;

}

Pop (Remove the Top Element):

The top node is removed and its memory is freed.

int pop(struct Node** top) {

    if (*top == NULL) {

        printf(“Stack Underflow\n”);

        return -1;

    }

    struct Node* temp = *top;

    int popped = temp->data;

    *top = temp->next;

    free(temp);

    return popped;

}

Peek (Retrieve the Top Element):

int peek(struct Node* top) {

    if (top == NULL) {

        printf(“Stack is empty\n”);

        return -1;

    }

    return top->data;

}

isEmpty (Check if Stack is Empty):

int isEmpty(struct Node* top) {

    return top == NULL;

}

Advantages of Stack Using List:

No Fixed Size Limitation: Unlike arrays, the stack can grow as long as memory allows.
Efficient Memory Use: Memory is allocated as needed.
No Overflow (unless memory is full): The stack does not overflow due to size restrictions.

Limitations:

Extra Memory Overhead: Every node requires additional space for the pointer field.
More Complex Implementation: Involves dynamic memory allocation and pointer manipulation.
Slightly Slower Access Time: Due to non-contiguous storage.

Applications:

Expression Evaluation (Postfix/Prefix)
Undo/Redo Features
Recursive Function Call Management
Syntax Parsing in Compilers
Depth-First Search (DFS) in Graph Algorithms

Diagram Representation of Stack Using List:

Top → [Data|Next] → [Data|Next] → [Data|Next] → NULL

Self-Organizing Lists:

A Self-Organizing List is a type of linear list (usually implemented using linked lists) which rearranges its elements automatically based on how frequently or recently they are accessed.

The main aim of a self-organizing list is to improve search efficiency by moving frequently accessed elements closer to the front of the list, reducing the average search time.

Why Self-Organizing Lists?

In standard linked lists, searching for an element requires traversing the list, which can be costly (O(n) time complexity).
Self-organizing lists reduce this cost by dynamically reordering the list to bring frequently accessed elements near the head.

Commonly Used Heuristics (Rearrangement Strategies):

Move-To-Front (MTF) Rule:

• Whenever an element is accessed (searched or used), it is moved to the front (head) of the list.

• Very simple and effective if a small number of elements are accessed repeatedly.

Transpose Rule:

• When an element is accessed, it is swapped with its immediate predecessor.

• Gradually moves frequently accessed elements closer to the front without sudden drastic changes.

Count Rule (Frequency Count):

• Each node maintains a counter of how many times it has been accessed.

• After every access, the node is repositioned so that the list is sorted in non-increasing order of counts.

Advantages of Self-Organizing Lists:

Improved Search Performance over time for frequently accessed elements.
Simple Implementation especially for Move-To-Front heuristic.
Dynamic Adaptation to usage patterns — the list reorganizes itself based on actual usage.

Limitations of Self-Organizing Lists:

Increased Overhead: Each access may involve moving nodes or updating counters.
Not Useful for Uniform Access: If all elements are accessed equally, reordering gives no benefit.
Less Effective for Short Lists: Overhead might outweigh benefits if the list is very small.

Applications of Self-Organizing Lists:

Caching Systems (LRU, MRU Algorithms)
Symbol Tables in Compilers
Data Compression (Move-To-Front Transform)
Dynamic Search Tables
Frequently accessed data repositories (like user favorites or search history)

Simple Example: Move-To-Front (MTF) in C:

struct Node {

    int data;

    struct Node* next;

};

struct Node* moveToFront(struct Node* head, int key) {

    if (head == NULL || head->data == key) return head;

    struct Node* prev = NULL;

    struct Node* curr = head;

    while (curr != NULL && curr->data != key) {

        prev = curr;

        curr = curr->next;

    }

    if (curr == NULL) return head; // Key not found

    // Move curr to front

    prev->next = curr->next;

    curr->next = head;

    head = curr;

    return head;

}

Diagram Representation (Move-To-Front):

Before Accessing Element 25:

10 → 15 → 25 → 30 → NULL

After Accessing Element 25:

25 → 10 → 15 → 30 → NULL

Skip Lists:

A Skip List is an advanced data structure that allows fast search, insertion, and deletion operations within an ordered sequence of elements.
It is a probabilistic alternative to balanced binary search trees and provides expected O(log n) time complexity for these operations.

Basic Concept:

A Skip List is essentially a multi-level linked list where each level acts as an “express lane” to skip over multiple elements, reducing the number of comparisons required to find an element.

The lowest level (Level 0) contains all the elements (like a simple sorted linked list). Higher levels contain a subset of the elements to allow faster jumps during search.

Structure:

• Each node contains:
  1. Data/Key Field

  2. Multiple Forward Pointers (one for each level the node belongs to)

Node Definition in C (conceptually):

struct Node {

    int key;

    struct Node** forward;  // array of pointers to next nodes at each level

};

Operations and Their Time Complexities:

Working Principle:

1. Search:
   Start at the highest level and move forward until you reach a node with a key greater than or equal to the target key, then drop down one level and repeat.

2. Insertion:
   • Determine random level for the new node.

   • Insert node in all appropriate levels maintaining the sorted order.

3. Deletion:
   • Similar to search, locate node and remove all forward references.

Advantages of Skip Lists:

Simplicity: Easier to implement compared to balanced trees.
Probabilistic Balance: Automatically balances with random levels, no need for complex re-balancing.
Efficient Searching: Provides logarithmic search times similar to AVL or Red-Black Trees.

Limitations:

Extra Memory Overhead: Requires multiple forward pointers in each node.
Randomization Dependent: Performance depends on the randomness of node levels; in worst-case scenarios, time complexity can degrade to O(n).
Complex Insertion/Deletion: More pointers to manage during insertions and deletions.

Applications of Skip Lists:

In-Memory Databases (e.g., Redis uses Skip Lists)
Concurrent Data Structures (Skip Lists perform well in multithreaded environments)
Ordered Maps and Sets
Priority Queues
Indexing for Distributed Systems

Skip List Representation (Simplified):

Level 3:      5 ——————–> 25

Level 2:      5 ——–> 15 ——-> 25

Level 1:      5 -> 10 -> 15 -> 20 -> 25

• Higher levels allow fast skipping over many nodes.