A brief introduction to the concept of a linked list through an example.

Introduction

Often in programming we are required to systematically store some type of information. A prime example of this is to use arrays but when you don’t know the amount of information to be stored we need a dynamic data structure. One option for us is to use a linked list. A linked list works by creating a collection of objects (nodes) which both carry the data we want to store and a reference to the next node in the list. So the first node in the list points to the next node and then the next points to the one after that until we reach the last node which will point to null. This way all we really need to keep track of is the first node, as knowing it will enable us to access any node down the list (because they each point to each other, they are linked). And whenever you add a node it goes to the end of the list (as in the current last node begins to point to the new node and the new node, of course, to null [and it is the new last node now]). Let’s do an example:

Example

Let’s pretend we need to store a collection of integers and then display them all. If we knew the amount of integers we were going to store the most obvious choice would be an array but we don’t so we need a dynamic data structure. If we decide to use a linked list then the first thing to do is to write a class for the node that will hold our integer. All the node really needs to have is two instance variables: one for the integer and one for the reference to the next node in the list (as well as the accessor methods and the constructor).

class node
{ private int data; //holds an arbitrary integer
private node next; //reference to the next node

public node(int d, node n) //constructor
{ data = d;
next = n;
}
//these methods let us use our variables
public void setNext(node n)
{ next=n;}

public void setData(int d)
{ data=d;}

public node getNext()
{ return next;}

public int getData()
{ return data;}
}

Now that we have the basic node class that will make up the linked list it’s pretty easy to think up a display algorithm if we define the first node (and last node) to be:

private static node firstNode; //a reference to the first node
private static node lastNode = null; //a reference to the last node

private static node firstNode; //a reference to the first node
private static node lastNode = null; //a reference to the last node

public static void display() //displays all the data in the nodes
{ node n=firstNode;
while(n!=null) //loops forward displaying node’s data (the integers)
{ System.out.print(n.getData()+", ");
n=n.getNext(); //move to the next node in the list
}
}

Now we must create the actual linked list by writing a method that will not only construct the node but put it at the end of the list (set the last node’s next pointer to the new node). We already have a reference to the first and last node so by using that information we can tell one of two conditions: that the node we are creating is the first node or it is not. So:

public static void create(int d) //inserts the node into the list
{ node n=new node(d,null); //create node
if(lastNode != null) //if it is not the first node
{ lastNode.setNext(n);lastNode=n;}
else //if n is the first node
{ firstNode=n;lastNode=n;}
}

This is basically all you really need to know. All that’s left is just to write a little loop prompting the user for numbers and then passing those numbers into create() and then to see if it works you can display() the nodes (or rather the integers) but I’ll leave that up to you.

Conclusion

Linked lists are a great way to store a theoretically infinite amount of data (of course this isn’t really possible) with a small and versatile amount of code. They are great in that you can change and write them to serve your particular needs. For example: our lists were one directional, in that the individual node has no idea who is behind him in the list. This can be easily altered by the addition of a reference to the node behind as well as in front. This will give you greater control over the list. We could also write sorting algorithms, delete functions, and any number of methods that we find beneficial.