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