Java Tips — A homemade linked list

How design and realize a linked list without using the java.util library

Photo by C Drying on Unsplash

Introduction

The Java SDK has realized a beautiful library to manage the collections of an object: this library is included in the java.util.* package.

To understand better the Collections and to impress in the mind the access by reference to an object will try to realize a homemade linked list.

This linked list that we will try to realize admit operation like add, remove and many others needed to manipulate the data structure. Imagine the linked list like a chain, with a start and an end and every node is linked only to the next ring.

Let’s go!

The node of the list

First of all we need to define the collection like a set of node and every node must have:

• Value: the information content that every node carry;
• Pointer: the pointer to the next element into the list; with this link every node knows the following node;

The structure of a Node is:

Node class

The Node class is provided of:

• A class variable to maintain the value and one to maintain the pointer to the following Node
• A default constructor that initializes to null the value and the pointer;
• A value constructor that initializes the value of the node with the object received in input and the pointer to null;
• Getter and setter methods to manipulate the node.

The linked list will be a sequence of nodes and every node will point by reference to the following node like the next picture:

Linked list structure

The LinkedList class is provided of:

• A class variable to maintain the reference to the first node of the list and one to maintain the reference to the last node;
• A default constructor that initializes to null the value and the pointer;
• Getter methods to retrieve the first and the last node of the list;
• Business method useful to manipulate the list.

The structure of the LinkedList class is:

Extract of LinkedList class

The core of the Linked List has two class variables: one to maintain the reference of the head of the list (first) and one to maintain the tail of the list (last). When the list is created both are null and need to be updated for every manipulation of the list.

Moreover the Linked List core class needs to implements the Iterable interfaces to be iterate.

Manipulations: add

After we create the list we can add Node to populate it. It is possible to add a new Node on top of the list with the addFirst method or add a new Node in tail with the addLast method.

The addFirst method needs to distinguish two cases:

• Empty list: in case of an empty list, the node that will be to add will coincides with first and last nodes because it will be the only one node contained in a list
• Full list: in case of the full list, is needed save on a temporary node the actual first node, set the first node with the new node and add a reference point from the new node to the temporary node

This is the addFirst implementation:

Add first method on LinkedList class

Also the addLast method needs to distinguish two cases:

• Empty list: in case of an empty list, the node that will be to add will coincides with first and last nodes because it will be the only one node contained in a list
• Full list: in case of the full list, is needed to set the pointer from actual last to the new node and overwrite the last node with the new node

This is the addLast implementation:

Add last method on LinkedList class

In both add method will be initialized a new object node withe the value received in input.

Manipulations: remove

In addition to the operations of add it is possible to remove any node by the linked list. The operations of remove can acts on the first node with the removeFirst operation or on the tail with the removeLast operations

The removeFirst method needs to distinguish two cases:

• Empty list: in case of an empty list, the operation will be stopped throwing a custom exception
• Full list: in this case is needed to override the value of the first variable with the pointer to the next node of the same first node. The old first node will remain without reference and will be caught by the garbage collector

This is the removeFirst implementation:

Remove first method on LinkedList class

Also the removeLast method needs to distinguish three cases:

• Empty list: in case of an empty list, the operation will be stopped throwing a custom exception
• One-element list: the linked list needs to be iterate, if the current node has a null pointer for the next node is needed to set to null the first and the last node because the list is now empty. The old first node will remain without reference and will be caught by the garbage collector
• Two-or-more element list: the linked list need to be iterate, and when it is found a current node that has a next node that not has the next pointer is needed to set null the pointer of the current node and replace the last node with the current. The old last node will remain without reference and will be caught by the garbage collector

This is the removeLast implementation:

Remove last method on LinkedList class

Sizing and scanning of the list

To count the objects included into the linked list there is no global counter, but the size of the list is calculated at runtime iterating the entire list.

To iterate the list we can start with the first element and, until the next is null, override the actual node with the pointer to the following:

Sizing the list

At every iteration increment the counter.

This cycle is internal to the LinkedList class, but if you would iterate the entire list by an external class you need to implement the iterator() method:

Implementation of the hasNext() and next() method of the iterator

Once you implement this method you can iterate an instance of LinkedList class simply using a for loop:

Example of iteration

Conclusion

These examples are useful to understand the concept of Collection and familiarize with the reference between Java objects.

You can use this approach when you need to customize the behavior of the standard collection or you can you these examples for educational purposes.

On GitHub repository you can find the complete code and many examples of use.

Follow me on GitHub: repository