Wednesday, November 13, 2019

Linked List Implementation Java Program

In this post we’ll see an implementation of Linked List in Java. Operations covered in this singly Linked List Java implementation are as per the given table of contents-


Linked List data structure

Linked list data structure though linear in nature doesn’t store its node in contiguous memory location like array. In Linked list nodes are linked by each node holding reference to the next node.

Following image shows the nodes in the Linked List and how nodes are linked.

Linked list implementation in Java

Java program for Linked List

For representing nodes of the linked list a separate class is used which, apart from the data, also holds a reference to itself.

class Node{
 //data
 int i;
 // Reference to next node
 Node next;
}

Java implementation of linked list given here is a double ended list where we have two references head and tail; head always points to the first node and the tail is a reference to the last node.

Insertion in linked list

For insertion there are three scenarios insert at the beginning, insert at the end and insert at the given index.

1- Inserting node in linked list at the beginning has two scenarios.

If it is the first node then both head and tail should point to it.

If nodes already exist then the inserted node should reference the current first node and head should start pointing to the inserted node.

public void insertFirst(int i){
 //Create a new node
 Node newNode = new Node(i);
 if(isEmpty()){
  tail = newNode;
 }
 newNode.next = head;
 head = newNode;
 size++;
}

Note here that size variable is used to store the current size of the List.

2- Inserting node in linked list at the end has two scenarios.

If it is the first node then both head and tail should point to it.

If nodes already exist then the current last node should reference the inserted node and tail should start pointing to the inserted node.

public void insertLast(int i){
 Node newNode = new Node(i);
 if(isEmpty()){
  head = newNode;
 }else{
  tail.next = newNode;
 }
 tail = newNode;
 size++;
}
3- Inserting node in linked list at the given index has three scenarios.

If inserting at index 0 that is equivalent to insertFirst.

If inserting at index when (index == size) that is equivalent to insertLast.

Otherwise traverse to the node currently at the given index and change the references so that the new node starts referencing the current node and the node which was previously referencing the current node should start referencing the new node.

linked list insertion java
public void insertAtIndex(int i, int index){
  if(!isValidIndex(index)){
    throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
  }
  Node newNode = new Node(i);
  Node current = head;
  Node temp = head;
  //insert at the start
  if(index == 0){
    insertFirst(i);
  }
  // insert at last
  else if(index == size){
    insertLast(i);
  }else{
    for(int j = 0; j < index && current.next != null; j++){
      temp = current;
      current = current.next;
    }
    newNode.next = current;
    temp.next = newNode;
    size++;    
  }        
}

Linked List traversal

For Linked list traversal from start to end you need to start from head and then move sequentially unless the next node reference is not null.

// Method to traverse and display all nodes
public void displayList(){
 Node current = head;
 while(current != null){
  current.displayData();
  current = current.next;
 }
 System.out.println("");
}

To get element at a given index traverse to the node currently at that index and return that node.

public Node get(int index){
  if(!isValidIndex(index)){
    throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
  }
  Node current = head;
  for(int j = 0; j < index; j++){
    current = current.next;
  }
  return current;        
}

Deleting node in Linked List

For deletion there are three scenarios-

  • Delete first node
  • Delete last node
  • Delete node at given index

1- If you are deleting the first node then in your Linked list Java program what you need to do is to change the head reference so that it starts referencing the next node.

public void removeFirst(){
 if(head == null){
  throw new RuntimeException("List is empty..");
 }
 // if there is only one node
 if(head.next == null){
  tail = null;
 }
 head = head.next;
 size--;
}

2- If you are deleting the last node in a linked list then change the reference for tail so that it starts referencing the previous node. Since it is a singly linked list implementation so you need to start from the first node and traverse the list till the end.

public void removeLast(){
 if(tail == null){
  throw new RuntimeException("List is empty..");
 }
 Node current = head;
 Node temp = head;
 // if there is only one node
 if(head.next == null){
  head = null;
 }  
 while(current != tail){
  temp = current;
  current = current.next;
 }
 tail = temp;
 tail.next = null;
 size--;
}
3- Deleting node at the given index has three scenarios.

If deleting node at index 0 that is equivalent to removeFirst.

If deleting node at index when (index == size) that is equivalent to removeLast.

Otherwise traverse to the node at the given index and change the references so that the node on the left of the node to be deleted starts referencing the node on the right of the node to be deleted.

