How to implement Generic Singly Linked List in Java - Part 1
This article describes on how to implement a generic singly linked list in Java.
Srivastava Bodakunti
In this post, we will use Java generics to implement Singly Linked List and test it. I assume that you know what generics in Java is. But still you can follow the code, generics is not rocket science. In a nutshell, generics enable types (classes and interfaces) to be parameters when defining classes, interfaces and methods. Code that uses generics has stronger type checks at compile time. Let's start with our linked list implementation.
Before discussing linked list implementation, I want to describe what linked list (I will mention linked list instead of singly linked list to save few key strokes) is:
A linked list is represented by a pointer to the first node of the linked list. This first node is referred as head. If our linked list is empty, this head value is null which points to nothing. As linked list is a sequence of nodes, each node contains some data of type T (T can be int, float, char, String, etc) and a pointer (or reference) to the next node. So, we need a Node class. Before creating that, what all opeations we perform in our Linked List?
Here we will discuss adding an item (at end), adding an item (element/data/value) at the begninning, adding an item at some position, get the value at particular position, get middle element, check if a value exists, update data at some position, reverse linked list, get the size of the linked list, check if list is empty, remove data at some position, delete given element, clear the linked list. For these operations we will define an interface which our Linked List class implements.
So let's create an interface called IList.java and add the following code to it which has operations described above.
/*
* Copyright (c) 2020.
* @author: Srivastava Bodakunti
* @version 2020.10.19.001
*/
package com.velocitybytes.list;
public interface IList<T> {
void add(T data);
void addFirst(T data);
void add(T data, int index);
T get(int index);
T getMiddle();
boolean exists(T data);
void set(T data, int index);
void reverse();
int size();
boolean isEmpty();
T remove(int index);
void delete(T data);
void clear();
}Note how we have used generics. The interface is written as IList<T>, which can accept an appropriate type. The methods are also written to accept and return data of type T. Okay, so now our interface is ready!
Node:
Coming back to Node class. So, next, we will create the Node class (Node.java) with Generics: Node<T>
package com.velocitybytes.list;
import lombok.Getter;
import lombok.Setter;
/**
* Implementation of a node object for {@code SinglyLinkedList} class.
*
* @author Srivastava Bodakunti
* @version 2020.10.19.001
*/
@Getter
@Setter
public class Node<T> {
// *************************************************************************
// Invariant of Node:
// (1) Instance variable data
// (2) Instance variable next will either contain a reference to the next
// node in a SinglyLinkedList, or, in case that a node is the last one in a
// SinglyLinkedList, it will contain a null reference.
// *************************************************************************
public T data;
public Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
@Override
public String toString() {
if (data != null) {
return this.data.toString();
} else {
return "";
}
}
}Here, I have used lombok which is a Java library/plugin which can inject getters, setters, equals methods, constructor with annotations in our class. I used @Getter and @Setter annotations that generates a getter and setter for each field, respectively. As we have two fields, the getters and setters would be generated as getData(), setData(...), getNext(), setNext(...). And our constructor takes data of type T and initialize the data and next fields and whenever we create a new node with some data, it should point to null (this.next = null;). I have overridden toString() method to return data which we will use later. Now our Node class is ready. Next we need to implement Singly Linked List.
Singly Linked List:
Create a file SinglyLinkedList.java and our class should now implement IList interface which we created earlier. See the below code snippet:
package com.velocitybytes.list.impl;
import com.velocitybytes.list.IList;
/**
* Implementation of a general purpose SinglyLinkedList class.
*
* @author Srivastava Bodakunti
* @version 2020.10.20.001
*/
public class SinglyLinkedList<T> implements IList<T> {
}Now the IDE will yell at you as haven't implemented the methods declared in IList interface. So implement them. Note how we are using generics here: SinglyLinkedList<T>
package com.velocitybytes.list.impl;
import com.velocitybytes.list.IList;
/**
* Implementation of a general purpose SinglyLinkedList class.
*
* @author Srivastava Bodakunti
* @version 2020.10.20.001
*/
public class SinglyLinkedList<T> implements IList<T> {
@Override
public void add(T data) {
}
@Override
public void addFirst(T data) {
}
@Override
public void add(T data, int index) {
}
@Override
public T get(int index) {
return null;
}
@Override
public T getMiddle() {
return null;
}
@Override
public boolean exists(T data) {
return false;
}
@Override
public void set(T data, int index) {
}
@Override
public void reverse() {
}
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public T remove(int index) {
return null;
}
@Override
public void delete(T data) {
}
@Override
public void clear() {
}
}Okay, now that we have some kind of skeleton for our linked list. We will proceed with implementation of each operation I described earlier. As linked list should have head pointer which points to first node, we need head field of type Node<T> and as we add or remove items we need to maintain the size of the linked list. So we also need size field which is an integer. So add the below code snippet in your SinglyLinkedList class.
// *************************************************************************
// Invariant of SinglyLinkedList:
// (1) If the list is empty (size = 0), head.data refers to null.
// (2) If the list is not empty, head.data refers to a null node, and
// head.next refers to the first non-empty node in the list.
// *************************************************************************
private Node<T> head;
private int size;But when we instantiate our SinglyLinkedList, the size should be zero as we don't have any elements yet. So we initialize that in our constructor by adding like this:
/**
* Default constructor for the SinglyLinkedList class.
* It creates an empty list.
*/
public SinglyLinkedList() {
this.size = 0;
}add():
Starting with "add" operation in linked list. The add() method adds an item at the end of the linked list. It takes data as a parameter. If data is null we don't want to do anything and simply return. If our linked list is empty, head points to null, so we create first node and assign to head. If head is not null, we need to traverse till end of the list to find the last node and set its next pointer to point to new node created and finally we increase the size of the linked list by 1. I have used recursion to find the last node of the list. See the below code snippet.
/**
* Adds an element at the end of the list
*
* @param data the value to be added at the end of the list
*/
@Override
public void add(T data) {
// if data is null
if (data == null)
return;
// if empty linked list
if (head == null) {
head = new Node<>(data);
} else {
// create a new node
Node<T> newNode = new Node<>(data);
// get the last node in linked list
Node<T> lastNode = getLastNode(head);
lastNode.setNext(newNode);
}
size++;
}
private Node<T> getLastNode(Node<T> node) {
return node.getNext() != null ? getLastNode(node.getNext()) : node;
}addFirst():
In list, we may want to add an item at the beginning of the list. Adding at beginning is very simple. But careful, don't assign the new node directly to head of the linked list, if we do so we will lose the connection to rest of the list. Set new node's next to head, so it will have connection to linked list and then modify the head to point to new node. Finally, increase the size of the list by 1. See the below code snippet.
/**
* Adds an element at the beginning of the list
* @param data the value to be added at the beginning of the list
*/
@Override
public void addFirst(T data) {
if (data == null)
return;
Node<T> newNode = new Node<>(data);
if (head != null)
newNode.setNext(head);
head = newNode;
size++;
}size():
If we want to know the size of the linked list, we can write a method that simply returns the size as we maintain the size in every add/delete operation.
/**
* Obtains the number of elements in the list
* @return size: number of elements in the list
*/
@Override
public int size() {
return size;
}isEmpty():
If we want to find if the list is empty, simply check if its size is zero which returns a boolean value.
/**
* Finds whether the list is empty
* @return {@code true} if list is empty, {@code false} otherwise
*/
@Override
public boolean isEmpty() {
return size == 0;
}add() at given position:
If we want to add an element at a given position, we need to take position parameter along with data. Find previous and next node wrt to given position. If index is not in a given list, we throw IndexOutOfBoundsException with custom message. See the below code snippet.
/**
* Adds an element at the given index position.
*
* @param data the value to be stored in the SinglyLinkedList
* @param index desired location
* @throws IndexOutOfBoundsException indicates that the index is not valid.
*/
@Override
public void add(T data, int index) {
if (data == null)
return;
// if negative index
if (index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// if first position
if (index == 0) {
addFirst(data);
return;
}
// if last position
if (index == size()) {
add(data);
} else if (index < size()) {
Node<T> newNode = new Node<>(data);
Node<T> beforeNode = getNode(index - 1);
Node<T> afterNode = getNode(index);
newNode.setNext(afterNode);
assert beforeNode != null;
beforeNode.setNext(newNode);
size++;
} else {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
@Nullable
private Node<T> getNode(int index) {
if (isNotElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
if (index == 0)
return head;
if (index == size() - 1)
return getLastNode(head);
int cursor = 0;
Node<T> cursorNode = head;
while (cursor <= index) {
if (cursor == index) {
return cursorNode;
} else {
if (cursorNode != null) {
cursorNode = cursorNode.getNext();
}
cursor++;
}
}
return null;
}
private boolean isNotElementIndex(int index) {
return index < 0 || index > size - 1;
}
@NotNull
@Contract(pure = true)
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}get() element at given position:
To get an element at a given position, take the position parameter. We need to traverse the list till the position given. See the below code snippet.
/**
* Retrieves the element at a given index position.
*
* @param index location of the desired item
* @return the element at the desired index position
* @throws IndexOutOfBoundsException indicates that the index is not valid.
*/
@Override
public T get(int index) {
if (isNotElementIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} else {
Node<T> cursorNode = head;
for (int i = 0; i < index; i++) {
cursorNode = cursorNode.getNext();
}
return cursorNode.getData();
}
}getMiddle():
If we want to find the middle element of the list, we use "Runner" technique. The runner (or second pointer) technique is used in many linked list problems. The runner technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other. The fast node might be ahead by a fixed amount, or might be hopping multiple nodes for each one node that the slow node iterates through, Here we used fast and slow pointer, where fast pointer advances by two elements for every one move that slow pointer makes. When fast pointer hits the end of the linked list, slow pointer will be at the midpoint. See the below code snippet.
/**
* Method that finds the middle element of the list
* @return returns the middle element of the list
*/
@Override
public T getMiddle() {
Node<T> slowPtr = head;
Node<T> fastPtr = head;
if (head != null) {
while (fastPtr != null && fastPtr.getNext() != null) {
fastPtr = fastPtr.getNext().getNext();
slowPtr = slowPtr.getNext();
}
return slowPtr.getData();
} else {
return null;
}
}exists():
If we want to check an element exists in our linked list, we need to traverse the list and compare the data with given data. See the below code snippet.
/**
* Checks whether the given element exists in the list
* @param data the value to be checked
* @return boolean value: {@code true} if exists else {@code false}
*/
@Override
public boolean exists(T data) {
boolean dataExists = false;
if (data == null)
return false;
Node<T> cursorNode = head;
while (cursorNode != null) {
if (cursorNode.getData() == data || cursorNode.getData().equals(data)) {
dataExists = true;
break;
}
cursorNode = cursorNode.getNext();
}
return dataExists;
}set():
In case if we want to modify data at some given position, traverse the list till the given postion and set the updated data. See the below code snippet.
/**
* Changes the value of the element at a given index position.
*
* @param data the value to substitute the current one
* @param index location of the desired item
* @throws IndexOutOfBoundsException indicates that the index is not valid.
*/
@Override
public void set(T data, int index) {
if (data == null)
return;
if (isNotElementIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} else {
Node<T> cursorNode = head;
for (int i = 0; i < index; i++) {
cursorNode = cursorNode.getNext();
}
cursorNode.setData(data);
}
}reverse():
Reversing a linked list is an interview question. We reverse the list by changing links between the nodes. See the below code snippet.
/**
* Reverses the list
*/
@Override
public void reverse() {
Node<T> prevNode = null;
Node<T> nextNode = head, cursorNode = head;
while (nextNode != null) {
nextNode = nextNode.getNext();
cursorNode.next = prevNode;
prevNode = cursorNode;
cursorNode = nextNode;
}
head = prevNode;
}remove() an element at given position:
To remove an element at a given position, traverse the list till the given index to find the node of it and set its next to next pointer in the found node's next. Finally decrement the size by 1 and return the element removed. See the below code snippet.
/**
* Removes the element at the given index position.
*
* @param index integer that represents the position of the item to be removed
* @throws IndexOutOfBoundsException indicates that the index is not valid.
*/
@Override
public T remove(int index) {
if (isNotElementIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} else {
Node<T> cursorNode = head;
for (int i = 0; i < index - 1; i++) {
cursorNode = cursorNode.getNext();
}
T removed = cursorNode.getNext().data;
cursorNode.next = cursorNode.getNext().getNext();
size--;
return removed;
}
}delete() given data:
Deleting the given data is similar to remove(). See the below code snippet.
/**
* Deletes the first occurrence of given data
* @param data data item to be deleted
*/
@Override
public void delete(T data) {
if (head != null) {
Node<T> currentNode = head;
Node<T> previousNode = head;
while (currentNode != null) {
if (currentNode.getData() == data) {
previousNode.setNext(currentNode.getNext());
size--;
break;
} else {
previousNode = currentNode;
currentNode = currentNode.getNext();
}
}
}
}clear():
Clearing the list means, setting each node's data and next field to null. So, later garbage collector takes care of it.
/**
* Clear the list
*/
@Override
public void clear() {
removeAllElements();
}
private synchronized void removeAllElements() {
if (head != null) {
for (Node<T> cursorNode = head; cursorNode != null;) {
Node<T> nextNode = cursorNode.getNext();
cursorNode.data = null;
cursorNode.next = null;
size--;
cursorNode = nextNode;
}
}
}loopExists():
Checking if there is a loop exists is an interview question, we use the same "Runner' technique. See the below code snippet.
public boolean loopExists() {
boolean loopExists = false;
if (head != null) {
Node<T> slowPtr = head, fastPtr = head;
while (slowPtr != null && fastPtr != null && fastPtr.getNext() != null) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext().getNext();
if (slowPtr == fastPtr) {
loopExists = true;
break;
}
}
}
return loopExists;
}toString(), equals(), hashCode():
/**
* Custom toString implementation
* @return returns list in format [x, y, z]
*/
@Override
public String toString() {
StringBuilder format = new StringBuilder("[");
Node<T> cursorNode = head;
while (cursorNode != null) {
format.append(cursorNode.toString());
cursorNode = cursorNode.getNext();
if (cursorNode != null) {
format.append(", ");
}
}
format.append("]");
return format.toString();
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList<?> that = (SinglyLinkedList<?>) obj;
if (size != that.size)
return false;
return Objects.equals(head, that.head);
}
@Override
public int hashCode() {
int result = head != null ? head.hashCode() : 0;
result = 31 * result + size;
return result;
}You can read part 2 for testing Implement a Generic Singly Linked List in Java - Part 2
Thank you!
