How to implement LinkedList in Java

How to implement LinkedList in Java is very common interview question. Let’s see how to implement it in Java. Before we jump into implementation let’s see What a LinkedList is. This post is more for an education perspective, and not full-fledged implementation of LinkedList

How is this post organised

• Introduction to LinkedList
• Node class
• Basic API’s
• API Implementation
• Everything Together

Introduction to LinkedList

LinkedList is made of Node’s inter-connected to each other by a single or a double link.

The picture above explains one way LinkedList. Each Node in a LinkedList contains some data and a pointer to the next node in the list.

Node Class

So now we know, the basic unit of creating the linked list is to create a Node class. Let’s quickly see the code

class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T data, Node<T> next) {
      this.data = data;
      this.next = next;
    }
}

Here we are using Java Generics to ensure that we have type-safe implementations. We need to two fields, one to store the data and the other to store a pointer to next node in the list

Basic API’s

Now that we have basic building block in the place, lets just see what are the API’s we would support for out class. To keep things simple, we would just provide basic API’s. Let’s see these API’s

public int size()
public void add(T data) 
public T get(int index)

API Implementation

Let’s see the code for the add() API

 public void add(T data) {
    if(data == null) {
      throw new IllegalArgumentException("Null data received");
    }

    Node<T> node = new Node<T>(data, null);

    if(head == null) {
      head = tail = node;
    } else {
      tail.next = node;
      tail = node;
    }
    size++;
 }

We maintain two Node’s Head and Tail for simplicity of adding. We create a Node instance, and if it’s 1st element we put head and tail as same as new Node instance, else we add pointer to tail node and update tail.

Now that the concept is clear, you can play around implementing different API’s Let’s see a very crude implementation of get() API

public T get(int index) {
    if(size == 0) {
      return null;
    }

    if(index >= size) {
      throw new NoSuchElementException("No such element");
    }

    Node<T> node = head;
    // lets find the node
    for(int i = 0; i < index; i++) {
      node = node.next;
    }
    return node.data;
  }

We have just added a few checks, we can customize the behaviour of the API as per our needs.

Everything Together

Let’s see the whole thing together.

package com.codezuzu.algo;

import java.util.NoSuchElementException;

/**
 * codezuzu
 */
public class LinkedList<T> {

  private int size;

  // Head of the List
  private Node<T> head;

  // Tail of the list
  private Node<T> tail;

  class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T data, Node<T> next) {
      this.data = data;
      this.next = next;
    }

    public T getData() {
      return data;
    }

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

    public Node<T> getNext() {
      return next;
    }

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

  public int size() {
    return size;
  }

  public void add(T data) {
    if(data == null) {
      throw new IllegalArgumentException("Null data received");
    }

    Node<T> node = new Node<T>(data, null);

    if(head == null) {
      head = tail = node;
    } else {
      tail.next = node;
      tail = node;
    }
    size++;
  }

  public T getFirst() {
    if(head != null) {
      return head.data;
    }
    return null;
  }

  public T get(int index) {
    if(size == 0) {
      return null;
    }

    if(index >= size) {
      throw new NoSuchElementException("No such element");
    }

    Node<T> node = head;
    // lets find the node
    for(int i = 0; i < index; i++) {
      node = node.next;
    }
    return node.data;
  }

  public static void main(String[] args) {
    LinkedList<Integer> integerLinkedList = new LinkedList<Integer>();
    integerLinkedList.add(1);
    integerLinkedList.add(2);
    integerLinkedList.add(3);
    integerLinkedList.add(4);
    System.out.println(integerLinkedList.getFirst());
    System.out.println(integerLinkedList.get(0));
    System.out.println(integerLinkedList.get(1));
    System.out.println(integerLinkedList.get(2));
    System.out.println(integerLinkedList.get(3));
    System.out.println(integerLinkedList.get(4));
  }
}

This class is missing an important feature of Iterator, we shall see the implementation in a related post