DOUBLY LINKED LIST

A) Definition

• It is convenient to traverse lists backwards and the implementation does not here but the solution is simple.[1]
• It contains a pointer to the previous cell, extra link,which adds to the space requirement and doubles the cost of insertions and deletions. It simplifies deletion, because you no longer have to refer to a key by using pointer to the previous cell.[1]

B) Illustration

Java Codes:

class Link
{
public int iData;
public Link next;
public Link previous;
public Link(int id)
{
iData = id;
}


public void displayList()
{
return "{" + iData + "} ";
}
}


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(2);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(3);
theList.insertLast(55);

System.out.println(theList);

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

theList.insertAfter(2, 77);
theList.insertAfter(3, 88);
System.out.println(theList);
}
}

C) Reference

[1]Data Structures and Algorithm Analysis in C; Mark Allen Weiss; Florida International University

[wiki] http://en.wikipedia.org/wiki/Linked_list#Doubly-linked_list