Linked List Theory

As we know that the instance variables of an object can be arrays, similarly one of the more interesting possibilities is that an object can also contain a reference to another object of the same type. There is a common data structure, the list, that takes advantage of this feature. Lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node usually contains a unit of data called the cargo. In our below example, the cargo will be a single integer, but later we will write a generic list that can contain objects of any type.

we'll start with the instance variables, one or two constructors and toString so that we can test the basic mechanism of creating and displaying the new type.

1) Node01.java

package com.symantec;

public class Node01
{
    int cargo;
    Node01 next;

    public Node01 () {
        cargo = 0;
        next = null;
    }

    public Node01 (int cargo, Node01 next) {
        this.cargo = cargo;
        this.next = next;
    }

    public String toString () {
        return cargo + "";
    }

}

The declarations of the instance variables follow naturally from the specification, and the rest follows mechanically from the instance variables. The expression cargo + "" is an awkward but concise way to convert an integer to a String.


To test the implementation so far, we would put something like this in main:

Node node = new Node (1, null);
System.out.println (node);

Further To make it more interesting, we need a list with more than one node which you can look in below code.

2) MainNode01.java

package com.symantec;

import java.util.ArrayList;
import java.util.List;

public class MainNode01 {
public static void main(String[] args)
{
    List list = new ArrayList();

    Node01 node = new Node01 (1, null);
   System.out.println (node);
 
   list.add(node);
   System.out.println ("list items >> "+list);
 
Node01 node1 = new Node01 (2, null);
Node01 node2 = new Node01 (1, null);
System.out.println ("node1 > "+node1+" node2 >"+node2);

list.add(node1);
list.add(node2);
        System.out.println ("updated list items >> "+list);
 
   node.next = node1;
   node1.next = node2;
   node2.next=null;
 
   System.out.println ("referring next node (node01) data from first node >> "+node.next);

}

}

Initially above code creates three nodes (1 in the begining and two created later), but we don't have a list yet because the nodes are not linked. The state diagram looks like this:

To link up the nodes, we have to make the first node refer to the second and the second node refer to the third.

    node.next = node1; 

    node1.next = node2; 

    node2.next = null; 

The reference of the third node is null, which indicates that it is the end of the list. Now the state diagram looks like:

Now we know how to create nodes and link them into lists.

The thing that makes lists more useful is that they are a way of assembling multiple objects into a single entity, sometimes called a collection. In the example, the first node of the list serves as a reference to the entire list.

If we want to pass the list as a parameter, all we have to pass is a reference to the first node. For example, the method printList takes a single node as an argument. Starting with the head of the list, it prints each node until it gets to the end (indicated by the null reference).

Modified  MainNode01.java class after adding printList method

package com.symantec;

import java.util.ArrayList;

import java.util.List;

public class MainNode01 {

public static void printList (Node01 list) { 

    Node01 node = list; 

       while (node != null) { 

           System.out.print (node); 

           node = node.next; 

       } 

       System.out.println (); 

   } 

public static void main(String[] args) 

{

List list = new ArrayList();

Node01 node = new Node01 (1, null);

   System.out.println (node);    

   //printList (node);   

   list.add(node);

   System.out.println ("list items >> "+list);

   

Node01 node1 = new Node01 (2, null); 

//printList (node1); 

Node01 node2 = new Node01 (1, null);

//printList (node2); 

System.out.println ("node1 > "+node1+" node2 >"+node2);

list.add(node1);

list.add(node2);

   System.out.println ("updated list items >> "+list);

   

   node.next = node1;

   node1.next = node2;

   node2.next=null;

   

   System.out.println ("referring next node (node01) data from first node >> "+node.next);

   printList (node); 

   printList (node1); 

   printList (node2); 

}

}

Inside printList we have a reference to the first node of the list, but there is no variable that refers to the other nodes. We have to use the next value from each node to get to the next node.

This diagram shows the value of list and the values that node takes on:

This way of moving through a list is called a traversal, just like the similar pattern of moving through the elements of an array. It is common to use a loop variable like node to refer to each of the nodes in the list in succession.

By convention, lists are printed in parentheses with commas between the elements, as in (1, 2, 3). 

As an exercise, we can modify printList  using a for loop instead of a while loop so that it generates output in this format.