Singly Linked list fundamentals and associated operations (Create, Insert, Delete, Iterate)

In Java, we create object dynamically using new operator and it is stored in heap memory location. Each object created is associated with a handler(a reference to that object, if not that object will be garbage collected).
Lets consider a scenario, all objects created on heap is not associated with reference(usually we do when object is created), instead each object has reference of another object and we have reference of only the very first object created.Refer the following diagram and understand how a collection of objects linked in specifies order form a new data structure.

A collections of objects(say nodes in linked list terminology) dynamically created and allocated chunk of memory “on the fly.” and all created nodes are linked together in some pattern,this entire structure is termed as Linked list.Linked list can be of Singly, Doubly or Double ended linked list.

Singly linked list - In singly lined list, the very first node has where about of second node and second node has where about of third node and so on.However, second node does not know about first node, so as third node does not know about second know. In other words, each node has only one reference, of next node. How do we define node in Java code:-

public class Node {
 private int data;
 private Node next; // reference(handler) for next Node.

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getNextnode() {
  return nextnode;
 }

 public void setNextnode(Node nextnode) {
  this.nextnode = nextnode;
 }
}

Class Node has two fields, one primitive type(data) and another one of reference type(next). Since, only one reference for node type is present in Node class , we can reference only one node with that. that's why it is called singly liked list.

Singly Lined list - data and next as fields 

Doubly linked list - If we add one more reference type(previous) and it is used to reference previous node then that linked list pattern is termed as Doubly-linked list. Doubly-linked list Node class may be obtained by adding a reference type and its getter & setter as follows:-

public class Node {
 .....
 private Node previous;// reference(handler) for previous Node.
 
 public Node getPrevious() {
  return previous;
 }

 public void setPrevious(Node previous) {
  this.previous = previous;
 }
        ....
        ......
}

Doubly linked list - data, previous and previous as fields 

In following posts term linked list refers Singly linked list and we will use singly linked list for solving our most of the problems.As an introductory exercise we will write a sample program to create a linked list and write methods associated with it.

Hide code lines

package com.devinline.linkedlist;

public class SinglyLinkedListOperations {

 static Node head = null;

 private static Node createNewNode(int data) {
  return new Node(data);
 }

 /* Add New node at start of linked list */
 private static void insertFirst(int data) {
  Node newNode = createNewNode(data);
  if (head == null) {
   head = newNode;
  } else {
   newNode.setNext(head);
   head = newNode;
  }
 }

 /* Add New node at after a given node in Linked list */
 private static void insertAfterNode(Node node, int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  if (head == null) {
   head = newNode;
  } else if (current.getData() == node.getData()) {
   newNode.setNext(current.getNext());
   current.setNext(newNode);
  } else {
   while (current != null) {
    if (current.getData() == node.getData()) {
     break;
    } else {
     current = current.getNext();
    }
   }
   if (current != null) {
    newNode.setNext(current.getNext());
    current.setNext(newNode);
   }

  }
 }

 /* Add New node at before a given node in Linked list */
 private static void insertBeforeNode(Node node, int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  Node previousNode = null;
  if (head == null) {
   head = newNode;
  } else if (current.getData() == node.getData()) {
   newNode.setNext(current);
   head = newNode;
  } else {
   while (current != null) {
    if (current.getData() == node.getData()) {
     break;
    } else {
     previousNode = current;
     current = current.getNext();
    }
   }
   if (current != null) {
    previousNode.setNext(newNode);
    newNode.setNext(current);
   }

  }
 }

 /* Iterate linked list, reach at end and add new node */
 private static void insertLast(int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  if (head == null) {
   head = newNode;
  } else {
   while (current.getNext() != null) {
    current = current.getNext();
   }
   current.setNext(newNode);
   newNode.setNext(null);
  }
 }

