Doubly Link List

Concept

According to National Institute of Standards and Technology
*a list in which each item has a link to the previous item as well as the next. This allows an accessing items backward, forward and deleting an item in a constant time.

[ ANIST ]

*each node has 2 pointers, one to the next and the other to the previous and the end is defined by NULL. With the doubly link list , we can move the current pointer backward and forward .

Illustration

Reference:
http://richardbowles.tripod.com/cpp/linklist/doublist.htm

implementation of doubly Link List

class Link {
public int iData;
public Link next;
public Link previous;

public Link(int id) {
iData = id;
}

public String toString() {
return "{" + iData + "} ";
}
}

class DoublyLinkedList {
private Link first;
private Link last;

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

public boolean isEmpty() {
return first == null;
}
//insertion
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;
}
//deletion
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;
}

public String toString() {
String str = "List (first-->last): ";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
System.out.println("");
System.out.print("List (last-->first): ");

current = last;
while (current != null) {
str += current.toString();
current = current.previous;
}
return str;
}
}
//main method
public class MainClass {
public static void main(String[] args) {
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(lovely);
theList.insertFirst(matet);
theList.insertFirst(tina);

theList.insertLast(nemz);
theList.insertLast(nellen);
theList.insertLast(jeany);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(nemz);

System.out.println(theList);

theList.insertAfter(lovely, jerrold);
theList.insertAfter(nellen, baste);

System.out.println(theList);
}
}

reference:

http://www.java2s.com/Tutorial/Java/0140__Collections/Adoublylinkedlist.htm