Single Linked List Exposition

It's one thing to understand how a data structure works, but you need to have the wit to implement it — and by doing that, it thickens your understanding about it.

It took me quite a while to understand most of the popular data structures, and Linked List was one them. So, for a refresher for myself I decided to implement a Single Linked List again in Java, and now I want to share it with you.  If you’re struggling to understand Linked List, hopefully, this piece will be helpful.

Introduction

A Linked List is a linear data structure, which entails a collection of separate objects called nodes or elements.

Sample Single Linked List
Figure 1.

A node (or element) is a single unit of a Linked List. It consists of two items as shown in Figure 2. — the Data which can be of any type like Integer, String, Objects e.t.c and a Reference, which is a link or pointer to the next node or a null.

Node
Figure 2.

Another way to understand this, is conceptualizing the node as a container which holds two items: The Data, which is the information intended to be stored and the Reference, which is a link to the node in front of it or a null — if there isn't a another node present. The Reference can also be called next pointer, next link, link or next node. They all mean the same thing.

Head

This is the entry point of the List, it is also called the Root Node. It's imperative to note that the head isn't a separate node, but the reference to the first node on the List, hence the entry point.

Null

This is an empty location in the computer memory. The last node in the List will always have a reference to null — this is why some people refer to the last node as the tail. When a node in the List reference equals to null, it means you are at the end of the List.

The Node Class

I've established above that a node holds two items, the Data (of any type) and a Reference (to the next node or null). By default, the reference has a null value and needs to be modified when adding a new node to the List. I will show you how this is done if you aren't jaded already.

public class Node<AnyDataType> {
private AnyDataType data;
private Node<AnyDataType> nextNode = null;

Node(AnyDataType data) {
this.data = data;
}
}

To create a new node object, you simply instantiate the node class with the data you want to store. As shown below, node1 reference is initially null until it was explicitly pointed to node2. Now, node2 has a reference to null which makes it the last node. The links go on and on and on.

Node<T> node1 = new Node<>(data);
Node<T> node2 = new Node<>(anotherData);
node1.nextNode = node2;

Operations Summary

Let me set some expectations before the main implementation. . . For the sake of this post I implemented methods which I think are the most important ones. These include:  add, remove, print, clear, indexOf, isEmpty and size.

Implementation

To make sure the Linked List implementation supports any data type, I used the Java Generic Types Interface and for comparing of objects I used Comparable  interface. Finally, I utilized some basic Object Oriented Programming concepts.

The list of classes implemented are the following, Node Class: for the node objects, List Interface:  which has the collection of abstract methods, LinkedList Class: which implements the List Interface and finally, the Applications class for testing. 


Node Class 

public class Node<T extends Comparable<T>> {
private T data;
private Node<T> nextNode = null;

Node(T data) {
this.setData(data);
}

public T getData() {
return data;
}

private void setData(T data) {
this.data = data;
}

public Node<T> getNextNode() {
return nextNode;
}

public void setNextNode(Node<T> nextNode) {
this.nextNode = nextNode;
}

@Override
public String toString() {
return this.data.toString();
}
}

List Interface

public interface List<T extends Comparable<T>> {

void add(T data);

void remove(T data);

T get(int index);

void print();

void clear();

int indexOf(T data);

int size();

Boolean isEmpty();
}

1.  add(data)Appends the specified node to the List.

@Override
public void add(T data) {
++nodeSize;
if (head == null) {
this.head = new Node<>(data);
} else {
addDataAtTheBeginning(data);
//addDataAtTheEnd(data, this.head);
}
}

One unique thing about Linked List is its flexibility. They are dynamic and with that I mean, they can grow to any capacity. Like arrays for an example, you must specify the capacity of the array at compile time before you can use it. Linked List however, allocates the needed memory at runtime, making it very flexible to use. What’s even more intriguing (to me at least) is the ability to append nodes at the Beginning of the List as shown in Figure 3 or at the End of the List as shown in Figure 4.

Adding element at the begining of a the Linked list

Figure 3.

private void addDataAtTheBeginning(T data) {
Node<T> currentNode = new Node<>(data);
currentNode.setNextNode(this.head);
this.head = currentNode;
}

