Double-ended link list

• list with first and last references

• allow for insertions in the front or in the back of the list
• Double-ended, single-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.

  Nodes have only forward pointers, so the natural traversal is forward, and nodes may be inserted or removed after any node.

• Double-ended, double-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.

  Nodes have both forward and backward pointers, so both traversals are natural, and nodes may be inserted or removed before or after any node.

//code for double-ended

class Link { //a class of methods
public int iData;
public double dData:
public Link next;

public Link(int id,double dd) {
iData = id;

dData=dd;
}
//display elements
public void displayLink(){

System.out.print("{"+iData+","dData+"}");
}
}

//another class of methods

class DoubleEndList {
private Link first;
private Link last;


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

//insertion method at first
public void insertFirst(int id,double dd) {
Link newLink = new Link(id,dd);

if (isEmpty ())
last = newLink;
newLink.next = first;

first = newLink;
}
//insertion method at last
public void insertLast(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}


//deletion of the first node
public Link deleteFirst(int id,double dd) {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

//deletion the last node
public Link deleteLast(int id, double dd){
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}

//for displaying elements
public void displayList(){
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null){
current.displayLink();
current=current.next;

}
}
System.out.println(" ");
}
}

//the main class

public class DoubleEndApp{
public static void main(String[] args) {

DoubleEndList theList = new DoubleEndList();

//application of the insertion methods on the first and the last
theList.insertFirst(44,87);
theList.insertFirst(56,09);
theList.insertLast(07,85);
theList.insertLast(788,02);

System.out.println(theList);

//for deletion
theList.deleteFirst();
theList.deleteFirst();
System.out.println(theList);
}
}
references:

my.safaribooksonline.com/
www-personal.umich.edu/~williams/archive/forth/lists/index.html