Linked Lists

Lesson 11

Last Week

• dynamic array (Intlist or Int Container and Polygon or Point Container)

This week

• Scanner

• LinkedList exercises

• Doubly linked list (moves forwards and backwards)

Scanner

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int my_int = scan.nextInt();
        double my_double = scan.nextDouble();
        String my_str = scan.next();

        System.out.println("int:" + my_int);
        System.out.println("double:" + my_double);
        System.out.println("string:" + my_str);

        scan.close();
    }
}

10
3.1415
hello world
int: 10
double: 3.1415
string: hello

LinkedList

advantages of LinkedList

• removal of element in O(n) i.e. very fast

• not contiguous in memory, so can expand

disadvantage of LinkedList

• not contiguous in memory, so its slower to get each node

Basic implementation

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }

    public String toString() {
        return data + "";
    }
}

class LinkedList {
    Node head;

    LinkedList() { head = null; }

    public LinkedList add(int elem) {
        if (head==null)
            head = new Node(elem);
        else{
            Node t = head; //transverse
            while (t.next != null)
                t = t.next;
            Node node = new Node(elem);
            t.next = node;
        }
        return this;
    }

    @Override
    public String toString() {
        Node node = head;
        StringBuilder str = new StringBuilder();

        while (node!=null){
            str.append(node + (node.next!=null ? " ," : ""));
            node = node.next;
        }

        return "LinkedList{" + str +'}';
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        System.out.println(ll);

        ll.add(10).add(7).add(3).add(9);
        System.out.println(ll);
    }
}

LinkedList{}
LinkedList{10 ,7 ,3 ,9}

Test Exercise: Add to an ordered Linked List

Solution:

Main

class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        System.out.println(ll);
        ll.add(1).add(2).add(4);

        ll.add_inorder(3);
        System.out.println(ll);


        ll.add_inorder(5);
        System.out.println(ll);

        ll.add_inorder(0);
        System.out.println(ll);
    }
}

class LinkedList {
    Node head;

    LinkedList() { head = null; }

    //add before

    public LinkedList add_inorder(int elem) {
        if (head==null)
            head = new Node(elem);
        else{
            Node t = head; //transverse

            //if at beginning of list
            if (elem < head.data){
                Node node = new Node(elem);
                node.next = head;
                head = node;
                return this;
            }


            //other cases
            while (t.next != null && t.next.data < elem)
                t = t.next;
            Node node = new Node(elem);
            Node next_node = t.next;

            t.next = node;
            node.next = next_node;

        }
        return this;
    }
}

LinkedList{1 ,2 ,3 ,4}
LinkedList{1 ,2 ,3 ,4 ,5}
LinkedList{0 ,1 ,2 ,3 ,4 ,5}

Exercise: Find the middle element (position) of LinkedList

• DIY: - naïve solution

• Our solution: Find the middle element (position) of LinkedList. You may only iterate through the linkedlist 1 time i.e. O(n)

Solution

The solution is similar to Floyd's cycle finding algorithm

Traverse linked list using two pointers.

• Move one pointer by 1

• Move other pointers by 2

When the fast pointer reaches the end slow pointer will reach the middle of the linked list.

class LinkedList {
    Node head;

    ...

    int middle_elem() {
        Node slow_ptr = head;
        Node fast_ptr = head;

        if (head != null) {
            while (fast_ptr != null && fast_ptr.next != null) {
                fast_ptr = fast_ptr.next.next;
                slow_ptr = slow_ptr.next;
            }
            return slow_ptr.data;
        }
        return -1; //if null
    }

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4).add(5);
        System.out.println(ll);
        System.out.println(ll.middle_elem());
    }
}

LinkedList{1 ,2 ,3 ,4 ,5}
3

Test Exercise: Cycle in LinkedList

Detect if there is cycle in LinkedList

Detect loop in a linked list - GeeksforGeeks

Hint! you should use the code we use before

I have added a print function to show the loop

class LinkedList {
    Node head;
    // ..... code from before

    public void print(){
        Node node = head;

        while (node!=null){
            System.out.print(node + " ");
            node = node.next;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4);
        System.out.println(ll);

        //add cycle
        Node temp = ll.head.next;
        ll.head.next.next.next.next = temp; // 4 -> 2, 4 connected to 2

//        System.out.println(ll); //runs out of heap
        ll.print();

    }
}

1 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 ...

Solution

    void detect_cycle() {
        Node slow_ptr = head;
        Node fast_ptr = head;


        while (slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
            slow_ptr = slow_ptr.next; //increment by 1
            fast_ptr = fast_ptr.next.next; //increment by 2
            if (slow_ptr == fast_ptr) {
                System.out.println("there is a cycle starting from: " + slow_ptr);
                return;
            }
        }
        System.out.println("no cycle");
    }

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4);
        System.out.println(ll);

        //add cycle
        Node temp = ll.head.next;
        ll.head.next.next.next.next = temp; // 4 -> 2, 4 connected to 2


        ll.detect_cycle();
    }
}

