JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Publish Your Article Here

Doubly linked list implementation


A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

Here is the pictorial view of doubly linked list:

The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly-linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient, because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

Here is the pictorial view of inserting an element in the middle of a doubly linked list:


Image Reference: younginc.site11.com

Here is the pictorial view of deleting an element in the middle of a doubly linked list:


Image Reference: younginc.site11.com

Below shows the java implementation of doubly linked list:


package com.java2novice.ds.linkedlist;

import java.util.NoSuchElementException;

public class DoublyLinkedListImpl<E> {

	private Node head;
	private Node tail;
	private int size;
	
	public DoublyLinkedListImpl() {
		size = 0;
	}
	/**
	 * this class keeps track of each element information
	 * @author java2novice
	 *
	 */
	private	class Node {
		E element;
		Node next;
		Node prev;

		public Node(E element, Node next, Node prev) {
			this.element = element;
			this.next = next;
			this.prev = prev;
		}
	}
	/**
	 * returns the size of the linked list
	 * @return
	 */
	public int size() { return size; }
	
	/**
	 * return whether the list is empty or not
	 * @return
	 */
	public boolean isEmpty() { return size == 0; }
	
	/**
	 * adds element at the starting of the linked list
	 * @param element
	 */
	public void addFirst(E element) {
		Node tmp = new Node(element, head, null);
		if(head != null ) {head.prev = tmp;}
		head = tmp;
		if(tail == null) { tail = tmp;}
		size++;
		System.out.println("adding: "+element);
	}
	
	/**
	 * adds element at the end of the linked list
	 * @param element
	 */
	public void addLast(E element) {
		
		Node tmp = new Node(element, null, tail);
		if(tail != null) {tail.next = tmp;}
		tail = tmp;
		if(head == null) { head = tmp;}
		size++;
		System.out.println("adding: "+element);
	}
	
	/**
	 * this method walks forward through the linked list
	 */
	public void iterateForward(){
		
		System.out.println("iterating forward..");
		Node tmp = head;
		while(tmp != null){
			System.out.println(tmp.element);
			tmp = tmp.next;
		}
	}
	
	/**
	 * this method walks backward through the linked list
	 */
	public void iterateBackward(){
		
		System.out.println("iterating backword..");
		Node tmp = tail;
		while(tmp != null){
			System.out.println(tmp.element);
			tmp = tmp.prev;
		}
	}
	
	/**
	 * this method removes element from the start of the linked list
	 * @return
	 */
	public E removeFirst() {
		if (size == 0) throw new NoSuchElementException();
		Node tmp = head;
		head = head.next;
		head.prev = null;
		size--;
		System.out.println("deleted: "+tmp.element);
		return tmp.element;
	}
	
	/**
	 * this method removes element from the end of the linked list
	 * @return
	 */
	public E removeLast() {
		if (size == 0) throw new NoSuchElementException();
		Node tmp = tail;
		tail = tail.prev;
		tail.next = null;
		size--;
		System.out.println("deleted: "+tmp.element);
		return tmp.element;
	}
	
	public static void main(String a[]){
		
		DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
		dll.addFirst(10);
		dll.addFirst(34);
		dll.addLast(56);
		dll.addLast(364);
		dll.iterateForward();
		dll.removeFirst();
		dll.removeLast();
		dll.iterateBackward();
	}
}

Output:
adding: 10
adding: 34
adding: 56
adding: 364
iterating forward..
34
10
56
364
deleted: 34
deleted: 364
iterating backword..
56
10
<< Previous Program 

List of Linked List Data Structure Examples

  1. Singly linked list implementation in java
  2. Doubly linked list in Java
Knowledge Centre
When to use LinkedList or ArrayList?
Accessing elements are faster with ArrayList, because it is index based. But accessing is difficult with LinkedList. It is slow access. This is to access any element, you need to navigate through the elements one by one. But insertion and deletion is much faster with LinkedList, because if you know the node, just change the pointers before or after nodes. Insertion and deletion is slow with ArrayList, this is because, during these operations ArrayList need to adjust the indexes according to deletion or insetion if you are performing on middle indexes. Means, an ArrayList having 10 elements, if you are inserting at index 5, then you need to shift the indexes above 5 to one more.
Famous Quotations
Millions long for immortality who do not know what to do with themselves on a rainy Sunday afternoon.
-- Susan Erz

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected].

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle.
Privacy Policy | Copyright © 2022 by Nataraja Gootooru. All Rights Reserved.