Understanding Linked List and Implementation in Java

What is Linked List??

A linked list is another linear data structure that stores data in a ListNode, and the ListNode has another address that points to its next ListNode.

How to represent a LinkedList?

using the head of the Linked List ListNode head
that means all Linked List Interview Problem is actually traversal problem. Because If we have the head, we can basically extract all the data afterward.

How to traverse a LinkedList?

we dont wnat to lose the address of the head, because we wont be able to visit it afterward. so, we create a variable that allow us traverse the linked list.

ListNode cur = head;
while (cur != null) {
    cur = cur.next;
}

What problems do we need to be extra cautious?

Null-pointer exception, since linked list is using pointer to traverse the list.
Losing the value of head. head = head.next -> will lead to lose the head pointer!

Singly Linked List Implementation

API to Implement:\

get(int index)/searchByValue
addHead/addTail/addIndex
deleteHead/deleteTail/deleteByIndex

public SinglyLinkedList class {
    // how to print a node?
    // if you put System.out.println(new ListNode(1)) -> it will pops up error.
    // just like you want to ompare ListNode(1) && ListNode(2)
    // since they all extend the class Object in Java
    // you have to override the toString method / compare method in order to directly
    // print it out or compare it.

    static class ListNode {
        int value;
        ListNode next;
        public ListNode(int value) {
            this.value = value;
        }
        @Override
            public String toString() {
            return value + “ -> “;
        }
    }

    // field
    ListNode head;
    int size;
    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    // get the value of the index node, index range from 0 to n - 1
    public Integer get(int index) {
        if (index < 0 || index >= size) {
            throw exception;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }

    // return the firstNode that has target value
    public ListNode searchByValue(int value) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.value == value) {
                return cur;
            }
            cur = cur.next;
        }
        return cur; // null
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void printLinkedList() {
        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur); //We implement toString.
            cur = cur.next
        }
    }

    public void addHead(int value) {
        ListNode newHead = new ListNode(value);
        newHead.next = head;
        head = newHead;
        size++;
    }

    public void addTail(int value) {
        if (head == null) {
            addHead(value);
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = new ListNode(value);
        size++;
    }

    public void addIndex(int index, int value) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            addHead(value);
        } else if (index == size) {
            addTail(value);
        } else {
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = new ListNode(value);
            cur = cur.next;
            cur.next = next;
            size++;
        }
    }

    public void deleteHead() {
        if (head == null) {
            return;
        }
        head = head.next;
        size–;
    }

    public void deleteTail() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            deleteHead();
            return;
        }
        ListNode cur = head;
        while (cur.next.next != null) {
            cur = cur.next;
        }
        cur.next = null;
        size--;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            deleteHead();
            return;
        } else if (index == size - 1) {
            deleteTail();
            return;
        } else {
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next;
            size--;
        }
    }

}

Doubly Linked List Implementation

The only difference between Doubly Linked List and Singly Linked List is adding and deleting.

public DoublyLinkedList class {

	static class ListNode {
        int value;
        ListNode next;
        ListNode prev;
        public ListNode(int value) {
            this.value = value;
        }
        @Override
        public String toString() {
            return “<-” + value + “ -> “;
        }
    }

    // field
    ListNode head;
    int size;
    public DoublyLinkedList() {
        head = null;
        size = 0;
    }
    //基本上改跟查 的Code是完全不需要變化
    // get the value of the index node, index range from 0 to n - 1
    public Integer get(int index) {
        if (index < 0 || index >= size) {
            throw exception;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }

    // return the firstNode that has target value
    public ListNode searchByValue(int value) {
        ListNode cur = head;
        while (cur != null) {
        if (cur.value == value) {
            return cur;
        }
        cur = cur.next;
        }
        return cur; // null
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void addHead(int value) {
        ListNode newHead = new ListNode(value);
        //多左一句
        if (head != null) {
            head.prev = newHead;
        }
        newHead.next = head;
        head = newHead;
        size++;
    }

    //増 跟刪除都只係改動左連pointer的方法.
    public void addTail(int value) {
        if (head == null) {
            addHead(value);
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        ListNode newHead = new ListNode(value);
        cur.next = newHead;
        newHead.prev = cur;
        size++;
    }

    public void addIndex(int index, int value) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            addHead(value);
        } else if (index == size) {
            addTail(value);
        } else {
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            ListNode newNode = new ListNode(value);
            cur.next = newNode;
            newNode.prev = cur;

            newNode.next = next;
            next.prev = newNode;
            size++;
        }
    }

    public void deleteHead() {
        if (head == null) {
            return;
        }
        head = head.next;
        head.prev = null;
        size–;
    }

    public void deleteTail() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            deleteHead();
            return;
        }
        ListNode cur = head;
        while (cur.next.next != null) {
            cur = cur.next;
        }
        cur.next.prev = null;
        cur.next = null;
        size--;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            deleteHead();
            return;
        } else if (index == size - 1) {
            deleteTail();
            return;
        } else {
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            ListNode delete = prev.next;
            ListNode next = delete.next;

            delete.prev = null;
            delete.next = null;

            prev.next = next;
            next.prev = prev;

            size--;
        }
    }
}

