Linked List

Linked lists are the most important type of data structure. It contains a series of special elements. These special elements are called special because they hold the data and a pointer to the next element. This pointer is usually called as next pointer. The root element is the starting point of the linked list and the tail element is the last element in the linked list. After the tail element there are no more elements and so the last element’s next pointer has a null reference.

There are 3 types of linked lists
1) Single Linked List – There is one next reference per element
2) Double Linked List – There are two references per element called prev and next. The prev reference points to the previous element and the next reference points to the next element as always
3) Circular Linked List – This is a special type of linked list and they can be of Single or double linked list. The important property that differentiates them is that they do not have the end elements. Yes, there are no head or tail elements. It means that if you start from any element and traverse, you will end up in going circles and never end.

This project illustrates the various operations that can be done on a Single Linked List. Additionally it also shows a special stack implementation using Single Linked List.

Traverse and Print All Elements
Traverses the entire linked list and prints all elements.

 /**
  * Prints all elements in the linked list to out stream
  * @param void
  * @return void
  */
 public void print() {
  Element currElement = head;
  while (currElement != null) {
   System.out.println(currElement);
   currElement = currElement.getNext();
  }
 }

Add an element to the end
This adds the given data as an element to the end of the linked list. Now the new element becomes the tail element.

 /**
  * Adds the provided Integer object data to the end of linked list
  * @param data Integer
  * @return boolean
  */
 public boolean add(Integer data) {
  Element newElement = new Element(data);
  if (head == null) {
   head = newElement;
   return true;
  } else {
   Element prevElement = head;
   Element currElement = head.getNext();
   while (currElement != null) {
    prevElement = currElement;
    currElement = currElement.getNext();
   }
   if (prevElement != null) {
    prevElement.setNext(newElement);
    return true;
   }
  }
  return false;
 }

Add an element at the specified position
Given an integer data, this method creates an element out of it and adds at the specified position of the list.

 /**
  * Inserts the provided Integer object data at the requested position of linked list.
  * If insert was successful it returns true else returns false
  * 
  * 
  * Implementation Details:
  * Though the iteration variable tracks the position of current Element pointer, if a position
  * is found where the new element needs to be inserted, it is implicit that the position is going to be
  * in between the prevElement and curreElement. Idea is to visualize the position (input) to be in between 
  * prevElement and currElement
  * 
  * Say if the position is after the last element then it means you have to insert after the prevElement(pointing last element)
  * but before the curreElement (which is pointing a virtual non-existent element - beyond last element). So its imperative that 
  * the while loop runs until the prevElement is pointing the last element
  * 
  * @param data Integer
  * @param position Long
  * @return boolean
  * 
  */
 public boolean add(Integer data, Long position) {
  
  if (position == null || position.intValue() < 1) {
   return false;
  }
  
  if (head != null) {
   Element newElement = new Element(data);
   if (position.intValue() == 1) {
    newElement.setNext(head);
    head = newElement;
   } else {
    Element prevElement = head;
    Element currElement = head.getNext();
    int iteration = 2;
    while (prevElement != null) {
     if (iteration == position.intValue()) {
      newElement.setNext(currElement);
      prevElement.setNext(newElement);
      return true;
     } else {
      prevElement = currElement;
      currElement = currElement.getNext();
      iteration++;
     }
    }
   }
  }
  
  return false;
 }

Delete an element from the given position
Given a position in linked list, this deletes the element at that position. If there is no such position in the list, then it does not delete anything from the linked list.

 /**
  * This method deletes all elements in the linked list that have the provided Integer data. 
  * If one or many elements are deleted, this method returns true else it returns false
  * @param data Integer
  * @return boolean
  */
 public boolean delete(Integer data) {
  Element givenElement = new Element(data);
  boolean deleted = false;
  
  // Special case if the head element needs to be deleted
  if (head.equals(givenElement)) {
   Element temp = head;
   head = head.getNext();
   temp.setNext(null);
   deleted = true; 
  }
  
  if (head != null) {
   Element prevElement = head;
   Element currElement = head.getNext();
   while (currElement != null) {
    if (currElement.equals(givenElement)) {
     prevElement.setNext(currElement.getNext());
     currElement = currElement.getNext();
     deleted = true;
    }
    prevElement = currElement;
    currElement = currElement.getNext();
   }
  }
  return deleted;
 }

Delete all elements with a given data
Deletes all elements that have the given data. Takes care of chaining the element appropriately after the deletion is complete.

 /**
  * This method deletes the element at requested position of the linked list. 
  * If deletion happens, this method returns true else it returns false
  * @param position Long
  * @return boolean
  */
 public boolean delete(Long position) {
  if (position == null || position.intValue() < 1) {
   return false;
  }

  if (head != null) {
   if (position.intValue() == 1) {
    Element temp = head;
    head = head.getNext();
    temp.setNext(null);
    return true;
   } else {
    int iteration = 2;
    Element prevElement = head;
    Element currElement = head.getNext();
    while (currElement != null) {
     if (iteration == position.intValue()) {
      prevElement.setNext(currElement.getNext());
      currElement.setNext(null);
      return true;
     }
     prevElement = currElement;
     currElement = currElement.getNext();
     iteration++;
    }
   }
  }

  return false;
 }

Clear all elements (delete all)
Deletes all elements that have the given data. Takes care of chaining the element appropriately after the deletion is complete.

 /**
  * Deletes all elements in the linked list. 
  * If all elements are deleted, this method returns true else it returns false
  * @param void
  * @return boolean
  */
 public boolean clear() {
  if (head == null) {
   return false;
  }
  
  while (head != null) {
   Element element = head;
   head = head.getNext();
   element.setNext(null);
  }
  return true;
 }

Get Element At
Gets the data from the element at the specified position. If there are no elements at the given position, then this method returns null.

 /**
  * Returns the element at requested position of the linked list. 
  * The position is counted from the head element.
  * @param position Long
  * @return Element
  */
 public Element getElementAt(Long position) {
  
  if (position == null || head == null || position.intValue() < 1) {
   return null;
  }
  
  int iteration = 1;
  Element currElement = head;
  while (currElement != null) {
   if (position.intValue() == iteration) {
    return currElement;
   }
   currElement = currElement.getNext();
   iteration++;
  }

  return null;
 }

Get Nth Element From Last
Get Nth element from the tail element of the linked list. The first thought that strike's everyone is – Navigate to the tail element of the linked list and return the Nth previous element from there. But the point that we all tend to forget is - we can traverse only forward in a single linked list. We cannot traverse backwards, and so it makes the solution pretty tricky. The idea is to have two references in the linked list, say A and B. As a first step, have them separated by N elements. This is done by forwarding the B reference by N elements and thereafter keep traversing both references until B reaches tail element. When B is referring the tail element, this in turn means that A is N elements before the tail element.

 /**
  * Returns the element at requested position of the linked list. 
  * The position is counted from the tail or last element of the linked list.
  * @param position Long
  * @return Element
  */
 public Element getNthFromLastElement(Long position) {
  
  if (position == null || head == null || position.intValue() < 1) {
   return null;
  }
  
  Element currElement = head;
  Element nthBehindElement = head;
  int iteration = 1;
  
  while (currElement != null && iteration <= position.intValue()) {
   if (iteration++ == position.intValue()) {
    break; 
   }
   currElement = currElement.getNext();
  }
  
  if (currElement == null) {
   System.out.println("** Error: Current Element is past tail element");
   return null;
  }
  
  while (currElement.getNext() != null) {
   currElement = currElement.getNext();
   nthBehindElement = nthBehindElement.getNext();
  }
  
  return nthBehindElement;
 }

Stack Implementation
This implementation of Stack is done using a linked list. Stack is a simple LIFO data structure. There are two major actions that you can perform on a stack. Push and Pop. Additionally we have a clear operation that deletes all elements in the stack. And lastly we have print operation that prints all elements in the stack.

 /**
  * Returns true if stack is empty else returns false
  * @return boolean
  */
 public boolean isEmpty() {
  if (this.head == null) {
   return true;
  }
  return false;
 }
 
 /**
  * Returns true if the method was able to push data to the stack. Else returns false.
  * @param data Integer
  * @return boolean
  */
 public boolean push(Integer data) {
  if (data == null) {
   return false;
  }
  
  Element newElement = new Element(data);
  if (head == null) {
   head = newElement;
   return true;
  }
  
  if (head != null) {
   Element temp = head;
   head = newElement;
   head.setNext(temp);
   return true;
  }
  
  return false;
 }
 
 
 /**
  * Pops and returns the last element that was pushed to the stack
  * @return stackElement
  */
 public Element pop() {
  Element element = null;
  if (head == null) {
   System.out.println("Stack is empty!! Cannot pop anything out of it!!");
   return element;
  }
  
  Element firstElement = head;
  Element secondElement = head.getNext();
  head = secondElement;
  firstElement.setNext(null);
  return firstElement;
 }
 
 
 /**
  * Returns true if stack was cleared or if it was empty already
  * @return boolean
  */
 public boolean clear() {
  while (head != null) {
   Element element = head;
   head = head.getNext();
   element.setNext(null);
  }
  return true;
 }
 
 
 /**
  * Iterates over the stack and prints all its elements
  */
 public void printAll() {
  if (head == null) {
   System.out.println("Stack is empty currently!!");
   return;
  }
  
  Element currElement = head;
  while (currElement != null) {
   System.out.println(currElement);
   currElement = currElement.getNext(); 
  }
 }

The entire code base for this project can be accessed from my Github repository – Linked List algorithms. I have added as many comments as possible in the code. Hope it helps!!