Adding a new node to the beginning of the List is fast, the new node is simply pointed to the head and then the new node set to head. This operation takes constant time O(1) as it doesn’t involve traversing through the whole List. But, of course, adding elements at the beginning of the list will change the order of the List as well. Remember this!

Add elements at the end of the list

Figure 4.

private void addDataAtTheEnd(T data, Node<T> node) {
if (node.getNextNode() != null) {
addDataAtTheEnd(data, node.getNextNode());
} else {
Node<T> newNode = new Node<>(data);
node.setNextNode(newNode);
}
}

To add a node to the end of the List requires pointing the last node to the new node that’s to be added. This operation takes linear time O(n) to add an element to the end of the List. I guess it sounds like a bad idea already since the operation will require a full iteration through the List to find the last node which is pointing to null.

A solution to making this operation efficient is, to keep a reference of the last node i.e. the tail, then we can simply append the new node to the tail and make the new node the last node. . . Try it!


2.  remove(data)Removes the first occurrence of the specified data from the List, if it is present.

@Override
public void remove(T data) {
if (this.head == null) return;

--this.nodeSize;

if (this.head.getData().compareTo(data) == 0) {
this.head = this.head.getNextNode();
} else {
remove(data, this.head, this.head.getNextNode());
}
}

private void remove(T data, Node<T> previousNode, Node<T> currentNode) {
while (currentNode != null) {
if (currentNode.getData().compareTo(data) == 0) {
previousNode.setNextNode(currentNode.getNextNode());
currentNode = null;
return;
}
previousNode = currentNode;
currentNode = previousNode.getNextNode();
}
}

Deleting a node is done by pointing the previous node to the next node of the current node that is to be deleted as shown in Figure 5, then setting the current node to null for garbage collection.

Delete a node
Figure 5.

The cost of removing a node in a Single Linked List does vary depending on the position of the node. Removing the first node in a List will be very fast compared to removing the last node; this is because we have a reference to the first node which is the head. To remove the head from the List, no need to search through the other elements to find it. For such operations, it takes constant time O(1) to remove an element in the List. On the contrary, it implies removing an element from other positions in the List will take linear time O(n)  — if the reference to the node isn't known.


3.  get(index)Returns the data at the specified position in the List.

@Override
public T get(int index) {
if (this.head == null) return null;

Node<T> currentNode = this.head;
int count = 0;
while (count < index) {
++count;
currentNode = currentNode.getNextNode();
}
return currentNode.getData();
}

This operation is done by traversing through the List to the particular index size being passed and returning the data of the node at the specified index position. For the worst case, this operation will require going through the entire List, making it have a time complexity of O(n).  
If you are curious about what happens if an index size exceeds the size of the List, the answer is — it throws a NullPointerException. A way to prevent this will be to check first if the List size exceeds the index size or not, before moving on and giving a nice message that suits.


4.  print()This traverses through the List and prints the data of every node.

@Override
public void print() {
if (this.head == null) return;
Node<T> currentNode = this.head;
while (currentNode != null) {
System.out.println(currentNode.getData());
currentNode = currentNode.getNextNode();
}
}

This operation takes linear time O(n) since printing all the data in the List involves traversing through the to end of the List.


5.  clear()Removes all of the elements from the List.

@Override
public void clear() {
if (this.head == null) return;
this.head = null;
this.nodeSize = 0;
}

To clear the List, you basically set the head to null, and everything else becomes garbage, ready for collection. Java has an automatic garbage collection, so there’s nothing to worry about.


6.  indexOf(data)Returns the index of the first occurrence of the specified element in the List, or -1 if the List does not contain the element.

@Override
public int indexOf(T data) {
Node<T> currentNode = this.head;
int index = -1;
while (currentNode.getNextNode() != null) {
++index;
if (currentNode.getData().compareTo(data) == 0) {
return index;
}
currentNode = currentNode.getNextNode();
}
return -1;
}

For this operation, you traverse through the List one element at a time and compare the data of each of them to the arguments provided.  At the worst case, you'd be going through the complete List, giving a complexity of O(n).


7.  size()Returns the number of elements in the List.

@Override
public int size() {
return this.nodeSize;
}

Hopefully, you’ve noticed the adjustments made to the nodeSize variable which is, Incremented: whenever a new element is appended to the List, Decreases: when an element is removed from the List, and also Set to Zero: when the List is cleared. This operation returns the current value of the nodeSize variable at a constant time O(1) since I've kept track of the List size as I perform different operations.


