Doubly Linked List

In this post, we will implement a doubly linked list in Java. This post is a little different from the theme of this blog(algorithms), but data structures are closely related to algorithms. In fact every computer program is made up of some kind of data structure and algorithm. In other words, a computer program is a combination of data structures and algorithms.

Data structures are used to store the information and algorithms are used to carry out the operations (computations) on those data structures. The efficiency of an algorithm depends on how effectively the data structures are utilized. Data structure can be simple primitive data type (such as int, float, double etc) or very complex data types (such as String, Arrays, Hash Maps, User defined objects (classes)).

Coming back to linked lists ...

Linked List is a data structure consisting of a group of nodes. These nodes are organized in a sequence starting from a first node to the last node. A node is composed of some kind of data and a reference (a pointer or a link) to the next node in the sequence. All nodes in one linked list are similar i.e. they are structurally same. First node of a linked list is called head and last node is called a tail.

There are two types of linked list representations:

1. Singly Linked List
In this type of a representation, each node includes a reference to next node in the sequence. So this linked list can be traversed only in one direction.

2. Doubly Linked List
In this type of a representation, each node includes a reference to previous node and next node in the sequence. So this kind of list can be traversed in both directions i.e. from head to tail or from tail to head. The "previous" pointer in a head node is null and "next" pointer in a tail node is null.

Linked list can be used implement a variety of data structures such as array (ordered list), stack or a queue.

Following basic operations can be performed on a linked list:
1. Add a new node to the list (either at front or at the end)
2. Remove a node (either from front or from end or from some specified position)
3. Get the size of list
4. Traverse and display the data from the list

Above operations can be implemented in various ways and there are many ways to represent it in a computer program.

Following Java program is an example of a doubly linked list implementation. This program can be used to implement a dynamic array or a stack or a queue using doubly linked list.

Remember that a stack is a "first in last out (FILO)" kind of data structure, so you will have to select specific methods out of this program in order to use it as a Stack implementation. Queue is a "first in first out (FIFO) kind of a data structure. So select methods accordinly in order to use it as a Queue implementation.

Note: This program takes advantage of Java's generics feature, hence the client program can use same implementation to create Linked List of a different data type. e.g. It can be used to create a Linked List of Integers or a Linked List of Strings etc.

package computer.science;

public class DoublyLinkedList<T> {
private Node head;
private Node tail;
private int size;

public DoublyLinkedList() {
size = 0;
head = new Node(null);
tail = new Node(null);
head.next = tail;
tail.prev = head;
}

public int getSize() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public void addFront(T data) {
Node n = new Node(data);
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
size++;
}

public void addLast(T data) {
Node n = new Node(data);
n.prev = tail.prev;
n.next = tail;
tail.prev.next = n;
tail.prev = n;
size++;
}

public T removeFirst() {
Node t = head.next;
t.next.prev = head;
head.next = t.next;
size--;
t.prev = null;
t.next = null;
return t.getData();
}

public T removeLast() {
Node t = tail.prev;
t.prev.next = tail;
tail.prev = t.prev;
size--;
t.prev = null;
t.next = null;
return t.getData();
}

// add at specified index
public void add(int pos, T data) {
// System.out.println("adding at index " + index);
if (pos <= 0) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

if (pos > size) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

Node n = new Node(data);
Node t = head;
int count = 1;
while (count < pos) {
t = t.next;
count++;
}

n.next = t.next;
n.prev = t;
t.next.prev = n;
t.next = n;
size++;
}

// remove from specified index
public T remove(int pos) {
if (pos <= 0) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

if (pos > size) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

Node t = head;
int count = 1;
while (count < pos) {
t = t.next;
count++;
}

Node toRemove = t.next;

t.next = toRemove.next;
toRemove.next.prev = t;
size--;

toRemove.prev = null;
toRemove.next = null;
return toRemove.getData();
}

public void printList() {
// System.out.println("Size of the List : " + getSize());
Node start = head.next;
while (start.next != null) {
System.out.print(start.getData() + " ");
start = start.next;
}
System.out.println(" [size=" + size + "]");
}

private class Node {
private Node next;
private Node prev;
private T data;

public Node(T data) {
this.next = null;
this.prev = null;
this.setData(data);
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public String toString() {
return data.toString();
}
}

public static void main(String[] args) {
// Integers
int[] intList = { 23, 25, 27, 28, 29, 31, 33, 35 };
DoublyLinkedList<Integer> dLL = new DoublyLinkedList<Integer>();

System.out.println("Adding to the front ...");
for (int i = 0; i < intList.length; i++) {
dLL.addFront(intList[i]);
dLL.printList();
}

System.out.println();
System.out.println("Adding to the end ...");
int[] intList2 = { 213, 215, 217, 218, 219 };
for (int i = 0; i < intList2.length; i++) {
dLL.addLast(intList2[i]);
dLL.printList();
}

System.out.println();
System.out.println("Removing from front ...");
int t = dLL.removeFirst();
dLL.printList();
t = dLL.removeFirst();
dLL.printList();
t = dLL.removeFirst();
dLL.printList();
t = dLL.removeFirst();
dLL.printList();

System.out.println();
System.out.println("Removing from end ...");
t = dLL.removeLast();
dLL.printList();
t = dLL.removeLast();
dLL.printList();
t = dLL.removeLast();
dLL.printList();
t = dLL.removeLast();
dLL.printList();

System.out.println();
System.out.println("Adding at specified position ...");
dLL.add(3, 1);
dLL.printList();
dLL.add(1, 100);
dLL.printList();
dLL.add(dLL.getSize(), 110);
dLL.printList();

System.out.println();
System.out.println("Removing from specified position ...");
dLL.remove(4);
dLL.printList();
dLL.remove(1);
dLL.printList();
dLL.remove(dLL.getSize());
dLL.printList();

System.out.println();

// Following code is to illustrate genericness of the implementation

// Strings
String[] strList = { "abc", "xyz", "pqr", "efg", "hijk" };
DoublyLinkedList<String> sLL = new DoublyLinkedList<String>();
for (int i = 0; i < strList.length; i++) {
sLL.addFront(strList[i]);
}
sLL.printList();

System.out.println();

// Doubles
Double[] dblList = { 23.23, 25.12, 27.15, 28.5, 29.0, 31.0, 33.98 };
DoublyLinkedList<Double> dblLL = new DoublyLinkedList<Double>();
for (int i = 0; i < dblList.length; i++) {
dblLL.addFront(dblList[i]);
}
dblLL.printList();
}

}