Doubly linked list (Java)

From LiteratePrograms

Jump to: navigation, search

This is a simple implementation of a doubly-linked list. Although Java SDK provides LinkedList class, it is not difficult to write a doubly-linked list class from scratch.

A doubly linked list is composed of two classes - the list itself and the node in the list.

Contents

Code

I would like to point out that this code as of jdk-1.6.0 does not work. -- anon

That's true. We need to go back to the pre-Generic version. -- Derek Ross | Talk 03:16, 25 January 2009 (EST)

Node

The Node class is not defined as a public class; rather, it is defined as package friendly. It means that this class is visible only inside of this package. 

<<DoublyLinkedList.java>>=
class Node<E> {
	Node_constructor
	Node_setter
	Node_getter
	Node_data
}

Data

A node in a doubly linked list
  • value stores the data in a node. Its type is a generic type parameter E, so we can ensure that we are storing the right data type.
  • prev points to the previous node in a doubly linked list.
  • next points to the next node in a doubly linked list. 
<<Node_data>>=
private E value;
private Node<E> prev;
private Node<E> next;

Constructor

<<Node_constructor>>=
Node(E value) {
	this.value = value;
}
Node(E value, Node<E> prev, Node<E> next) {
	this.value = value;
	setPrev(prev);
	setNext(next);
}

Setter

<<Node_setter>>=
void setPrev(Node<E> prev) {
	this.prev = prev;
}
void setNext(Node<E> next) {
	this.next = next;
}

Getter

<<Node_getter>>=
Node<E> getPrev() {
	return prev;
}
Node<E> getNext() {
	return next;
}
E getValue() {
	return value;
}

List

<<DoublyLinkedList.java>>=
public class DoublyLinkedList<E> {
	List_construct
	List_get
	List_remove
	List_add
	List_utils
	List_test
	List_data
}

Data

An empty doubly linked list.
  • head: a dummy node for the head of a list
  • tail: a dummy node for the end of a list
  • length: the length of nodes in a list, initialized to 0. 
<<List_data>>=
private Node<E> head = new Node<E>(null);
private Node<E> tail = new Node<E>(null);
private int length = 0;

Initializer block

The initializer block connects the head and tail nodes. We could do this in a constructor; but it is not necessary in this case because the initialization is not dependent on any inputs. 

<<List_construct>>=
{
	head.setPrev(null);
	head.setNext(tail);
	tail.setPrev(head);
	tail.setNext(null);
}

Get a node

<<List_get>>=
public Node<E> get(int index) throws IndexOutOfBoundsException {
	if (index < 0 || index > length) {
		throw new IndexOutOfBoundsException();
	} else {
		Node<E> cursor = head;
		for (int i = 0; i < index; i++) {
			cursor = cursor.getNext();
		}
		return cursor;
	}
}

Remove a node

<<List_remove>>=
public E remove(int index) throws IndexOutOfBoundsException {
	if (index == 0) {
		throw new IndexOutOfBoundsException();
	} else {
		Node<E> result = get(index);
		result.getNext().setPrev(result.getPrev());
		result.getPrev().setNext(result.getNext());
		length--;
		return result.getValue();
	}
}

Add a node

<<List_add>>=
public void add(int index, E value) throws IndexOutOfBoundsException {
	Node<E> cursor = get(index);
	Node<E> temp = new Node<E>(value);
	temp.setPrev(cursor);
	temp.setNext(cursor.getNext());
	cursor.getNext().setPrev(temp);
	cursor.setNext(temp);
	length++;
}
public void addHead(E value) {
	Node<E> cursor = head;
	Node<E> temp = new Node<E>(value);
	temp.setPrev(cursor);
	temp.setNext(cursor.getNext());
	cursor.getNext().setPrev(temp);
	cursor.setNext(temp);
	length++;
}
public void addTail(E value) {
	Node<E> cursor = tail.getPrev();
	Node<E> temp = new Node<E>(value);
	temp.setPrev(cursor);
	temp.setNext(cursor.getNext());
	cursor.getNext().setPrev(temp);
	cursor.setNext(temp);
	length++;
}

Utilities

<<List_utils>>=
public int size() {
	return length;
}
public boolean isEmpty() {
	return length == 0;
}
public String toString() {
	StringBuffer result = new StringBuffer();
	result.append("(head) - ");
	Node<E> temp = head;
	while (temp.getNext() != tail) {
		temp = temp.getNext();
		result.append(temp.getValue() + " - ");
	}
	result.append("(tail)");
	return result.toString();
}

Test

<<List_test>>=
public static void main(String argv[]) {
	DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
	list.addHead(new Integer(1));
	list.addHead(new Integer(2));
	list.addTail(new Integer(9));
	list.addHead(new Integer(3));
	list.addTail(new Integer(11));
	list.add(2, new Integer(0));
	System.out.println(list);
	list.remove(list.size());
	System.out.println(list);
}

Execution result

Download code
Retrieved from "http://literateprograms.org/Doubly_linked_list_%28Java%29"
Views