Circular Linked List Implementation

The only difference between SinglyLinkedList and CircularLinkedList is the terminate condition in the while loop, and always look for the tail in adding and deleting head/tail.

public CircularLinkedList class {
    static class ListNode {
        int value;
        ListNode next;
        public ListNode(int value) {
            this.value = value;
        }
        @Override
        public String toString() {
            return value + “ -> “;
        }
    }

    ListNode head;
    int size;
    public CircularLinkedList () {
        head = null;
        size = 0;
    }

    // get the value of the index node, index range from 0 to n - 1
    public Integer get(int index) {
        if (index < 0 || index >= size) {
            throw exception;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.value;
    }

    // return the firstNode that has target value
    public ListNode searchByValue(int value) {
        ListNode cur = head;
        while (cur != head) {
            if (cur.value == value) {
                return cur;
            }
            cur = cur.next;
        }
        return null; // null
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void addHead(int value) {
        ListNode newHead = new ListNode(value);
        newHead.next = head;
        ListNode cur = head;
        while (cur.next != head) {
            cur = cur.next;
        }
        cur.next = newHead;
        head = newHead;
        size++;
    }

    public void addTail(int value) {
        if (head == null) {
            addHead(value);
        }
        ListNode cur = head;
        while (cur.next != head) {
            cur = cur.next;
        }
        cur.next = new ListNode(value);
        cur = cur.next;
        cur.next = head;
        size++;
    }

    public void addIndex(int index, int value) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            addHead(value);
        } else if (index == size) {
            addTail(value);
        } else {
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = new ListNode(value);
            cur = cur.next;
            cur.next = next;
            size++;
        }
    }

    public void deleteHead() {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        // find the last pointer;
        while (cur.next != head) {
            cur = cur.next;
        }
        head = head.next;
        cur.next = head;
        size–;
    }

    public void deleteTail() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            deleteHead();
            return;
        }
        ListNode cur = head;
        while (cur.next.next != head) {
            cur = cur.next;
        }
        cur.next = head;
        size--;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        if (index == 0) {
            deleteHead();
        return;
        } else if (index == size - 1) {
            deleteTail();
        return;
        } else {
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next;
            size--;
        }
    }
}

Problem Number	Problem	Solution
1	Insert In Sorted Linked List
2	Merge Two Sorted Lists
3	Remove Linked List Elements
4	Middle of the Linked List
5	Linked List Cycle

Problem Number	Problem	Solution
1	Delete Node in a Linked List
2	Delete the Middle Node of a Linked List
3	Remove Nth Node From End of List

Problem Number	Problem	Solution
1	Reverse Linked List
2	Reverse Linked List II
3	Swap Nodes in Pairs

Problem Number	Problem	Solution
1	Add Two Numbers
2	Add Two Numbers II
3	Plus One Linked List
4	Add Two Polynomials Represented as Linked Lists

Problem Number	Problem	Solution
1	Palindrome Linked List
2	Partition List
3	Reorder List

Problem Number	Problem	Solution
1	Merge Sort List
2	Insertion Sort Linked List
3	Selection Sort Linked List
3	Quick Sort Linked List