This tutorial will introduce you to characteristics of Doubly LinkedList and explain how to implement it in Java

Abstract

LinkedList is an important yet simple data structure. Its benefit over array is that it supports deletion and insertion of elements without re-allocation or re-shuffling of the elements of entire data structure. Unlike Array, LinkedList does not store the elements in continuous memory locations and each element has reference to next (and previous, in some cases) node in the list.

There are following two types of LinkedList based on how many references a node has -

1. Singly LinkedList - In this LinkedList, each node has the reference to next node in List. Deleting the last node requires O(n) time and backward traversal is very hard.
2. Doubly LinkedList - Each node of this LinkedList has references to next as well as previous nodes. Backward iteration of elements is quite easy and deletion of last node can be done in just O(1) time.

In this tutorial, we will be focusing on Doubly LinkedList and see how we can implement it in Java.

Characteristics of Doubly LinkedList

Here are the characteristics of Doubly LinkedList data structure -

1. Stores the values in Nodes
2. Can contain any number of Nodes with the ability to extand without any memory overhead like ArrayLists
3. Each Node has the reference to the next as well as previous Node resulting into a list of linked nodes
4. Inserts/Removes a node in O(1) time
5. Maintains the insertion order
6. Supports easy navigation of nodes in both forward and backward directions
7. Does not provide index based search and one needs to search the nodes sequentially in order to find a node
8. Can be used to easily implement linear data structures such as Queue and Stack

Doubly LinkedList Implementation in Java

package com.saintech.allprogtutorials.datastructures;

/**
 * This code is distributed under Apache License 2.0.
 * 
 * @author Sain Technology Solutions
 *
 */
public class DoublyLinkedList<T> {

	private Node<T> head;
	private Node<T> tail;

	/**
	 * Inserts the value at the first position (head) of LinkedList.
	 * 
	 * @param value
	 *            to be inserted
	 */
	public void insertFirst(final T value) {
		final Node<T> node = new Node<>(value);
		node.next = head;
		if (head != null) {
			head.previous = node;
		}

		head = node;

		if (tail == null) {
			tail = node;
		}
	}

	/**
	 * Inserts the value at the last position (tail) of LinkedList.
	 * 
	 * @param value
	 */
	public void insertLast(final T value) {
		final Node<T> node = new Node<>(value);
		if (tail != null) {
			tail.next = node;
			node.previous = tail;
		}
		tail = node;

		if (head == null) {
			head = node;
		}
	}

	/**
	 * Removes the node from first position (head) of LinkedList.
	 * 
	 * @return the value of node deleted. Null if no nodes are present
	 */
	public T removeFirst() {
		T value = null;
		if (head != null) {
			value = head.value;
			if (head == tail) {
				tail = null;
			}

			head = head.next;
			head.previous = null;
		}

		return value;
	}

	/**
	 * Removes the node from last position (tail) of LinkedList.
	 * 
	 * @return the value of node deleted. Null if no nodes are present
	 */
	public T removeLast() {
		T value = null;
		if (tail != null) {
			value = tail.value;

			if (tail == head) {
				head = tail = null;
			} else {
				tail = tail.previous;
				tail.next = null;
			}
		}
		return value;
	}

	/**
	 * Removes the first occurance of node having the value same as input value.
	 * 
	 * @param value
	 *            to be removed
	 * @return deleted node's value if node is found else null;
	 */
	public T remove(final T value) {
		T deletedObj = null;
		if (head != null) {
			if (head == tail) {
				if (head.value.equals(value)) {
					deletedObj = head.value;
					head = tail = null;
				}
			} else {
				Node<T> node = head;
				do {
					if (node.value.equals(value)) {
						deletedObj = node.value;

						if (node.previous != null) {
							node.previous.next = node.next;

						}
						node.next.previous = node.previous;
						break;
					}
					node = node.next;
				} while (node != null);
			}
		}

		return deletedObj;
	}

	/**
	 * Implementation of a Node of a Doubly Linked List.
	 * 
	 * @author Sain Technology Solutions
	 *
	 * @param <T>
	 */
	private static class Node<T> {
		T value;
		Node<T> next;
		Node<T> previous;

		private Node(T value) {
			this.value = value;
		}

		@Override
		public String toString() {
			return "Node [value=" + value + "]";
		}

	}

	/**
	 * Entry point for testing LinkedList.
	 */
	public static void main(String[] args) {
		final DoublyLinkedList<Integer> doublyLinkedList = new DoublyLinkedList<>();

		// Inserts the node with value 5 at the head position
		doublyLinkedList.insertFirst(5);

		// Inserts the node with value 1 at the head position, pushing the
		// previously inserted node to second position
		doublyLinkedList.insertFirst(1);

		// Inserts the node with value 2 at the head position, pushing the
		// previously inserted node to second position
		doublyLinkedList.insertFirst(2);

		// Inserts the node with value 3 at the tail position
		doublyLinkedList.insertLast(3);

		// Inserts the node with value 4 at the tail position, pushing the
		// previously inserted node to second position from last
		doublyLinkedList.insertLast(4);

		// At this point, LinkedList will look like: 2 <=> 1 <=> 5 <=> 3 <=> 4

		// Removes the node with value 2 since it is head node. This operation
		// will also make node with value 1 as head node
		System.out.println(doublyLinkedList.removeFirst());

		// Removes the node with value 1 since it is head node. This operation
		// will also make node with value 5 as head node
		System.out.println(doublyLinkedList.removeFirst());

		// Removes the node with value 4 since it is tail node. This operation
		// will also make node with value 3 as tail node
		System.out.println(doublyLinkedList.removeLast());

		// Removes the node with value 3 since it is tail node. This operation
		// will also make node with value 5 as tail node
		System.out.println(doublyLinkedList.removeLast());

		// Removes the node with value 5
		System.out.println(doublyLinkedList.remove(5));

		// Returns null since there is no node with value 2 as it was removed
		// due to earlier removeXXX method calls
		System.out.println(doublyLinkedList.remove(2));

	}

}

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.