public void removeAtIndex(int index){   
  if(!isValidIndex(index +1)){
    throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
  }
  Node current = head;
  Node temp = head;
  //remove at the start
  if(index == 0){
    removeFirst();
  }
  // remove at last
  else if(index == size - 1){
    removeLast();
  }else{
    for(int j = 0; j < index && current.next != null; j++){
      temp = current;
      current = current.next;
    }
    temp.next = current.next;
    current.next = null;
    size--;
  }
}

Linked List implementation in Java – Full Program

class Node{
  //data
  int i;
  // Reference to next node
  Node next;

  public Node(int i){
    this.i = i;
    this.next = null;
  }
  public void displayData(){
    System.out.print(" " + i);
  }
}

public class LinkedList {
  private Node head;
  private Node tail;
  private int size = 0;
  public LinkedList(){
    head = null;
    tail = null;
  }
  public boolean isEmpty(){
    return head == null;
  }
    
  public void insertFirst(int i){
    //Create a new node
    Node newNode = new Node(i);
    if(isEmpty()){
      tail = newNode;
    }
    newNode.next = head;
    head = newNode;
    size++;
  }
    
  public void insertLast(int i){
    Node newNode = new Node(i);
    if(isEmpty()){
      head = newNode;
    }else{
      tail.next = newNode;
    }
    tail = newNode;
    size++;
  }
    
  public void insertAtIndex(int i, int index){
    if(!isValidIndex(index)){
      throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
    }
    Node newNode = new Node(i);
    Node current = head;
    Node temp = head;
    //insert at the start
    if(index == 0){
      insertFirst(i);
    }
    // insert at last
    else if(index == size){
      insertLast(i);
    }else{
      for(int j = 0; j < index && current.next != null; j++){
        temp = current;
        current = current.next;
      }
      newNode.next = current;
      temp.next = newNode;
      size++;    
    }        
  }
    
  public Node get(int index){
    if(!isValidIndex(index)){
      throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
    }
    Node current = head;
    for(int j = 0; j < index; j++){
      current = current.next;
    }
    return current;        
  }
    
  // Method to traverse and display all nodes
  public void displayList(){
    Node current = head;
    while(current != null){
      current.displayData();
      current = current.next;
    }
    System.out.println("");
  }
    
  public void removeFirst(){
    if(head == null){
      throw new RuntimeException("List is empty..");
    }
    // if there is only one node
    if(head.next == null){
      tail = null;
    }
    head = head.next;
    size--;
  }
    
  public void removeLast(){
    if(tail == null){
      throw new RuntimeException("List is empty..");
    }
    Node current = head;
    Node temp = head;
    // if there is only one node
    if(head.next == null){
      head = null;
    }        
    while(current != tail){
      temp = current;
      current = current.next;
    }
    tail = temp;
    tail.next = null;
    size--;
  }
    
  public void removeAtIndex(int index){
    if(!isValidIndex(index +1)){
      throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size);
    }
    Node current = head;
    Node temp = head;
    //remove at the start
    if(index == 0){
      removeFirst();
    }
    // remove at last
    else if(index == size - 1){
      removeLast();
    }else{
      for(int j = 0; j < index && current.next != null; j++){
        temp = current;
        current = current.next;
      }
      temp.next = current.next;
      current.next = null;
      size--;
    }
  }
    
  private boolean isValidIndex(int index){
    return index >= 0 && index <= size;
  }
    
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    
    list.insertFirst(1);
    list.insertLast(2);
    list.insertLast(3);
    list.insertLast(4);
    list.insertLast(5);
    System.out.println("After insertions--");
    list.displayList();
    list.removeLast();
    System.out.println("After removal--");
    list.displayList();
    list.removeAtIndex(1);
    System.out.println("After removal--");
    list.displayList();
    System.out.println("Get Node--");
    Node node = list.get(1);
    node.displayData();
  }
}

Output

After insertions--
 1 2 3 4 5
After removal--
 1 2 3 4
After removal--
 1 3 4
Get Node--
 3

That's all for this topic Linked List Implementation Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. How to Reverse a Linked List in Java
  2. Java Program to Detect And Remove Loop in a Linked List
  3. Binary Tree Traversal Using Depth First Search Java Program
  4. Exponential Search Program in Java
  5. Radix Sort Program in Java

You may also like-

  1. How to Format Time in AM-PM Format - Java Program
  2. How to Find Last Modified Date of a File in Java
  3. Setting And Getting Thread Name And Thread ID - Java Program
  4. How to Find Common Elements Between Two Arrays - Java Program
  5. How LinkedList Class Works Internally in Java
  6. Lambda Expressions in Java 8
  7. Switch-Case Statement in Java
  8. Spring Asynchronous Method Execution Support Using @Async Annotation

No comments:

Post a Comment