How to create our own linked list in Java

Each node is an object of class. Node can store an int, and a reference to next Node object. Also note that you can use a complex object, as a member instead of an int.

As shown in the example, next reference of last element is null.

while loop is used to iterate thru the elements in the linked list.
Also, more methods can be added which performs adding an element, deleting an element, etc….

Below is a Program of singly linked list in Java.

class Node
{
	private int i;
	
	Node next;

	Node(int i)
	{
		this.i = i;
	}
	public void set(int i)
	{
		this.i = i;
	}
	
	public int get()
	{
		return i;
	}
	
}

public class OwnLinkedList {
	public static void main(String args[])
	{
	//create elements, and assign next element
	Node n1 = new Node(10);
		
	Node n2 = new Node(20);
	n1.next = n2;
		
	Node n3 = new Node(30);
	n2.next = n3;
		
	Node n4 = new Node(40);
	n3.next = n4;
		
	Node n5 = new Node(50);
	n4.next = n5;
	n5.next = null;
		
	Node tmp = n1;
	while(tmp.next!=null)
	{
		System.out.println(tmp.get());
		tmp = tmp.next;
	}
		
	}
}

double linked list
double linked list

Below is program on how to implement double linked list. Advantage of doubly linked list is it can be traversed in both the directions, unlike singly linked list. As shown below, each Node1 has reference to previous element, along with reference to next element. previous reference for first element is null. next reference for last element is null.

class Node1
{
	private int i;
	
	Node1 next;
	Node1 previous;

	Node1(int i)
	{
		this.i = i;
	}
	public void set(int i)
	{
		this.i = i;
	}
	
	public int get()
	{
		return i;
	}
	
}

public class OwnDLinkedList {
	public static void main(String args[])
	{
		//create elements, and assign next and previous element
		Node1 n1 = new Node1(10);
		
		n1.previous = null;
		Node1 n2 = new Node1(20);
		n1.next = n2;
		n2.previous = n1;
		
		Node1 n3 = new Node1(30);
		n2.next = n3;
		n3.previous = n2;
		
		Node1 n4 = new Node1(40);
		n3.next = n4;
		n4.previous = n3;
		
		Node1 n5 = new Node1(50);
		n4.next = n5;
		n5.previous = n4;
		n5.next = null;
		
		Node1 tmp = n1;
		while(tmp.next!=null)
		{
			System.out.println(tmp.get());
			tmp = tmp.next;
		}
		
	}
}

What is circular linked list

Below is an implementation of Circular doubly linked list. Here Head node refers to starting node, Tail node refers to last node.

Circular Linked List
Circular Linked List

public class OwnCLinkedList {
	public static void main(String args[])
	{
		Node1 n_head, n_tail;
		//create elements, and assign next and previous element
		Node1 n1 = new Node1(10);
		
		Node1 n5 = new Node1(50);
		
		n_head = n1; //set head node
		n_tail = n5; //set tail node
		
		n1.previous = n5;
		Node1 n2 = new Node1(20);
		n1.next = n2;
		n2.previous = n1;
		
		Node1 n3 = new Node1(30);
		n2.next = n3;
		n3.previous = n2;
		
		Node1 n4 = new Node1(40);
		n3.next = n4;
		n4.previous = n3;
		
		
		n4.next = n5;
		n5.previous = n4;
		n5.next = n1;
		
		Node1 tmp = n_head;
		while(tmp!=n_tail)
		{
			System.out.println(tmp.get());
			tmp = tmp.next;
		}
		
	}
}

We can make above Data structures better useful by providing methods, to add and delete Node,etc…

Similar steps can be followed to build complex data structures such as Graph

You may also like to read:
How Vector and ArrayList differ
List and Set differences
How ArrayList and LinkedList are implemented internally

Internal implementation of ArrayList and LinkedList Collections

ArrayList underlying implementation is based on Traditional Array data structure. Read Arrays in Java , for details on Arrays.

This post focuses on internal working of ArrayList and LinkedList Collections.

java.util.ArrayList class, is internally implemented as array.

What is array data structure?

An Array is a simplest data structure, which stores same type of elements, sequentially in memory.

Static Array
Static Array

Advantage of array

Accessing an element is very fast. Since base address of array is known, the required element which need to be fetched, can be retrieved, just by doing some manipulations on base address.

Disadvantage of array

Adding an element in between or in the beginning is very slow. Reason is, other existing elements need to be moved right by one position, and new element can be added, to the free slot created. This hits performance of program, and hence it is not recommendable to use Arrays for such situations.

java.util.LinkedList class is internally implemented using linked list data structure.

What is linked list data structure

linked list is a data structure, whose elements are not stored sequentially in memory, and are scattered in the memory. As shown in below picture, each node has Element, and reference to next and previous nodes.

what is linked list
linked list data structure

Advantage of link list data structure

An element can be added any where in between, just by changing previous and next references, as shown in below picture. This operation is slow in an array, as briefed above in array section.

Size of linked list can shrink or increase, during run time, based on the requirement.

Disadvantage of link list data structure

To Access an element, all elements need to be traversed, until the specific required element is reached. Hence searching an element is slower.

Another disadvantage of linked list is, there will be wastage of small memory, since each node need to store references to previous and next nodes.

You may also like to read:
Create our own linked list
When to use List and Set
Which are non synchronized Collections?
Generic version HashSet example