Linked Lists
Lesson 11
Last Week
dynamic array (Intlist or Int Container and Polygon or Point Container)
This week
ScannerLinkedList 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: helloLinkedList
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);
}
}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}
3Test 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: 4Note: 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.
Last updated
Was this helpful?