LinkedList{1 ,2 ,3 ,4}
there is a cycle starting from: 4

Note: since if the linked list is empty the code will work since in

while (slow_ptr != null && fast_ptr != null && fast_ptr.next != null)

slow_ptr will equal to null and exit the while before checking fast_ptr.next

But how do we remove the the cycle?

Easy just add 1 line of code

slow_ptr.next = null;

so now

void detect_and_remove_cycle() {
        Node slow_ptr = head;
        Node fast_ptr = head;


        while (slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
            slow_ptr = slow_ptr.next; //increment by 1
            fast_ptr = fast_ptr.next.next; //increment by 2
            if (slow_ptr == fast_ptr) {
                System.out.println("there is a cycle starting from: " + slow_ptr);
                slow_ptr.next = null; // <========= added this
                return;
            }
        }
        System.out.println("no cycle");
    }

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4);
        System.out.println(ll);

        //add cycle
        Node temp = ll.head.next;
        ll.head.next.next.next.next = temp; // 4 -> 2, 4 connected to 2


        ll.detect_and_remove_cycle();
        System.out.println(ll);
    }
}

LinkedList{1 ,2 ,3 ,4}
there is a cycle starting from: 4
LinkedList{1 ,2 ,3 ,4}

Exercise: Reverse LinkedList - Iteratively- DIY (15 minutes)

Solution

reverse-all-steps

  LinkedList reverse() {
        Node prev = null;
        Node current = head;
        Node next = head;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        head = prev;
        return this;
    }

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4);
        System.out.println(ll);
        System.out.println(ll.reverse());
    }
}

LinkedList{1 ,2 ,3 ,4}
LinkedList{4 ,3 ,2 ,1}

Exercise: Reverse LinkedList - Recursively

solution

    LinkedList reverseRec(){
        head = reverse_rec(head);
        return this;
    }

    Node reverse_rec(Node head) {
        //Base Case 1:
        if(head == null) 
            return head;

        //Base Case 2: last node or only one node
        if(head.next == null)
            return head;

        Node newHeadNode = reverse_rec(head.next);

        // change references for middle chain
        head.next.next = head;
        head.next = null;

        // send back new head node in every recursion
        return newHeadNode;
    }

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4);
        System.out.println(ll);
        System.out.println(ll.reverseRec());
    }
}

LinkedList{1 ,2 ,3 ,4}
LinkedList{4 ,3 ,2 ,1}

Exercise: Partition LinkedList

all even numbers appear before all the odd numbers in the modified linked list

linked-LIst-even-odds

Solution

1. Pointer should be at last node (iterate to get there)

2. Move all the odd nodes to the end

   • Consider all odd nodes before the first even node and move them to end.

   • Change the head pointer to point to the first even node.

   • Consider all odd nodes after the first even node and move them to the end.

    LinkedList partition_evens_odds() {
        Node end = head;
        Node prev = null;
        Node curr = head;

        // Get pointer to last Node
        while (end.next != null)
            end = end.next;

        Node new_end = end;

        // Consider all odd nodes before getting first even node
        while (curr.data %2 !=0 && curr != end) {
            new_end.next = curr;
            curr = curr.next;
            new_end.next.next = null;
            new_end = new_end.next;
        }

        // do following steps only if there is an even node
        if (curr.data %2 ==0) {
            head = curr;

            // now curr points to first even node
            while (curr != end) {
                if (curr.data % 2 == 0) {
                    prev = curr;
                    curr = curr.next;
                }
                else {
                    prev.next = curr.next;  // Break the link between prev and curr
                    curr.next = null; // Make next of curr as null
                    new_end.next = curr; //Move curr to end
                    new_end = curr; //Make curr as new end of list
                    curr = prev.next; //Update curr pointer
                }
            }
        } else { // We have to set prev before executing rest of this code
            prev = curr;
        }

        if (new_end != end && end.data %2 != 0) {
            prev.next = end.next;
            end.next = null;
            new_end.next = end;
        }
        return this;
    }

public class Main {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.add(1).add(2).add(3).add(4).add(5).add(6).add(7);
        System.out.println(ll);

        System.out.println(ll.partition_evens_odds());
    }
}

LinkedList{1 ,2 ,3 ,4 ,5 ,6 ,7}
LinkedList{2 ,4 ,6 ,1 ,3 ,5 ,7}

Doubly LinkedList

linked-LIst-doubly

Advantages over singly linked list

• can traverse in both forward and backward direction

• and more, so read up

Disadvantages over singly linked list

• takes up more space

• All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers.