Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: double LinkedList (insersion sort)

  1. #1
    Junior Member
    Join Date
    Nov 2011
    Posts
    1
    My Mood
    Angelic
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question double LinkedList (insersion sort)

    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


  2. #2

    Default Re: double LinkedList (insersion sort)

    What you need to do is implement a Doubly Linked List and ensure that you have add(), insert(), remove() working correctly.

    Insertion sort is one of the easiest algorithms to implement.

    After your doubly linked list class is complete, create a new class using Object Composition or inheritance (your choice) that either contains the list (object composition - preferred) or is the list (inheritance - easier to understand).

    Anyway the algorithm is as such:

    In a new list place the first element. Then do:

    if next element < current element:
    insert(next element, at position index(current element))
    else if current element is tail:
    add(next element)

    while there are more elements.

    You have an insertion sorted doubly linked list in ascending order (small to large). I suggest using the Comparable interface if you are sorting objects that cannot be compared with the < and > operators.
    Kenneth Walter
    Software Developer
    http://kennywalter.com

Similar Threads

  1. LinkedList outputs ONLY last element
    By hexwind in forum What's Wrong With My Code?
    Replies: 3
    Last Post: June 30th, 2011, 04:57 AM
  2. [SOLVED] Read double from console without having to read a string and converting it to double.
    By Lord Voldemort in forum File I/O & Other I/O Streams
    Replies: 3
    Last Post: June 26th, 2011, 08:08 AM
  3. LinkedList Objects
    By thedolphin13 in forum What's Wrong With My Code?
    Replies: 11
    Last Post: October 13th, 2010, 03:14 PM
  4. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 09:44 AM
  5. Implementing LinkedList as a user?
    By vluong in forum Collections and Generics
    Replies: 3
    Last Post: October 15th, 2009, 03:00 AM