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

[code lang=”java”]
class Node {
private T data;
private Node next;

public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
[/code]

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

[code lang=”java”]
public int size()
public void add(T data)
public T get(int index)
[/code]

API Implementation

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

[code lang=”java”]
public void add(T data) {
if(data == null) {
throw new IllegalArgumentException(“Null data received”);
}

Node node = new Node(data, null);

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

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

[code lang=”java”]
public T get(int index) {
if(size == 0) {
return null;
}

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

Node node = head;
// lets find the node
for(int i = 0; i < index; i++) { node = node.next; } return node.data; } [/code] 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.

[code lang=”java”]
package com.codezuzu.algo;

import java.util.NoSuchElementException;

/**
* codezuzu
*/
public class LinkedList {

private int size;

// Head of the List
private Node head;

// Tail of the list
private Node tail;

class Node {
private T data;
private Node next;

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

public T getData() {
return data;
}

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

public Node getNext() {
return next;
}

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

public int size() {
return size;
}

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

Node node = new Node(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 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 integerLinkedList = new LinkedList();
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));
}
}
[/code]

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