Doubly-Linked Lists

Concept/Definition:
"a doubly linked list is not an abstract data type, but only an implementation type".[TUTORIAL_DOUBLY]

Double-linked lists require more space per node and their elementary operations are more expensive but they are often easier to manipulate because they allow sequential access to the list in both directions. In particular, one can insert or delete a node in a constant number of operations given only that node's address. [WIKI].

As what I Have Learned in our class..

doubly linked lists are complicated because there is another feature which is the "previous" in such you can access to the previous link. In inserting or deleting a node, you have to keep track of the four pointers: "2 next and 2 previous" pointers.

Code Implementation:

/* Programmer: Chrisdyll P. Pellejo
Program name: A Doubly-Linked List
Purpose: To implement a doubly linked list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures
*/

//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 for the program*/

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;
}

}

/*another class which is the main that applies all of the methods*/
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:

[TUTORIAL_DOUBLY]

http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/MTP/Common/Strandh-Tutorial/double-list.html

[WIKI]

http://en.wikipedia.org/wiki/Linked_list