Doubly Linked List
February 16, 2009

Concept/Definition:

A more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each node has two links: one points to the previous node, or points to a null value or empty list if it is the first node; and one points to the next, or points to a null value or empty list if it is the final node.

[wiki]

♥ As what I have learned, you can access the link before or after a node since they are connected with each other. You have the previous and the next links which are its feature. It's complicated since you have to deal with the 4 pointers.

Illustration:

This is taken from the given example of our instructor.


Code Implementation:

/* Programmer: Marjorie T. Egot
Program name: A Doubly Linked List
Purpose: To implement a doubly linked list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structure */

//constructor
class Link
{
public int iData; //data item
public Link next; //next link in the list
public Link previous; //previous link in the list
public Link(int id)
{
iData = id;
}

//display the elements in the list
public void displayList()
{
return "{" + iData + "} ";
}
}

//another class which contains the methods
class DoublyLinkedList
{
private Link first;
private Link last;

public DoublyLinkedList()
{
first = null;
last = null;
}

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

public void insertFirst(int dd)
{
Link newLink = new Link(dd);

if (isEmpty())
{
last = newLink;
}else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}

public void insertLast(int dd)
{
Link newLink = new Link(dd);
if (isEmpty())
{
first = newLink;
}else{
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}

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

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

public boolean insertAfter(int key, int dd)
{
Link current = first;
while (current.iData != key)
{
current = current.next;
if (current == null)
{
return false;
}
}
Link newLink = new Link(dd);
if (current == last)
{
newLink.next = null;
last = newLink;
}else{
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}

public Link deleteKey(int key)
{
Link current = first;
while (current.iData != key)
{
current = current.next;
if (current == null)
return null;
}
if (current == first)
{
first = current.next;
}else{
current.previous.next = current.next;
}
if (current == last)
{
last = current.previous;
}else{
current.next.previous = current.previous;
}
return current;
}
}

// the main method
public class DoublyLinkedApp
{
public static void main(String[] args)
{
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
System.out.println(theList);

theList.insertAfter(22, 77);
theList.insertAfter(33, 88);
System.out.println(theList);
}
}

References:

• [wiki] http://en.wikipedia.org/wiki/Linked_list