 /* Display data of nodes/iterate linked list */
 private static void iterateLinedList(Node head) {
  Node current = head;
  if (head != null) {
   System.out.print("Data in linkedlist:[");
   while (current != null) {
    System.out.print(current.getData() + " ");
    current = current.getNext();
   }
   System.out.print(" ]");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 /* Find node with given value */
 private static boolean findNode(int data) {
  Node current = head;
  if (head != null) {
   while (current != null) {
    if (current.getData() == data) {
     return true;
    }
    current = current.getNext();
   }
  }
  return false;
 }

 /* Delete a given node */
 private static boolean deleteNode(int data) {
  Node current = head;
  Node backupNode = null;
  if (head != null && head.getData() == data) {
   head = current.getNext();
   return true;
  }
  if (current != null) {
   while (current != null) {
    if (current.getData() == data) {
     break;
    } else {
     backupNode = current;
     current = current.getNext();
    }
   }
   if (current != null) {
    backupNode.setNext(current.getNext());
    current = null;// garbage collected
    return true;
   }

  }
  return false;
 }

 public static void main(String[] args) {
  /* Create Linked list */
  insertFirst(13);
  insertLast(23);
  insertFirst(14);
  insertFirst(134);
  insertLast(23);
  insertFirst(142);
  insertFirst(135);
  insertFirst(141);
  insertFirst(141);
  insertFirst(145);
  insertFirst(148);
  insertFirst(145);
  insertLast(124);

  /* Display data of list, iterate linked list */
  iterateLinedList(head);

  /* Find a node, if exist */
  Boolean found = findNode(14);
  System.out.println((found == true) ? "\nNode exist "
    : "\nNot does not exist  ");

  /* Delete a Node */
  Boolean delStat = deleteNode(141);
  System.out.println((delStat == true) ? "\nNode deleted "
    : "\nNot does not exist  ");
  iterateLinedList(head);

  /* insert After Node operation*/
  insertAfterNode(createNewNode(124), 237);
  System.out.println("\n\nlist after insert afterNode operation");
  iterateLinedList(head);

  /* insert Before Node operation */
  insertBeforeNode(createNewNode(13), 297);
  System.out.println("\n\nlist after insert beforeNode operation ");
  iterateLinedList(head);

 }
}

In above program, we have created several methods for the linked list like:
1. createNewNode(int data) - It creates a Node with value data and returns the same.
2. insertFirst(int data) - It creates a Node and add it to, start of linked list. If head is null then it means linkedlist is empty and head is pointing to newly created node. Otherwise, newly created node is added before first node of linked list and head point to newly created node.
3. insertLast(int data) - It creates a new node and add it to end of the list.Since, we do not have direct reference for last node, we need to traverse to the end of list and then add the node at the end. Here with while() loop, we are iterating the list and reaches at end of list.
4. insertAfterNode(Node node, int data) - In this method, first we check whether head is null or not, if null head points to newly created node. If head it self is that reference node, then add newly created node next to it. If reference node is in middle or some where, iterate list an find that node. Once we get that node, come out of loop and add newly created node.
5. insertBeforeNode(Node node, int data) - Here we need to maintain previous node because once we move on from a given node we do not have control over that and since we have to add node right before that current node, so we maintain previous node reference using previousNode. Adding of node is similar to above method.
6. iterateLinedList(Node head) - Here we iterate linked list using loop and display each data value until we reach at end of loop.
7. findNode(int data) - Similar to above method, iterate the list linked list and compare for the data value, if found return true.
8. deleteNode(int data) - here node with the given value is deleted. First check whether first node is that node to be deleted, if true , head start pointing to second node. Otherwise, if that node is in between somewhere, loop through linked list and find that node. If found, come out of the loop. In loop we maintain backupNode(a reference to previous node) so that after removing current node this node will have reference of next of current(node to be deleted).
=============Sample output================
Data in linkedlist:[145 148 145 141 141 135 142 134 14 13 23 23 124  ]
Node exist

Node deleted
Data in linkedlist:[145 148 145 141 135 142 134 14 13 23 23 124  ]

list after insert afterNode operation
Data in linkedlist:[145 148 145 141 135 142 134 14 13 23 23 124 237  ]

list after insert beforeNode operation
Data in linkedlist:[145 148 145 141 135 142 134 14 297 13 23 23 124 237  ]
=========================================