# An Introduction to Linked Lists

`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.

##### Nathan
Nathan Pakovskie is an esteemed senior developer and educator in the tech community, best known for his contributions to Geekpedia.com. With a passion for coding and a knack for simplifying complex tech concepts, Nathan has authored several popular tutorials on C# programming, ranging from basic operations to advanced coding techniques. His articles, often characterized by clarity and precision, serve as invaluable resources for both novice and experienced programmers. Beyond his technical expertise, Nathan is an advocate for continuous learning and enjoys exploring emerging technologies in AI and software development. When he’s not coding or writing, Nathan engages in mentoring upcoming developers, emphasizing the importance of both technical skills and creative problem-solving in the ever-evolving world of technology. Specialties: C# Programming, Technical Writing, Software Development, AI Technologies, Educational Outreach