8.  isEmpty()Returns true if the List contains no elements and false if it does.

@Override
public Boolean isEmpty() {
return nodeSize == 0;
}

Linked List Class — This class implements the List Interface.

public class LinkedList<T extends Comparable<T>> implements List<T> {

private Node<T> head;
private int nodeSize;

@Override
public void add(T data) {
++nodeSize;
if (head == null) {
this.head = new Node<>(data);
} else {
addDataAtTheBeginning(data);
//addDataAtTheEnd(data, this.head);
}
}
//O(1)
private void addDataAtTheBeginning(T data) {
Node<T> currentNode = new Node<>(data);
currentNode.setNextNode(this.head);
this.head = currentNode;
}
//O(n)
private void addDataAtTheEnd(T data, Node<T> node) {
if (node.getNextNode() != null) {
addDataAtTheEnd(data, node.getNextNode());
} else {
Node<T> newNode = new Node<>(data);
node.setNextNode(newNode);
}
}

@Override
public void remove(T data) {
if (this.head == null) return;

--this.nodeSize;

if (this.head.getData().compareTo(data) == 0) {
this.head = this.head.getNextNode();
} else {
remove(data, this.head, this.head.getNextNode());
}
}

private void remove(T data, Node<T> previousNode, Node<T> currentNode) {
while (currentNode != null) {
if (currentNode.getData().compareTo(data) == 0) {
previousNode.setNextNode(currentNode.getNextNode());
currentNode = null;
return;
}
previousNode = currentNode;
currentNode = previousNode.getNextNode();
}
}

@Override
public T get(int index) {
if (this.head == null) return null;

Node<T> currentNode = this.head;
int count = 0;
while (count < index) {
++count;
currentNode = currentNode.getNextNode();
}
return currentNode.getData();
}

@Override
public void print() {
if (this.head == null) return;
Node<T> currentNode = this.head;
while (currentNode != null) {
System.out.println(currentNode.getData());
currentNode = currentNode.getNextNode();
}
}

@Override
public void clear() {
if (this.head == null) return;
this.head = null;
this.nodeSize = 0;
}

@Override
public int indexOf(T data) {
Node<T> currentNode = this.head;
int index = -1;
while (currentNode.getNextNode() != null) {
++index;
if (currentNode.getData().compareTo(data) == 0) {
return index;
}
currentNode = currentNode.getNextNode();
}
return -1;
}

@Override
public int size() {
return this.nodeSize;
}

@Override
public Boolean isEmpty() {
return nodeSize == 0;
}
}

How To Use

As said earlier, the Linked List is generic hence it can take any data type which includes objects.

public class Application {

public static void main(String... args) {
List<Integer> linkedList = new LinkedList<>();

linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);

linkedList.remove(2);
linkedList.indexOf(3);
linkedList.print();

System.out.println(linkedList.isEmpty());
System.out.println(linkedList.get(2));
System.out.println(linkedList.size());

linkedList.clear();
linkedList.print();
System.out.println(linkedList.size());
}
}

Limitations and Constraints

  • While Linked List can be very useful to store data, it is important to know that it needs extra memory to store the references. If memory matters for your use-case, Linked List won't be an excellent choice.
  • Linked List does not support random access.  As such, the cost of accessing an element in the List isn’t constant. Its efficiency depends largely on the position of the node and the number of elements in the List.
  • Single Linked List is difficult to reverse backward, a simple solution to this will be a Doubly Linked List which points to the previous and next node.
  • Linked List's dynamic nature has a constraint. Whenever memory is dynamically allocated, it utilizes the Heap Memory. And this action is only possible if there is available space in the Heap.

Summary

Your aim of using any data structure should always be efficiency. . . Generally, the insertion and deletion operations are very efficient because it only involves updating references/pointers which can be done in constant time O(1) assuming the reference to the node is known. However, to find the reference of a node in the List will still take O(n)

As it is with every data structure, your use-case should help you decide which data structure to use. If you need more insertion and deletion operations, it is a great reason for you to use Linked List :) 

Thanks for reading — See complete code here

Bobai

Software Development Engineer.