Middle Element of Linked List

Approach

If we do not know the size of the linked list prior to finding the middle element, then our approach would be to use two pointers to traverse the list.
One pointer, the fast pointer, would move twice as fast as the the other pointer.  So if the slow pointer traverses one node per iterations, the fast pointer would traverse two nodes in the same time.
When the fast pointer reached the end of the list, the slow pointer would be in the middle.
This allows us to find the middle element in a running time of O(n).

      public Node<Type> printMiddle(Node<Type> head) {  
           Node<Type> slowPointer = head;  
           Node<Type> fastPointer = head;  
           while (fastPointer != null && fastPointer.next != null) {  
                slowPointer = slowPointer.next;  
                fastPointer = fastPointer.next.next;  
           }  
           System.out.println(slowPointer.data);  
           return slowPointer;  
      }  

Given only a pointer to a single node in a singly linked list how do you delete it

Approach

• If we don't have the pointer to the previous node, and don't have the head pointer to be able to get to the previous node, then our approach is to copy the contents of the node that comes after the node to be deleted into the current node.
• If the node we have to delete is the last node, then we won't be able to delete it.  Our only other option in this case is to make this node a "dummy node".
• This takes constant time O(1) since we don't have to traverse the list to get the node previous to the node to be deleted.

      public boolean removeSpecific(Node refNode) {  
           if (refNode == null || refNode.next == null)  
                return false;  
           Node next = refNode.next;  
           refNode.data = next.data;  
           refNode.next = next.next;  
           return true;  
      }  

Reverse a Linked List

This can be achieved either iteratively or recursively.

Iterative

