> For the complete documentation index, see [llms.txt](https://nissan-goldberg.gitbook.io/java101/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nissan-goldberg.gitbook.io/java101/lesson-9-linked-lists/lesson-11.md).

# 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

```java
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

```java
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

![](/files/-MbV8FIZ3sQ7br5wMFD9)

#### Solution:

{% tabs %}
{% tab title="Main" %}

```java
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);
    }
}
```

{% endtab %}

{% tab title="" %}

```java
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;
    }
}
```

{% endtab %}
{% endtabs %}

```
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.

![](https://i.ibb.co/bbQcWyZ/linked-List-Middle.png)

```java
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
    }
```

```java
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

![](/files/-MbV-heWD_MLp57wKxJ6)

Detect if there is cycle in LinkedList

![Detect loop in a linked list - GeeksforGeeks](https://www.geeksforgeeks.org/wp-content/uploads/2009/04/Linked-List-Loop.gif)

**Hint!** you should use the code we use before

I have added a `print` function to show the loop

```java
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

```java
    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");
    }
```

```java
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

```java
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

```java
slow_ptr.next = null;
```

so now

```java
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");
    }
```

```java
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](https://i.ibb.co/dKHgngG/reverse-all-steps.png)

```java
  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;
    }
```

```java
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

```java
    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;
    }
```

```java
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](https://i.ibb.co/drky52z/linked-LIst-even-odds.png)

## 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.&#x20;
   * Change the head pointer to point to the first even node.&#x20;
   * Consider all odd nodes after the first even node and move them to the end.

```java
    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;
    }
```

```java
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](https://i.ibb.co/j3x6L6P/linked-LIst-doubly.png)

### **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.&#x20;