Implementing a Linked List in Java

Lets begin implementing a singly linked list in Java.

First declare our MyLinkedList class:

public class MyLinkedList<T> {

}

We’re declaring the class to have a type of T. This means that a new MyLinkedList class is instantiated to hold objects of a chosen data type.

Before we get into implementing the linked list itself we must first define our node class. This node class defines a node in our linked list. Each node needs to contain a data element and a reference to the next node in the list.

private class Node<U> {
	public U data;
	public Node<U> next;
	public Node(U data) {
		this.data = data;
		next = null;
	}
}

Our node class is typed just like our MyLinkedList class. Upon instantiating an object of our Node class we set the data correctly and set the next Node to null. Setting the next node to null indicates that there is not a next node in the list.

So now that we have our node class defined lets get back to our MyLinkedList class. To start off we’ll want to be able to store the head of our linked list as well as the size of our list. So declare variables for each of these:

	private Node<T> head;
	private int size;

Next lets declare a constructor. Our linked list will be initially empty. Accordingly we will set head to null and the size to 0.

	public MyLinkedList() {
		head = null;
		size = 0;
	}

Declare a getter that returns the value of our size variable named getSize:

	public int getSize() {
		return size;
	}

Now that the base for the MyLinkedList class has been setup the next thing to do is to write a function that will add data to the end of linked list. The function definition will look as follows:

public void add(T data) {

}

Before starting to write our add function it would be wise to think of the edge cases. Here there are two:

1. An empty list (AKA the head is null)
2. A non-empty list (AKA the head is not null)

Here’s how we will handle each case:

1. Create a new node and assign the head node to be the new node.
2. Create a new node. Navigate to the last node in the list and set it’s next node to be the new node.

Declare our new node and add one to the size of our list (since adding an element increases the size by 1):

	Node<T> newNode = new Node<T>(data);
	// add code to add the new node to the list here
	size++;

Add an if statement to cover both cases when adding a node:

	if(head == null) {

	} else {

	}

If the head is null we simply assign the head node to be the new node:

		head = newNode;

If the head is not null it becomes a bit more complicated. First declare a node and set it to the value of the head node:

		Node<T> n = head;

Get the last (tail) node in the list. We will do this by iterating through the list until n.next is equal to null:

		while(n.next != null)
			n = n.next;

After our while loop has finished processing n will contain the last node in the list. All that is left to do is set the value of n.next to the newNode:

		n.next = newNode;

The next value of the newNode is set to null in it’s constructor so there is no need to set it to null again.

The finished function looks as follows:

public void add(T data) {
	Node<T> newNode = new Node<T>(data);
	if(head == null) {
		head = newNode;
	} else {
		Node<T> n = head;
		while(n.next != null)
			n = n.next;
		n.next = newNode;
	}
	size++;
}

Add a function to clear our list. This is easier then it sounds. This function will reset the head to null and size to zero if the head is not currently null:

public void clear() {
	if(head != null) {
		head = null;
		size = 0;
	}
}

Add a function to output our current list to a String. The contents of our list will be contained within the brackets ‘[]’. If the list is empty [] will be printed to the string. A comma and space will be printed to the string in between elements of our list.

First start with the following function definition:

public String toString() {

}

Declare a new StringBuilder s. We will use this StringBuilder to build our string:

	StringBuilder s = new StringBuilder();

Append the brackets ‘[]’ to our StringBuilder and return the string represented by our StringBuilder at the end of the function:

	s.append("[");
   //code to iterate through our list and print out the elements goes here
	s.append("]");
	return s.toString();

Add an if statement that only runs if our list is not empty (ie head is not equal to null). If our list is not empty we don’t need to do anything:

	if(head != null) {
		
	}

Add code to iterate through the list. This will be similar to the the in the add function. Declare a node n that is set to head and iterate each node:

		Node<T> n = head;
		while(n != null) {
          // add code to print out each node here
			n = n.next;
		}

For each node we simply append the string value of the node followed by a comma and a space if the node is not the last in the list (ie n.next is not equal to null):

			s.append(n.data.toString());
			if(n.next != null)
				s.append(", ");

The finished function is as follows:

public String toString() {
	StringBuilder s = new StringBuilder();
	s.append("[");
	if(head != null) {
		Node<T> n = head;
		while(n != null) {
			s.append(n.data.toString());
			if(n.next != null)
				s.append(", ");
			n = n.next;
		}
	}
	s.append("]");
	return s.toString();
}

So far our MyLinkedList class is able to instantiate, add nodes to the end, get the size, clear all nodes, and output the contents of the list to a string. One should be able to add nodes and print out the current contents of the list for testing purposes now. In the following post we will cover how to delete nodes, get a node by index, and insert nodes to a specific position in the list.

This post is continued in the following post: Implementing a Linked List in Java - Part Two

Data Structures