LinkedList is a linear data structure which allows to insert and remove elements at the front and rear in constant time.

LinkedLists are typically of two types,

• Single LinkedList
  Each node has a reference to the next node.
• Doubly LinkedList
  Each node has a reference to previous and next nodes.

Doubly Linked Lists are used extensively in various computer science domains like caching, binary trees etc.

Node Structure

A Single Linkedlist typically has a node reference to the next node and a value, on the other hand the doubly linked list has two references, previous and next, pointing to different nodes.

class DNode{
    DNode prev, next;
    T val;
}

List Operations

The doubly linked list allows typical operations like adding or removing elements to the lists, search ane element in the list.

Implementation

package src.DSFullImplementations;
/*
 * Author: Venkatesh Thallam
 * 
 */
public class DoubleLinkedListImpl {

	/*
	 * Node definition with two pointers
	 */
	class DNode {
		DNode prev, next;
		int val;

		DNode(int val) {
			this.val = val;
			prev = next = null;
		}
	}

	/*
	 * Head points to the first element of the list and tail to the last
	 */
	DNode head, tail;

	DoubleLinkedListImpl() {
		this.head = this.tail = null;
	}

	public static void main(String[] args) {
		DoubleLinkedListImpl list = new DoubleLinkedListImpl();
		list.add(10, null);
		list.add(20, 10);
		list.add(30, 10);
		list.add(40, 30);
		list.print();
		System.out.println("List size is " + list.size());
		list.remove(30);
		list.print();
		list.remove(20);
		list.print();
	}

	/*
	 * Adds an element after certain element. If ele is null, it inserts at the
	 * front
	 */
	public void add(int val, Integer ele) {
		/*
		 * If target node is head
		 */
		if (head == null) {
			head = tail = new DNode(val);
		} else if (head.val == ele || ele == null) {
			DNode temp = new DNode(val);
			temp.next = head;
			head.prev = temp;
			head = temp;
		}
		/*
		 * If target node is tail
		 */
		else if (tail.val == ele) {
			DNode newnode = new DNode(val);
			tail.next = newnode;
			newnode.prev = tail;
			tail = newnode;
		} else {
			DNode newnode = new DNode(val);
			DNode temp = head;
			while (temp.next != null && temp.val != ele) {
				temp = temp.next;
			}
			newnode.next = temp.next;
			newnode.prev = temp;
			temp.next = newnode;
		}
	}

	/*
	 * Removes the specified element
	 */
	public void remove(int ele) {
		/*
		 * If target node is head
		 */
		if (head.val == ele) {
			head = head.next;
			head.prev = null;
		}
		/*
		 * If target node is tail
		 */
		else if (tail.val == ele) {
			tail = tail.prev;
			tail.next = null;
		} else {
			DNode temp = head;
			while (temp.next != null && temp.next.val != ele) {
				temp = temp.next;
			}
			if (temp != null) {
				temp.next = temp.next.next;
				temp.next.prev = temp;
			}
		}
	}

	/*
	 * Checks whether a certain element is true
	 */
	public boolean search(int ele) {
		DNode temp = head;
		while (temp != null) {
			if (temp.val == ele) {
				return true;
			}
			temp = temp.next;
		}
		return false;
	}

	/*
	 * Returns the number of elements in the linked list.
	 */
	public int size() {
		DNode temp = head;
		int count = 0;
		while (temp != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}

	/*
	 * Prints the elements in the list
	 */
	public void print() {
		DNode temp = head;
		while (temp != null) {
			System.out.print(temp.val + " ");
			temp = temp.next;
		}
		System.out.println();
	}

}

Time Complexity

The time complexity is similar to that of single linkedlists.