Linked List

Linked list is a fundamental data structure, which uses reference stored in each node to iterate through subsequent nodes. A linked list has many types like singly linked list, doubly linked list and circular linked list. Following is a simple bare bone implementation of singly linked list:

The base interface:

public interface LinkedList {
 public boolean add(T t);
 public boolean remove(T t);
 public void removeAll();
 public int size();
 public boolean isEmpty();
}

Class representing each node:

public class LinkNode {
 private LinkNode nextNode = null;
 private T node = null;

 public LinkNode() {
  
 }
 
 public LinkNode(T node) {
  this.node = node;
 }
 
 public T getNode() {
  return node;
 }

 public void setNode(T node) {
  this.node = node;
 }
 
 public LinkNode getNextNode() {
  return nextNode;
 }

 public void setNextNode(LinkNode nextNode) {
  this.nextNode = nextNode;
 }
 
 public String toString() {
  return node.toString();
 }
 
 public int hashCode() {
  return node.hashCode();
 }
 
 public boolean equals(LinkNode t) {
  return node.equals(t.getNode());
 }
}

Implementation for a singly linked list:

public class SingleLinkedList implements LinkedList {
 LinkNode header = null;
 LinkNode lastNode = null;
 
 public SingleLinkedList() {
  
 }
 
 public boolean add(T t) {
  LinkNode newNode = new LinkNode(t);
  if(header == null) {
   header = newNode;
  }
  else {
   lastNode.setNextNode(newNode);
  }
  lastNode = newNode;
  return true;
 }
 
 public boolean remove(T t) {
  LinkNode tmp = header;
  LinkNode prev = null;
  
  while(tmp != null) {
   if(tmp.getNode().equals(t)) {
    if(prev == null) header = null;
    else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());
    return true;
   }
   prev = tmp;
   tmp = tmp.getNextNode();
  }
  return false;
 }
 
 public void removeAll() {
  header = null;
 }
 
 public boolean isEmpty() {
  return header == null;
 }
 
 public int size() {
  LinkNode tmp = header;
  int size = 0;
  while(tmp != null) {
   size++;
   tmp = tmp.getNextNode();
  }
  
  return size;
 }
 
 public String toString() {
  StringBuffer str = new StringBuffer("[");
  LinkNode tmp = header;
  while(tmp != null) {
   str.append(tmp.toString());
   tmp = tmp.getNextNode();
   if(tmp != null) str.append(", ");
  }
  str.append("]");
  return str.toString();
 }
}

Test class which uses the singly linked list implementation:

public class LinkedListTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  LinkedList list = new SingleLinkedList();
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.add("1");
  list.add("2");
  list.add("3");
  list.add("2");
  list.add("2");
  list.add("3");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.remove("2");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.removeAll();
  System.out.println("Is list empty? " + list.isEmpty());
 }

}