Singly Linked List

Singly Linked List is a type of a data structure in which each node stores some kind of data and a pointer or a reference to the next node in the list. Last node in the list (called as a tail) will not point to any other node, hence is reference value is null. First node in the list is called as a head of the Linked List.

Here is a generic implementation of Singly Linked List in java programming language. You can easily implement Stack Or Queue data structures using the Singly Linked List code provided below.

package computer.science;

public class SinglyLinkedList {
 private Node head;
 private int size;

  SinglyLinkedList() {
  head = new Node(null);
  size = 0;
 }

  public T get(int index) {
  if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException("Index out of bounds: " + index);
  }
  if (size == 0) {
   throw new IllegalAccessError("Trying to get element from empty list.");
  }
  Node temp = head;
  int count = 0;
  while (count < index) {
   temp = temp.next;
   count++;
  }
  Node reqNode = temp.next;
  return reqNode.getData();
 }

  public void add(int index, T data) {
  System.out.println("index=" + index + ", value=" + data);
  if (index < 0 || index > size) {
   throw new IllegalArgumentException("Invalid position specified: " + index);
  }
  Node n = new Node(data);
  Node temp = head;
  int count = 0;
  while (count < index) {
   temp = temp.next;
   count++;
  }
  n.next = temp.next;
  temp.next = n;
  size++;
 }

  // append to the list
 public void add(T data) {
  add(size, data);
 }

  public T remove(int index) {
  if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException("Index out of bounds: " + index);
  }
  if (size == 0) {
   throw new IllegalAccessError("Trying to remove element from empty list.");
  }
  Node temp = head;
  int count = 0;
  while (count < index) {
   temp = temp.next;
   count++;
  }

   Node toRemove = temp.next;
  if (toRemove.next != null) {
   temp.next = toRemove.next;
   toRemove.next = null;
  } else {
   temp.next = null;
  }
  size--;
  return toRemove.getData();
 }

  public String toString() {
  if (size == 0) {
   return null;
  } else {
   StringBuilder str = new StringBuilder();
   Node t = head.next;
   for (int i = 0; i < size; i++) {
    str.append(t.data + " ");
    t = t.next;
   }
   str.append("[size=" + size + "]");
   return str.toString();
  }
 }

  public int getSize() {
  return size;
 }

  private class Node {
  Node next;
  T data;

   Node(T data) {
   this.data = data;
   this.next = null;
  }

   public T getData() {
   return data;
  }
 }

  public static void main(String[] args) {
  SinglyLinkedList sLL = new SinglyLinkedList();

   System.out.println("Adding nodes ...");
  sLL.add(sLL.getSize(), 100);
  sLL.add(sLL.getSize(), 99);
  sLL.add(sLL.getSize(), 98);
  sLL.add(sLL.getSize(), 97);
  System.out.println(sLL.toString());
  sLL.add(2, 96);
  System.out.println(sLL.toString());
  sLL.add(1, 95);
  System.out.println(sLL.toString());
  sLL.add(4, 94);
  System.out.println(sLL.toString());
  sLL.add(sLL.getSize(), 93);
  System.out.println(sLL.toString());

   System.out.println();

   System.out.println("Removing nodes ...");
  int t;
  t = sLL.remove(0);
  System.out.println("removed " + t + " from position " + 0);
  System.out.println(sLL.toString());

   t = sLL.remove(6);
  System.out.println("removed " + t + " from position " + 6);
  System.out.println(sLL.toString());

   t = sLL.remove(4);
  System.out.println("removed " + t + " from position " + 4);
  System.out.println(sLL.toString());

   System.out.println();

   System.out.println("Get elements ...");
  System.out.println("Got " + sLL.get(1) + " at position " + 1);
  System.out.println("Got " + sLL.get(sLL.getSize() - 1) + " at position " + (sLL.getSize() - 1));
  System.out.println("Got " + sLL.get(3) + " at position " + 3);

   System.out.println();
  System.out.println(sLL.toString());
 
  System.out.println();
  System.out.println("Appending 55 to the list ...");
  sLL.add(55);
  System.out.println(sLL.toString());
 }

}