Linked List | Data Structures

A brief introduction

Linked List is a linear collection of objects, which is composed of nodes pointing to the next node. Each node contains a value and a reference to the next node in the sequence. Most of the operations applied in a linked list (add, remove, search, etc.) will require sequencial scanning most of the time.

single-linked-list
As you can notice, each node will always have a pointer to the next node and a value, this is called a single linked list. If a node has a link to the previous and to the next one, it is called a double linked list or a circular linked list.

Implementation

The first step will be creating a node class:

public class Node<T>{

    private Node next;
    private T value;

    public Node(){
        
    }
    
    public Node(T value){
        this.value = value;
    }
    
    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }
}

This is a POJO (Plain Old Java Object) of a Node class, which contains a value and another Node that will be the “Next” node. If you ask yourself about the “T” I have in there, I am declaring the Node class as Generic, enabling the option to choose what datatype to use. Now, we will be creating varios operations used, starting with the add.

public class MyLinkedList<T>{

    private Node head;
    private static int counter;

    public void add(T value){
         
        if (head == null) {
            head = new Node(value);
        } else {
            Node temp = new Node(value);
            Node current = head;

            while (current.getNext() != null) {
                current = current.getNext();
            }

            current.setNext(temp);
        }

        counter++;
    }
}

The Add Operation is simple, basically, you will check if the head node exists or not. If it doesn’t exist, you will be creating a new one passing the value as parameter. Other than that, you will need to the last node in the list and insert the temporal node.

We have various options to remove a node: Remove the first element, remove a specific value or remove by an index.

For the remove() operation, we will only need to point the head to it’s next node instead of the current one.

public void remove(){
     if(head == null){
         return;
     }

     head = head.getNext();
     counter--;
}

In this method, we will be doing a sequential scan through each node, having a counter per iteration until it matches to the position sent.

public void remove(int index) {
      if (head == null) {
          return;
      }

      if(index > counter){
          throw new IndexOutOfBoundsException("Index out of range");
      }

      int position = 0;

      Node targetNode = head;
      Node leftNode = null;

      while (targetNode.getNext() != null) {

          if (index == position) {
              if (leftNode != null) {
                  leftNode.setNext(targetNode.getNext());
              }

              targetNode.setNext(null);
              counter--;
          } else {
              leftNode = targetNode;
              targetNode = targetNode.getNext();
          }
          position++;
      }
}

This is almost the same as the previous method, but instead we compare the values with the “equals”. Remember there’s a difference when comparing object using “equals” and “==”. I added a boolean to stop iterating through the nodes.

    public void remove(T object) {
        if (head == null) {
            return;
        }

        boolean found = false;
        Node targetNode = head;
        Node leftNode = null;
        while (targetNode.getNext() != null || !found) {

            if (targetNode.getValue().equals(object)) {
                if (leftNode != null) {
                    leftNode.setNext(targetNode.getNext());
                }
                found = true;
                targetNode.setNext(null);
                counter--;
            } else {
                leftNode = targetNode;
                targetNode = targetNode.getNext();
            }
        }
    }

Remember that when doing an sequential scan and you are trying to remove or replace a node, we will need another node, “left node” to be able to disconnect successfully the target node, setting target’s next node to null and passing it’s next nodes to the “left node”. However, when we are going to traverse a linked list, we need to point to the last node and assign each previous node to it. As you can notice, we use three nodes, a previous, current and next. While we have nodes, the next node of the current one should be the previous in order to successfully traverse the list and correctly assign the nodes.

    public void traverse() {
        Node prev = null;
        Node current = head;
        Node next;

        while (current != null) {
            next = current.getNext();
            current.setNext(prev);
            prev = current;
            current = next;
        }

        head = prev;
    }

These are the basic operations that a linked list should have. With this implementation, you could create the other operations like finding a node, checking if it exists, peek, etc. Please let me know if you have any questions or you just want to comment something.