How To Implement a Linked List in Java

Updated: Aug 9



A Linked List is a useful data structure available through the Java collections framework. But it's important to know how the concepts behind the data structure actually work, and especially in an interview scenario you may be asked to implement one on your own from scratch.


This is the basic implementation of a custom Singly LinkedList class that we can define for ourselves:


Basic Linked List Class


public class LinkedList {
      Node head;	
      static class Node {
	    int data;
            Node next;
		
	    Node (int d) {
		data = d;
	        next = null;
 	    }
      }
}

A LinkedList consists of individual Nodes (static class Node), and each node contains its data (int data;) and a reference to the next Node (Node next;).


There are several advantages of a linked list compared to other linear data structures such as an array.


Advantages


1 - Insertion and Deletion: We do not need to shift elements in a linked list once a node is deleted, instead we only have to adjust a pointer reference.


2 - Dynamic Size: A Linked List does not need to be initialized with a specified size, and can continue to grow or shrink just by adjusting the pointer reference of the final element in the list.


Disadvantages


1 - Traversal: Unlike an array which provides direct access to its elements, a Linked List cannot refer to an element by id. Instead we must traverse the list until we find the desired element.


2 - Memory Efficiency: More memory is consumed with a Linked List compared to an array, because in addition to the data there is storage consumed by holding a reference to the next Node object.


Full Program with Linked List


In order to see our data structure in action, we'll add 2 functions to the Linked List class in addition to a main driver function to instantiate an object of our custom defined class.


Below is a self-contained Java program for the LinkedList class with these 2 functions:

1 - printList - Prints the data of each list node in order to the console.

2 - reverseList - Reverses the order of each list node by changing the pointers for each node. Returns the new Head node.


public class LinkedList {
      Node head;	
      static class Node {
	    int data;
            Node next;
		
	    Node (int d) {
		data = d;
	        next = null;
 	    }
      }
	
	// Prints every node in Linked List
	// @param node is the head of the Linked List	
	static void printList(Node node) {
		Node curr = node;			
		while (curr != null) {
			System.out.println(curr.data);
			curr = curr.next;
		}		
	}
	
	// Reverses the node order of Linked List and return new Head Node
	// @param node is the head of the Linked List
	static Node reverseList(Node node) {			
			
		Node prev = null;
		Node current = node;			
			
		while (current != null) {
			Node nextTemp = current.next;			
			current.next = prev;
			prev = current;						
			current = nextTemp;			
		}						
		return prev;			
	}
	
	// Program Driver	
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		list.head = new Node(85);
		list.head.next = new Node(15);
		list.head.next.next = new Node(4);
		list.head.next.next.next = new Node(20);
		
		System.out.println("Original List: ");
		printList(list.head);
		
		System.out.println("\nReversed List: ");		
		printList(reverseList(list.head));
	}
}


Console Output of the program above:


Original List: 
85
15
4
20

Reversed List: 
20
4
15
85