Linked List In Java

Linked List is a linear data structure where elements are not stored in contiguous memory location. The elements of linked list contains a object and the address part.Each element in linked list is called node.

It has some advantage over array:

• Size of the list doesn't need to be mentioned at the beginning of the program, certainly dynamic memory allocation and deallocation.

• As the linked list doesn't have a size limit, we can go on adding new nodes (elements) and increasing the size of the list to any extent.

It has some disadvantage over array:

• Wastage of Memory – Pointer Requires extra memory for storage.

• The main disadvantage of linked list over array is access time to individual elements.Array is random-access,which means it takes O(1) to access any element in the array.Linked list takes O(n) for access to an element in the list in the worst case.

• In linked list ,Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.

Code:

Create a class called Node for representing each element i linked list.

class Node
{
	int data;
	Node next;

	public Node(int data)
	{
		this.data = data;
		this.next = null;
	}
}

data represent the integer value of element and next is the pointer to next element.

Create a class called LinkedList

class LinkedList
{
	Node head;

	public LinkedList()
	{
	   head = null;
	}
}

head points to the first element of the linked list.

Add addLast ,addFirst and addAtPos methods that add the elements to the linked list at last ,first and given position respectively.

public void addLast(int data)
	{
		Node current = this.head;

		if(current == null) {
			head = new Node(data);
			return;
		}

		while(current.next != null)
		{
			current = current.next;
		}

		current.next = new Node(data);
	}

	public void addFirst(int data)
	{
		Node current = this.head;

		if(current == null) {
			head = new Node(data);
			return;
		}

		head = new Node(data);
		head.next = current;
	}

	public void addAtPos(int data,int pos)
	{
		Node current = this.head;

		if(current == null&&pos == 0) {
			head = new Node(data);
			return;
		}

		int index = 0;

		while(current != null)
		{
			if(index == pos-1) {
				Node temp = current.next;
				current.next = new Node(data);
				current = current.next;
				current.next = temp;
				return;
			}
			else {
				index++;
				current = current.next;
			}
		}
		System.out.println("Index is not found !!");
	}

Add removeLast,removeFirst and removeAtPos methods to remove elements from linked list at last ,first nd given position respectively.

public void removeLast()
	{
		Node current = this.head;

		if(current == null) {
			System.out.println("There is no last element !!");
			return;
		}

		if(current.next == null) {
			head = null;
			return;
		}

		while(current.next.next != null)
		{
			current = current.next;
		}

		current.next = null;
	}

	public void removeFirst()
	{
		Node current = this.head;

		if(current == null) {
			System.out.println("There is no first element !!");
			return;
		}

		if(current.next == null) {
			head = null;
			return;
		}

		Node temp = current.next;
	    this.head = temp;
	}

	public void removeAtPos(int pos)
	{
		Node current = this.head;

		if(current == null) {
			System.out.println("There is no index found !!");
			return;
		}

		if(current.next == null&&pos == 0) {
			head = null;
			return;
		}

		int index = 0;
		while(current != null)
		{
			if(index == pos-1) {
				Node temp = current.next;
				current.next = temp.next;
				return;
			}
			else {
				index++;
				current = current.next;
			}
		}

		System.out.println("Index is not found !!");
	}

Add print method to print the elements in linked list.

public void print()
	{
		Node current = this.head;

		while(current !=null)
		{
			System.out.print(current.data+" ");
			current = current.next;
		}
		System.out.println();
	}

Add length method to find the number of elements in linked list.

public int length()
	{
		Node current = this.head;

		int length = 0;
		while(current != null)
		{
			length++;
			current = current.next;
		}
		return length;
	}

Main method:

public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		System.out.println("Linked List******************************************");
		list.addFirst(5);
		list.addLast(6);
		list.print();
		System.out.println("*******************************************************");
		list.addAtPos(10,3);
		list.print();
		System.out.println("*******************************************************");
		list.addLast(3);
		list.addLast(5);
		list.addLast(2);
		list.addLast(8);
		list.print();
		System.out.println("*******************************************************");
		//System.out.println("**********************************************************");
		list.removeLast();
		list.print();
		System.out.println("************************************************************");
		list.removeFirst();
		list.print();
		System.out.println("*******************************************************");
		list.removeAtPos(2);
		list.print();
		System.out.println("*******************************************************");
		list.removeAtPos(5);
		list.print();
		System.out.println("*******************************************************");
		list.addAtPos(10,2);
		list.print();
		System.out.println("*******************************************************");
		System.out.println("Length :"+list.length());
		System.out.println("*******************************************************");
	}

Output: