• - Articles

• - QuickSort Tutorial
• - Linked Lists Tutorial

Linked Lists are a very common way of storing arrays of data. The major benefit of linked lists is that you do not specify a fixed size for your list. The more elements you add to the chain, the bigger the chain gets.

There is more than one type of a linked list, although for the purpose of this tutorial, we'll stick to singly linked lists (the simplest one). If for example you want a doubly linked list instead, very few simple modifications will give you what you're looking for. Many data structures (e.g. Stacks, Queues, Binary Trees) are often implemented using the concept of linked lists. Some different types of linked lists are shown below:

Here's a diagram to help you realize the main disadvantage of arrays but not Linked Lists (there are certain advantages of using arrays over linked lists, but they are not covered in this article):

Another drawback of arrays is that if you delete an element from the middle and want no holes in your array (e.g. (1, 2, 4, null) instead of (1, 2, null, 4)), you will need to shift everything after the deleted element down in O(n) time. If you're trying to add an element somewhere other than the very end of an array, you will need to shift some elements towards the end by one (also O(n) time) to make room for the new element, and if you're writing an application which needs to perform well and needs to do these operations often, you should consider using Linked Lists instead. This should help you understand Linked Lists:

My code of the LinkedList class follows. It is a commented oversimplification of the LinkedList class that's already built into Java. Please note that indexes start at 1 and not 0 (like in the Java LinkedList class), so the first element in the list has index 1.

public class LinkedList
{
	// reference to the head node.
	private Node head;
	private int listCount;
	
	// LinkedList constructor
	public LinkedList()
	{
		// this is an empty list, so the reference to the head node
		// is set to a new node with no data
		head = new Node(null);
		listCount = 0;
	}
	
	public void add(Object data)
	// post: appends the specified element to the end of this list.
	{
		Node temp = new Node(data);
		Node current = head;
		// starting at the head node, crawl to the end of the list
		while(current.getNext() != null)
		{
			current = current.getNext();
		}
		// the last node's "next" reference set to our new node
		current.setNext(temp);
		listCount++;// increment the number of elements variable
	}
	
	public void add(Object data, int index)
	// post: inserts the specified element at the specified position in this list.
	{
		Node temp = new Node(data);
		Node current = head;
		// crawl to the requested index or the last element in the list,
		// whichever comes first
		for(int i = 1; i < index && current.getNext() != null; i++)
		{
			current = current.getNext();
		}
		// set the new node's next-node reference to this node's next-node reference
		temp.setNext(current.getNext());
		// now set this node's next-node reference to the new node
		current.setNext(temp);
		listCount++;// increment the number of elements variable
	}
	
	public Object get(int index)
	// post: returns the element at the specified position in this list.
	{
		// index must be 1 or higher
		if(index <= 0)
			return null;
		
		Node current = head.getNext();
		for(int i = 1; i < index; i++)
		{
			if(current.getNext() == null)
				return null;
			
			current = current.getNext();
		}
		return current.getData();
	}
	
	public boolean remove(int index)
	// post: removes the element at the specified position in this list.
	{
		// if the index is out of range, exit
		if(index < 1 || index > size())
			return false;
		
		Node current = head;
		for(int i = 1; i < index; i++)
		{
			if(current.getNext() == null)
				return false;
			
			current = current.getNext();
		}
		current.setNext(current.getNext().getNext());
		listCount--; // decrement the number of elements variable
		return true;
	}
	
	public int size()
	// post: returns the number of elements in this list.
	{
		return listCount;
	}
	
	public String toString()
	{
		Node current = head.getNext();
		String output = "";
		while(current != null)
		{
			output += "[" + current.getData().toString() + "]";
			current = current.getNext();
		}
		return output;
	}
	
	private class Node
	{
		// reference to the next node in the chain,
		// or null if there isn't one.
		Node next;
		// data carried by this node.
		// could be of any type you need.
		Object data;
		

		// Node constructor
		public Node(Object _data)
		{
			next = null;
			data = _data;
		}
		
		// another Node constructor if we want to
		// specify the node to point to.
		public Node(Object _data, Node _next)
		{
			next = _next;
			data = _data;
		}
		
		// these methods should be self-explanatory
		public Object getData()
		{
			return data;
		}
		
		public void setData(Object _data)
		{
			data = _data;
		}
		
		public Node getNext()
		{
			return next;
		}
		
		public void setNext(Node _next)
		{
			next = _next;
		}
	}
}

Written by Pavel Bennett. Thanks to Tess Ghidei from IBM for suggesting a performance improvement.