Lets begin implementing a singly linked list in Java.
First declare our MyLinkedList class:
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.
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:
Next lets declare a constructor. Our linked list will be initially empty. Accordingly we will set head to null and the size to 0.
Declare a getter that returns the value of our size variable named getSize:
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:
Before starting to write our add function it would be wise to think of the edge cases. Here there are two:
Here’s how we will handle each case:
Declare our new node and add one to the size of our list (since adding an element increases the size by 1):
Add an if statement to cover both cases when adding a node:
If the head is null we simply assign the head node to be the new node:
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:
Get the last (tail) node in the list. We will do this by iterating through the list until n.next is equal to null:
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:
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:
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:
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:
Declare a new StringBuilder s. We will use this StringBuilder to build our string:
Append the brackets ‘’ to our StringBuilder and return the string represented by our StringBuilder at the end of the function:
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:
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:
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):
The finished function is as follows:
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