Algorithm and Data Structure Basics - Linked List

  |   Source

Reference List

Efficiency of Linked List

Insertion and Deletion at the head of linked list is really quick. It need O(1) time complexity.

Compare with Array

Both array and linked list need O(N) time complexity for searching and insertion/deletion to certain node. However, linked list may still be a better option, because it does not need to move anything when it does these operations. Linked list can save lots of time expecially if there exists a large amount of elements.

Linked list is also better at saving space. Linked list also gives flexibility of expanding size.

So if we don't know exact size of data, linked list can be a better option comparing to array.

ADT

You can create stack using linked list. When you create push and pop method, just insert/remove first element from head of linked list.

Insertion Sort for Sorted Linked List

If you have a un-sorted array, you can take all elements out, and insert them to a sorted linked list. Then after you deleting all elements and re-put them to array, this array will become a sorted one.

/*
  Insert Node at the end of a linked list
  head pointer input could be NULL as well for empty list
  Node is defined as
  class Node {
     int data;
     Node next;
  }
*/
class SortedList{
  private Node head; //head of linked list

  public SortedList(){
    head = null;
    //constructor for empty list
  }

  //Constructor for taking a array of nodes as parameter
  public SortedList(Node[] nodearray){
    head = null;
    for(int j=0; j<nodearray.length; j++){
      insert(nodearray[j]);
    }
  }

  public void insert(Node insertNode){
    Node currentNode = new Node();
    currentNode = head;

    if(currentNode.next == null){
      //Skip this process. Insert insertNode if there is only one node in linked list
    }

    //Do insertion sort. Left most is always the largest one
    while(currentNode.next != null && insertNode.data > currentNode.next.data){
      Node temp = currentNode.next;
      currentNode.next = insertNode;
      insertNode.next = temp;
      currentNode = currentNode.next;
    }
  }
}

Iterator

Iterator is used as a reference so that it can point to any node in linked list, in order to find and change certain node.

Class of Iterator
class ListIterator(){
  private Node current; //current node in linked list that iterator is pointing to
  //private Node previous;  for doubly linked list
  private LinkedList currentList; //current linked list
}
Main Class

You may have different iterators for one linked list. Each iterator points to a certain node.

public static void main(...){
  LinkedList l = new LinkedList();
  ListIterator iter = l.getIterator();
  Node point = iter.getCurrent(); //get current node in iterator
  //point.next...
}
Possible Methods

You can add following possible methods to your iterator:

  • reset(): Make iterator point to head of linked list

  • nextLink(): Make iterator point to next node

  • getCurrent(): return current node

  • atEnd(): return true if iterator is pointing to end of linked list

  • insertAfter()/insertBefore()/deletCurretn(): operation for insertion/deletion

Merge Two Sorted Linked Lists/Merge Sort Single Linked List

You can check Merge Two Sorted Linked Lists on hackerrank.com.

Idea

To merge two sorted linked lists, you just need to create a new node and always get the smaller node from two source linked lists. Every time a node is passed, move header to next node.

To merge sort a single linked list, you need to have two pointer: p and f. Every time if p points to next node, f should point to the node after the next one. In this case, when f finish walking through a certain part of linked list, p is on the half of that linked list.

Recursively call the method above for first part(start from origin head) of linked list and second part(start from p) for division process. Then merge result using same method as merging two sorted linked lists

Code
Code for merging two sorted linked list, on hackerrank.com:
/*
  Insert Node at the end of a linked list
  head pointer input could be NULL as well for empty list
  Node is defined as
  class Node {
     int data;
     Node next;
  }
*/

Node MergeLists(Node headA, Node headB) {
        Node c = new Node();
        Node result = c;

        while (headA != null && headB != null ){
            if (headA.data <= headB.data){
                c.next = headA;
                headA = headA.next;
            }else {
                c.next = headB;
                headB = headB.next;
            }
            c = c.next;
        }

        if(headA == null){
            c.next = headB;
        }else{
            c.next = headA;
        }

        return result.next;
        //result is a empty node. result.next (i.e. c.next) is the start of new linked list
    }
Code for merging single linked list, divide part:
/*
  Insert Node at the end of a linked list
  head pointer input could be NULL as well for empty list
  Node is defined as
  class Node {
     int data;
     Node next;
  }
*/
public class Solution {
public Node sortList(Node head) {

    if (head == null || head.next == null){
        return head;
    }

    ListNode p = head;
    ListNode f = head.next;

    while ( f.next !=null && f.next.next !=null ){
        p = p.next;
        f = f.next.next;
    }

    //Perform division to second half of linked list
    ListNode h2 = sortList(p.next);
    p.next = null;

    /*
    Perform divide to first half of linked list (starting from head),then merge division result.
    'MergeLists' method is the code in first part
    */
    return MergeLists(sortList(head),h2);
}

Flatten a Doubly Linked List

This is a question from the book Programming Interview Exposed. Following graph is a example of a doubly linked list, from this post:

../images/articles/2015/algorithm/double_linkedlist.png

Idea

Generally, each child linked list can be flattened as a single linked list, which can be appended to the end of result linked list. Each time you encounter a node with a child, append the child (and thus the child list) to the end of the first level and update the tail pointer.

This is a description of algorithm:

Start at the beginning of the first level
While you are not at the end of the first level
    If the current node has a child
        Append the child to the end of the first level
        Update the tail pointer
    Advance to next node
Code
/*
  Insert Node at the end of a linked list
  head pointer input could be NULL as well for empty list
  Node is defined as
  class Node {
     int data;
     Node next;
     Node prev;
     Node child;
  }
*/
void flattenList(Node head, Node tail){
    Node currentNode = new Node();
    currentNode = head;

    while(currentNode != null){
        if(currentNode.child != null)
            append(currentNode.child, tail);
    }
    currentNode = currentNode.next
}

/*
Append the child list to the end of the tail and update the tail;
*/
void append(Node child, Node tail){
    Node currentNode = new Node();

    //Append child list to tail
    tail.next = child;
    child.prev = tail;

    //Find the new tail, which should be the end of the child list
    currentNode = child;
    while(currentNode.next != null){
        currentNode = currentNode.next;
    }

    //Update the tail pointer now that currentNode is the new tail
    tail = currentNode;
}

Unflatten Previous Linked List

Idea

To unflatten previous linked list, you can do following:

Explore Path:
    While not at the end
        If current node has a child
            Separate the child from its previous node
            Explore path beginning with the child
        Go onto the next node
Code
/*
  Insert Node at the end of a linked list
  head pointer input could be NULL as well for empty list
  Node is defined as
  class Node {
     int data;
     Node next;
     Node prev;
     Node child;
  }
*/
void unflattenList(Node start, Node tail){
    Node currentNode = new Node();

    exploreAndSeparate(start);

    //Update the tail pointer
    currentNode = start;
    while(currentNode.next != null)
        current = current.next
    tail = currentNode;
}

//exploreAndSeparate actually does the recursion and separation
void exploreAndSeparate(Node childListStart){
    Node currentNode = new Node();
    currentNode = childListStart;

    while(currentNode.next != null){
        //Check if currentNode is a start of a child list
        if(currentNode.child != null){
            //Broken child list from origin list. i.e. original prev node should point to null now
            currentNode.child.prev.next = null;
            //Split new child list out. Remember original parent can still do node.child to get this child list
            currentNode.child.prev = null;

            //Run recursion so that all childs from child node can be split
            exploreAndSeparate(currentNode.child);
        }
        currentNode = currentNode.next;
    }
}
Comments powered by Disqus