DEV Community

Juan Sedano
Juan Sedano

Posted on • Originally published at jsedano.dev on

Linked list

My notes on Linked list with an implementation in Java.

You can find the complete code for this and other data structures here: data structures and algorithms

A linked list is a data structure that uses nodes that hold both a value and a reference to the next node.

Common Operations for a linked list includes:

Operation Complexity
get(indexOfElement) O(n)
insert(index, value) O(n)
find(value) O(n)
delete(value) O(n)

This is the node we will be using:

node

public class SingleNode<T extends Comparable<? super T>>{
    private T value;
    private SingleNode<T> nextNode;
Enter fullscreen mode Exit fullscreen mode

In this implementation of the linked list we will hold both a reference to the head and the tail of the list. We will be only accepting objects of classes that implement the Comparable interface since that way we can easily compare between two values.

public class LinkedList<T extends Comparable<? super T>> {

    private int size;
    private SingleNode<T> head;
    private SingleNode<T> tail;
Enter fullscreen mode Exit fullscreen mode

At the beginning the list will look like this:

empty linked list

If we add an element to the list it will look like this, with both head and tail pointing to the same node.

one element linked list

To append an element at the end of the list we can use the tail reference, add the element as the next element of the tail:

append linked list 1

Then we update the tail reference:

append linked list 2

public void add(T value) {
    if(size == 0) {
        head = new SingleNode<T>(value, null);
        tail = head;
    } else {
        tail.setNextNode(new SingleNode<T>(value, null));
        tail = tail.getNextNode();
    }
    size++;
}
Enter fullscreen mode Exit fullscreen mode

For prepending an element to the beginning of the list we first create the new element and set the head as the new elements next node:

prepend linked list 1

And then we update the head reference

prepend linked list 2

public void prepend(T value) {
    if(size == 0) {
        head = new SingleNode<T>(value, null);
        tail = head;
    } else {
        head = new SingleNode<T>(value, head);
    }
    size++;
}
Enter fullscreen mode Exit fullscreen mode

To find a value from an index we just iterate the linked list counting every node.

private SingleNode<T> getSingleNodeByIndex(int index) {
    if(size <= 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    if(index == 0) {
        return head;
    }
    if(index == size - 1 ) {
        return tail;
    }

    SingleNode<T> singleNode = head.getNextNode();
    for(int i = 1; i < index; i++) {
        singleNode = singleNode.getNextNode();
    }
    return singleNode;
}
Enter fullscreen mode Exit fullscreen mode

To find the index of an element using the value we just iterate the linked list until we run out of list, or we find the element.

public int indexOf(T value) {
    SingleNode<T> singleNode = head;
    for(int i = 0; i < size; i++) {
        if (singleNode.getValue().compareTo(value) == 0) {
            return i;
        } else {
            singleNode = singleNode.getNextNode();
        }
    }
    return -1;
}
Enter fullscreen mode Exit fullscreen mode

To remove an element using its value we will use two references, previous and current, and when current points to the value we want to remove we will use the previous reference to take out of the list the element we want to remove.

Suppose in this case current points to the value we want to remove:

remove linked list 1

We update the next node of previous:

remove linked list 2

public void removeByValue(T value) {
    if(size == 0) {
        return;
    }
    SingleNode<T> beforeValue = null;
    SingleNode<T> valueToCompare = head;

    for(int i = 0; i < size; i++) {
        if (valueToCompare.getValue().compareTo(value) == 0) {
            if(i == 0) {
                head = head.getNextNode();
            } else {
                beforeValue.setNextNode(valueToCompare.getNextNode());
                if (i == size - 1) {
                    tail = beforeValue;
                }
            }
            size--;
            break;
        } else {
            beforeValue = valueToCompare;
            valueToCompare = valueToCompare.getNextNode();
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Insertion at any index works by getting a reference to the node right before the index where we want to insert, and then updating the next node references.

adding at any index

public void add(T value, int index) {
    if(size <= 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    if(index == 0){
        prepend(value);
    } else if (index == size - 1) {
        add(value);
    } else {
        SingleNode<T> beforeNewNode = getSingleNodeByIndex(index - 1);
        beforeNewNode.setNextNode(new SingleNode<T>(value, beforeNewNode.getNextNode()));
        size++;
    }
}
Enter fullscreen mode Exit fullscreen mode

Download the complete code for this and other data structures here: data structures and algorithms

Top comments (0)