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:

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

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

  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

Solution

Pointer should be at last node (iterate to get there)
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

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.

PreviousLesson 9 - More OOP NextInterface - Intro

Last updated 3 years ago