hello there
plz come n help me in how to sort double linked list
i want function sort in my codes................
public class DLinkedListed
{
private int size;
private DLink header;
private DLink trailer;
// -------------------------------------------------------------
public DLinkedListed() // constructor
{
header = null; // no items on list yet
trailer = null;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if no links
{ return header==null; }
// -------------------------------------------------------------
public void insertFirst(long dd) // insert at front of list
{
DLink newLink = new DLink(dd); // make new link
if( isEmpty() ) // if empty list,
trailer = newLink; // newLink <-- trailer
else
header.previous = newLink; // newLink <-- old header
newLink.next = header; // newLink --> old header
header = newLink; // header --> newLink
}
public void insertLast(long dd)
{
DLink newLink = new DLink(dd);
if( isEmpty() )
header = newLink;
else
{
trailer.next = newLink;
newLink.previous = trailer;
}
trailer = newLink;
}
/*public void deleteFirst()
{int size=0;
DLink v,u;
v=header.getNext();
u=v.getNext();
header.setNext(u);
u.setPrevious(header);
v.setNext(null);
v.setPrevious(null);
size--;
}
*/
public void deleteFirst()
{int size=0;
DLink v,u;
if (!isEmpty());{
v=header;
u=v.getNext();
if (u!=null)
u.setPrevious(null);
else
trailer=null;
header=u;
size--;}
}
public void deleteLast()
{
{int size=0;
DLink v;
if (!isEmpty());{
v=trailer.getPrevious();
if (v!=null)
v.next=null;
else
header=null;
trailer=v;
size--;}
}
}
/*public void insertmiddle(DLink v,DLink z)
{int size=0;
DLink w;
w=v.getNext();
v=w.getPrevious();
z.setPrevious(v);
z.setNext(w);
size++;}
public void deletmiddle(DLink v)
{int size=0;
DLink u=v.getPrevious();
DLink w=v.getNext();
w.setPrevious(u);
u.setNext(w);
v.setNext(null);
v.setPrevious(null);
size--;}*/
public boolean insertAfter(long key, long dd)
{ // (assumes non-empty list)
DLink current = header; // start at beginning
//to know where is the current
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return false; // didn’t find it
}
DLink newLink = new DLink(dd); // make new link
if(current==trailer) // if last link,
{
newLink.next = null; // newLink --> null
trailer = newLink; // newLink <-- last
}
else // not last link,
{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion
}
public DLink deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
DLink current = header; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return null; // didn’t find it
}
if(current==header) // found it; first item?
header = current.next; // first --> old next
else // not first
// old previous --> old next
current.previous.next = current.next;
if(current==trailer) // last item?
trailer = current.previous; // old previous <-- last
else // not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}
public void displayForward()
{
System.out.print("List (header-->trailer): ");
DLink current = header; // start at beginning
while(current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}
public void displayBackward()
{
System.out.print("List (trailer-->header): ");
DLink current = trailer; // start at end
while(current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}
}
,,,,,,,,,,,,,,,,,,,,,,,
public class DLink
{
public int size;
public long dData; // data item
public DLink next; // next link in list
public DLink previous; // previous link in list
// -------------------------------------------------------------
public DLink(long d) // constructor
{ dData = d; }
public long getdData() {return dData;}
public void setdData(long dData) {this.dData = dData;}
public DLink getNext() {return next;}
public void setNext(DLink next) {this.next = next;}
public DLink getPrevious() {return previous;}
public void setPrevious(DLink previous) {this.previous = previous;}
// -------------------------------------------------------------
public void displayLink() // display this link
{ System.out.print(dData + " "); }
// -------------------------------------------------------------
public int size() { return size; }
/** Returns whether the list is empty */
}
,,,,,,,,,,,,,,,,,,,,,,,,
public class DLinkedListApp
{
public static void main(String[] args)
{ // make a new list
DLinkedListed theList = new DLinkedListed();
theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);
theList.displayForward(); // display list forward
theList.displayBackward(); // display list backward
theList.deleteFirst(); // delete first item
theList.deleteLast(); // delete last item
theList.displayForward(); // display list forward
DLinkedListed theList2 = new DLinkedListed();
theList2.insertFirst(1); // insert at front
theList2.insertFirst(2);
theList2.insertFirst(3);
theList2.insertLast(4); // insert at rear
theList2.insertLast(5);
theList2.insertLast(6);
System.out.println("////////////");
theList2.displayForward();
theList2.displayBackward();
theList2.insertAfter(1, 19); // insert 77 after 22
theList2.displayForward(); // display list forward
theList2.deleteKey(19);
theList2.displayForward();
} // end main()
} // end class DoublyLinkedApp