Linked List in Java

Let us write a linked list program in Java.

You certainly ask me why don't you use List class - either ArrayList or LinkedList class in Collections? Because your interviewer will not ask you about library classes. He wants you to write your own code.


OK, the basic premise of linked list is that - it has a node and it is linked to next node with a pointer - or a reference in Java.

So we can define a Node class as follows

class Node{
    int num;
    Node next;
}

The data of the node can be integer or some complex structure. But we must have a reference to next node - which is the second field in the class.

First node has reference of second node. Second node has reference of third node and so on. What about last node? What will be next of the last node? Last node will have next field as null. null indicates the termination of list. 


Now the list also needs the reference of first node - head, first or you call it by any name.

It makes your program easier if you maintain the reference to last node as well - it is optional. Because you can always find last node by traversing till the end - till you reach null.

You will need methods to get data of a node and next field of a node. Let us write these methods.

class LinkedList{
     class Node{
         int num;
         Node next;
         Node(int a){
             num = a;
             next = null;
         }
     }
     Node first, last;
     int getData(){
         return num;   
     }
     Node getNext(){
         return next;
     }
}

We have a class LinkedList with inner class Node and we have defined methods to getData and getNext.

Next we will add two methods a)constructor - which will initialize the list by creating one node and setting first to it  and b)method to append one node which will add a node at the end of list (this is where last field is helpful)

class LinkedList{
    ......
    LinkedList(int n){
         Node nd = new Node(n); 
         first = last = nd;
    }
     void append(int n){
         Node nd = new Node(n);
         last.next = nd;
         last = nd;
   }
}

Now let us put all these things together and write a complete program to create a linked list and print the elements.

import java.util.Scanner;
class LinkedList{
    class Node{
       int num;
       Node next;
       public Node(int n){
           num = n;
       }
       Node getNext(){
          return next;
       }
       int getNum(){
          return num;
       }
    }
    public LinkedList(){
       createList();
    }
    public void createList()
    {
       int n;
       Scanner scanner = new Scanner(System.in);
       System.out.println("First node=");
       n = scanner.nextInt();
       head = new Node(n);
       head.next = null;
       last = head;//only one node. 
    }
    Node head = null;
    Node last = null;
    void append(int n){
         Node newNode = new Node(n);
         last.next = newNode;
         last = newNode;
    }
    void print(){
       for(Node nd = head; nd.getNext()!=null;nd=nd.getNext()){
            System.out.println(nd.getNum()+" ");
       }
    }
    Node findNthFromEnd(Node nd,int n){
    }
 void printNthFromLast(int n) 
    { 
        Node main_ptr = head; 
        Node ref_ptr = head; 
  
        int count = 0; 
        if (head != null) { 
            while (count < n) { 
                if (ref_ptr == null) { 
                    System.out.println(n + " is greater than the no "
                                       + " of nodes in the list"); 
                    return; 
                } 
                ref_ptr = ref_ptr.next; 
                count++; 
            } 
            while (ref_ptr != null) { 
                main_ptr = main_ptr.next; 
                ref_ptr = ref_ptr.next; 
            } 
            System.out.println("Node no. " + n + " from last is " + main_ptr.data); 
        } 
    }   
         
  }
  class Demo{
      public static void main(String args[]){
             Scanner scanner = new Scanner(System.in);
             LinkedList list = new LinkedList();
             for(int i=0;i<10;i++){
                 System.out.println("num=");
                 int a = scanner.nextInt();
                 list.append(a);
             }
             list.print();
        }
}