• • Doubly Linked List: The limitation of a Singly linked list is that it can only traverse the nest links and there is no corresponding way to traverse previous links. A doubly linked list provides capability to traverse forward as well as forward through the list. I doubly linked list a node includes three data fields: info, next and previous. Each node in a doubly linked list contains a reference (or link) to both the next and previous elements. If the current node is A then A.next points to its successor in the linked list, and A.previous points to its predecessor. First node previous points to null and last node next points to null.

Java implementation of Doubly Linked List

Create a Node class first which will keep info and link to the next and previous element.

public class Node {

	int info;
	Node next;
	Node previous;
	
	public Node(int info){
		this.info = info;
	}
	
	public void displayNode(){
		System.out.print("["+info+"]->");
	}
}

Create DoublyLinkList class which will hold nodes.

public class DoublyLinkList {

	private Node first;
	private Node last;
	
	public DoublyLinkList() {
		first = last = null;
	}

	public boolean isEmpty() {
		return first == null;
	}

	public void insertFirst(int data) {
		Node node = new Node(data);
		if (isEmpty()) {
			last = node;
		} else {
			first.previous = node;
		}
		node.next = first;
		first = node;
	}

	public void insertLast(int info) {
		Node node = new Node(info);
		if (isEmpty()) {
			first = node;
		} else {
			last.next = node;
		}
		node.previous = last;
		last = node;
 	}

	public boolean delete(int info) {
		assert isEmpty() : "Empty list!";
                
		if (first.info == info) {
			return deleteFirst();
		}
		if (last.info == info) {
			return deleteLast();
		}
		Node current = first;
		while (current != null && current.info != info) {
			current = current.next;
		}
		if (current != null) {
			current.previous.next = current.next;
			current.next.previous = current.previous;
			return true;
		} else {
			System.err.println("No match found in the list for value:" + info);
			return false;
		}

	}

	public boolean deleteFirst() {
     		first = first.next;
		if (first == null) {
			last = null;
		} else {
			first.previous = null;
		}
		return true;
	}

	public boolean deleteLast() {
 		last = last.previous;
		if (last == null) {
			first = null;
		} else {
			last.next = null;
		}
		return true;
	}

	public void displayForward() {
		Node current = first;
		while (current != null) {
			current.displayNode();
			current = current.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		DoublyLinkList list1 = new DoublyLinkList();
		list1.insertFirst(5);
		list1.insertFirst(10);
		list1.insertFirst(15);
		list1.insertFirst(20);
		System.out.println("First List-");
		list1.displayForward();
		list1.delete(15);
		System.out.println("After deleting 15-");
		list1.displayForward();

		DoublyLinkList list2 = new DoublyLinkList();
		list2.insertLast(5);
		list2.insertLast(10);
		list2.insertLast(15);
		list2.insertLast(20);
		System.out.println("Second List-");
		list2.displayForward();
		list2.delete(5);
		System.out.println("After deleting first element 5-");
		list2.displayForward();
	}
}
Output
--------
First List-
[20]->[15]->[10]->[5]->
After deleting 15-
[20]->[10]->[5]->
Second List-
[5]->[10]->[15]->[20]->
After deleting first element 5-
[10]->[15]->[20]->

All the methods are similar to singly link list only difference is that you have to change two links next and previous. Please refer previous page for details.

Go to the next page – Click on the below red circle with page number.