Linked List for Beginners

Why do we need Linked List?

Linked lists are essential because they provide a dynamic and memory-efficient data structure that excels at accommodating changing data sizes and facilitating efficient insertions and deletions. Unlike arrays, linked lists don't require contiguous memory allocation, enabling flexible memory usage and minimizing wastage.

Use of LinkedList?

1. Text Editor Undo History: Linked lists store previous versions of text to enable undo and redo operations efficiently.

2. GPS Route Navigation: Linked lists represent a series of waypoints for navigation, allowing easy addition and removal of destinations.

3. Bank Transaction History: Linked lists track transaction records, enabling organized storage and retrieval of account activity.

4. Web Browser Tabs: Linked lists store open tabs for swift tab switching and addition of new tabs without disturbing others.

5. Video Streaming Buffer: Linked lists hold segments of videos to provide smooth streaming by loading and discarding parts as needed.

6. Contact List on Phones: Linked lists store contacts, allowing easy insertion, deletion, and modification of contact details.

7. Playlist of Podcast Episodes: Linked lists organize podcast episodes, letting users manage playback sequence and updates.

What is a Linked List?

A linked list is a linear data structure consisting of a sequence of elements, where each element is represented by a node. Each node contains two parts: the data it holds and a reference (or link) to the next node in the sequence. The last node typically points to null, indicating the end of the list.

Types of Linked Lists

There are several types of linked lists, each with its own characteristics:

1. Singly Linked List: In a singly linked list, each node points only to the next node in the list. It's the simplest form of a linked list.

2. Doubly Linked List: In a doubly linked list, each node contains references to both the next and the previous nodes. This allows for efficient traversal in both directions.

3. Circular Linked List: A circular linked list forms a loop, where the last node points back to the first node, creating a closed cycle.

Advantages of Linked Lists

Linked lists offer several advantages over other data structures, such as arrays:

1. Dynamic Size: Linked lists can grow or shrink dynamically, as nodes can be added or removed without the need to allocate a fixed amount of memory upfront.

2. Insertions and Deletions: Insertions and deletions in linked lists are often faster than arrays, especially when dealing with elements in the middle of the list.

3. Memory Efficiency: Linked lists use memory more efficiently than arrays, as they only require memory for the data and the pointers, rather than allocating a continuous block.

Singly LinkList Code:

Operations : Insert ,Delete ,Display List

package LinkList;

public class LL {

    private Node head;
    private Node tail;

    private int size;

    public LL() {
        this.size = 0;
    }

    // insertFirst
    public void insertFirst(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;

        if (tail == null) {
            tail = head;
        }

        size += 1;
    }

    // insertLast
    public void insertLast(int val) {
        Node node = new Node(val);
        if (tail == null) {
            insertFirst(val);
            return;
        }
        tail.next = node;
        tail = node;
        size++;
    }

    // insert
    public void insert(int val, int index) {
        if (index == 0) {
            insertFirst(val);
            return;
        }
        if (index == size) {
            insertLast(val);
            return;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        Node node = new Node(val, temp.next);
        temp.next = node;

        size++;
    }

    // delete last
    public int deleteLast() {
        if (size <= 1) {
            return deleteFirst();
        }
        Node secondLast = get(size - 2);
        int val = tail.value;
        tail = secondLast;
        tail.next = null;
        return val;
    }

    // find the node from the given value
    public Node find(int value) {
        Node node = head;
        while (node != null) {
            if (node.value == value) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    public Node get(int index) {
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    // delete first element
    public int deleteFirst() {
        int val = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return val;
    }

    // delete from any index
    public int delete(int index) {
        if (index == 0) {
            return deleteFirst();
        }
        if (index == size - 1) {
            return deleteLast();
        }
        Node prev = get(index - 1);
        int val = prev.next.value;
        prev.next = prev.next.next;

        return val;
    }

    // display
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.value + "->");
            temp = temp.next;
        }
        System.out.println("END");
    }

    private class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

package LinkList;

public class Main {
    public static void main(String[] args) {

        LL list = new LL();
        list.insertFirst(5);
        list.insertFirst(6);
        list.insertFirst(7);
        list.insertFirst(8);
        list.insertLast(3);
        list.insert(100, 2);
        list.display();
        System.out.println(list.deleteFirst());
        list.display();
        System.out.println(list.deleteLast());
        list.display();
        System.out.println(list.delete(2));
        list.display();
}
}

YOU Should Watch this as a bigneer...