> 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. * 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. ```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. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://nissan-goldberg.gitbook.io/java101/lesson-9-linked-lists/lesson-11.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.