Doubly Linked List

♥ Definition/Concept

According to Wikipedia:

A more sophisticated kind of linked list is a doubly-linked list or two-way lined list, that every 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]

A double linked list is a linked list, in which each node contains a pointer to a next node and a pointer to a previous element in the list.[google]

♣ As I understand of doubly linked list it has a node that points in the next node and the other points in the previous node, to access with next and previous node.

♥ Illustrations


Doubly-linked-list.svg‎ (SVG file, nominally 610 × 41 pixels, file size: 23 KB)
[This is a file from the Wikimedia Commons]

♥ Implementation

// To implement a doubly linked list.

//constructor
class Link{

public int iData;
public Link next;
public Link previous;
public Link(int id) {

iData = id;
}

// display element in a list
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;
}

//insertion of first element
public void insertFirst(int dd)
{
Link newLink = new Link(dd);

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

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

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

//deletion of last element
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 to apply
public class DoublyLinkedApp
{
public static void main(String[] args)
{
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(12);
theList.insertFirst(87);
theList.insertFirst(30);
theList.insertLast(22);
theList.insertLast(25);
theList.insertLast(27);

System.out.println(theList);

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

theList.insertAfter(12, 10);
theList.insertAfter(30, 21);
System.out.println(theList);
}
}

♥ Reference

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

http://www.google.com.ph/search?hl=en&q=double+linked+list&btnG=Google+Search&meta=

[wiki] http://en.wikipedia.org/wiki/File:Doubly-linked-list.svg