1. We consider 3 nodes at the time, namely a current node, a node that comes before it and a node that comes after it.
2. We currently have a link between from previous->current->next.  We alter pointers in such a way that current points to previous (previous<-current).  
3. We then reset the pointers current and previous to point to their respective next nodes
4. We repeat till current is null (we've reached the end of the list.
5. Once we're done resetting all the pointers, previous will point to the last element.  We set this as the new head of the list.

      public Node<Type> reverse(Node<Type> head)  
      {  
           Node<Type> current=head;  
           Node<Type> previous=null,next=null;  
           while(current!=null)  
           {  
                next=current.next;  
                current.next=previous;  
                previous=current;  
                current=next;  
           }  
           head=previous;  
           return head;  
      }  

This runs in O(N) because we go through the entire list once while doing the reversal.

Recursive

1. In the recursive solution, we basically traverse till the end of the list.
2. Once we've reached the last element, we can set this as the new head.
3. For all the rest of the recursive iterations, we now have to reset two links.  We have to make current point to previous and break the link between previous and current.

      public void reverseRecurse(Node<Type> current)  
      {  
           if(current==null )  
                return;  
           if(current.next==null)  
           {  
                this.head=current;  
                return;  
           }  
           reverseRecurse(current.next);  
           current.next.next=current;  
           current.next=null;  
      }  

This implementation requires O(n) because it has to go through the entire list once, but also requires O(n) space in terms of the stack frames used for the recursion.

Complete Implementation

 public class LinkedListReverse<Type> {  
      private Node<Type> head;  
      public static class Node<Type> {  
           Type data;  
           Node<Type> next;  
           public Node(Type data) {  
                this.data = data;  
                this.next = null;  
           }  
      }  
      public LinkedListReverse() {  
           head = null;  
      }  
      public void push(Type item) {  
           Node<Type> newNode = new Node<Type>(item);  
           newNode.next = head;  
           head = newNode;  
      }  
      public void print(Node<Type> head) {  
           while (head != null) {  
                System.out.print(head.data + ",");  
                head = head.next;  
           }  
           System.out.println();  
      }  
      public Node<Type> reverse(Node<Type> head) {  
           Node<Type> current = head;  
           Node<Type> previous = null, next = null;  
           while (current != null) {  
                next = current.next;  
                current.next = previous;  
                previous = current;  
                current = next;  
           }  
           head = previous;  
           return head;  
      }  
      public void reverseRecurse(Node<Type> current) {  
           if (current == null)  
                return;  
           if (current.next == null) {  
                this.head = current;  
                return;  
           }  
           reverseRecurse(current.next);  
           current.next.next = current;  
           current.next = null;  
      }  
      public static void main(String args[]) {  
           LinkedListReverse<Integer> list = new LinkedListReverse<Integer>();  
           list.push(1);  
           list.push(2);  
           list.push(3);  
           list.push(4);  
           list.push(5);  
           list.print(list.head);  
           list.head = list.reverse(list.head);  
           list.print(list.head);  
           list.reverseRecurse(list.head);  
           list.print(list.head);  
      }  
 }  

Sample Output

5,4,3,2,1,

1,2,3,4,5,

5,4,3,2,1,

Linked List Deletion

Deletion by Key

• We traverse through the linked list looking for the key
• We maintain a pointer to the node previous to the match
• If the head is a match we simply reset the head pointer
• If another node is a match, we set its previous node to point to the node after the match node

      public void remove(Type item) {  
           Node previous = null;  
           Node current = head;  
           if (head.data.equals(item)) {  
                head = head.next;  
                return;  
           }  
           while (current != null && !current.data.equals(item)) {  
                previous = current;  
                current = current.next;  
           }  
           if (current == null)  
                return;  
           previous.next = current.next;  
      }  

Deletion by Node

Here we match by node and not by key. 
      public void remove(Node refNode)  
      {  
           Node previous = null;  
           Node current = head;  
           if (head.equals(refNode)) {  
                head = head.next;  
                return;  
           }  
           while (current != null && !current.equals(refNode)) {  
                previous = current;  
                current = current.next;  
           }  
           if (current == null)  
                return;  
           previous.next = current.next;  
      }  

Linked List Traversal

Traversing from start to end

Traversal involves visiting every node in the list.
Printing the list requires this sort of traversal.
In a singly linked list we traverse from the head node to the end of the list.

 public void printList(Node head) {  
           while(head!=null)  
           {  
                System.out.print(head.data+",");  
                head=head.next;  
           }  
           System.out.println();  
      }  

This takes linear time O(N) since we need to visit each node in the list.

Traversing in Reverse Order

We can achieve this through recursion.  We basically traverse to the end of the list and then recursively print out till the head.

      public void reversePrint(Node head) {  
           if (head == null)  
                return;  
           reversePrint(head.next);  
           System.out.print(head.data + ", ");  
      }  

Linked List - Java Implementation

Node Definition

      public class Node {  
           private Type data;  
           private Node next;  
           public Node(Type data, Node next) {  
                this.data = data;  
                this.next = next;  
           }  
      }  

Class Definition

 public class LinkedList<Type> implements Iterable<Type> {  
      private Node head;  
      public class Node {  
           private Type data;  
           private Node next;  
           public Node(Type data, Node next) {  
                this.data = data;  
                this.next = next;  
           }  
      }  
      public LinkedList() {  
           head = null;  
      }
}  

Linked List Insertion

There are 3 possible ways to insert a new element into an existing linked list.

1. We can insert in the front (push)
2. We can insert at the end (append)
3. We can insert in between 2 nodes

1. Push Insert

• Inserting in the front of a linked list is also called the push operation.
• If you imagine a stack of plates and want to add another plate to it, you'll always add it to the top of pile of plates.  So when a list represents a stack of plates, the push operation is when the insert always happens in the front of the list.

Steps:

1. Create a new Node to hold the new element to be inserted
2. Set the next pointer of the new node to point to the current head of the list
3. Now make this new node the head of the list

      // Push  
      public void push(Type item) {  
           Node newNode = new Node(item, null);  
           newNode.next = head;  
           head = newNode;  
      }  

2. Append Insert

• Inserting in the tail or end of a linked list is also called the append operation.
• If you imagine yourself joining a queue of people, you'll join at the end of the queue.  So when a list represents a queue, the append operation is when the insert always happens in the end of the list.

Steps:

1. Create a new Node to hold the new element to be inserted
2. Create a pointer to traverse the list to the end
3. Check if the list is empty (head is null) in which case make the head as the new node and quit
4. If the list isn't empty, use the pointer to traverse to the end of the list.  The last element will have its next pointer point to null
5. Make the last node point to newNode

      // Append  
      public void append(Type item) {  
           Node current = head;  
           Node newNode = new Node(item, null);  
           if (head == null) {  
                head = newNode;  
                return;  
           }  
           while (current.next != null)  
                current = current.next;  
           current.next = newNode;  
      }  

3. Insert After Node

• Inserting between 2 nodes given a reference node involves traversal till the node is located and then insertion after that reference node.

Steps:

1. Create a new Node to hold the new element to be inserted
2. Make sure the reference Node after which insertion should take place is not null
3. Reset the newNode next pointer to point to the reference node's next pointer (In the figure the reference node is 4 ->2.  We want to make 5 -> 2 and 4 -> 5.
4. Reset reference node's pointer to point to newNode.

      // Insert after  
      public void insertAfter(Node refNode, Type item) {  
           if (refNode == null)  
                return;  
           Node newNode = new Node(item, null);  
           newNode.next = refNode.next;  
           refNode.next = newNode;  
      }  

Linked List

Linked lists can be viewed as a collection of nodes which do not necessarily occupy continuous locations in memory.

• Each node typically contains the element and a link to the next node in the list which is referred to as next.  The last node's next link refers to null.
• We store the starting node of the list to allow for easy traversal.
• A singly linked list only has one pointer to the next element in the list.
• A doubly linked list has two pointers for each node, one pointing to the next element and one pointing to the previous element in the list.

Linked List Node

Advantages of Linked Lists over arrays:

1. Easy insertion and deletion - can be achieved in constant time O(1).

2. No need to know how much memory to allocate beforehand.  The list grows dynamically.

3. No need to pre allocate memory beforehand and potentially have wasted spaces or the need to increase the size later like arrays.

Disadvantages over arrays:

1. Traversal takes linear time O(N) because access by position/index isn't possible

2. Need extra memory to store pointer to next element in the list.