Java, Creating an insert function for a LinkedList to add all inserted elements in ascending order

Question

I have to create a linked List class from scratch for my Java project which will insert a date Object into its proper position. My format for sorting is to simply keep the year/month/day as a single string for use in comparing two Date objects. My compareTo function seems to not be the source of the problem as a simple selectionSort test yielded the proper result. My insert is simply using only the first element to compare to all the rest which is not correct. I don't know how to fix the situation after tinkering with it for some time now.

public class Date212 {
    private int month;
    private int day;
    private int year;

    public Date212(String d){

        String temp;
        temp = d.substring(4,6);
        int theMonth = Integer.parseInt(temp);
        temp = d.substring(6,8);
        int theDay = Integer.parseInt(temp);
        temp = d.substring(0,4);
        int theYear = Integer.parseInt(temp);

        setDate212(theYear, theMonth, theDay);
    }
    public void setDate212(int y, int m, int d){
        year = y;
        month = m;
        day = d;


    }

    public int getMonth(){
        return month;
    }
    public int getDay(){
        return day;
    }
    public int getYear(){
        return year;
    }

    public int compareTo(Date212 other){
        if(this.toString().compareTo( ((Date212)other).toString()) < 0)
            return -1; //This temp is smaller
         else if(this.toString().compareTo( ((Date212)other).toString()) > 0){
            return 1; //This temp is bigger
        }
        return 0; //Must be equal
    }

    public String toString(){
        String s = Integer.toString(year) + "/" + Integer.toString(month) + "/" + Integer.toString(day);
        return s;
    }           

}

public class ListNode
{
   protected Date212 data;
   protected ListNode next;

   public ListNode(Date212 d)
   {
      data = d;
      next = null;
   }  // constructor
}  // class ShortNode

public class LinkedList {

/** First node in linked list - dummy node */
private ListNode first = new ListNode(null);

/** Last node in linked list */
private ListNode last = first;

/** Number of data items in the list. */
private int length = 0;

/**
 * Gets the number of data values currently stored in this LinkedList.
 * 
 * @return the number of elements in the list.
 */

public int getLength() {
    return length;
}

/**
 * Appends a String data element to this LinkedList.
 * 
 * @param data
 *            the data element to be appended.
 */
public void append(Date212 d) {
    ListNode n = new ListNode(d);
    last.next = n;
    last = n;
    length++;
} // method append(String)

/**
 * Prepends (adds to the beginning) a String data element to this
 * LinkedList.
 * 
 * @param data
 *            the data element to be prepended.
 */
public void insert(Date212 d) {
    ListNode n = new ListNode(d);
    if (length == 0) //If your list is empty
    {
        last = n;
        first.next = n;
        n.next = null;
        length++;
    }
    else //There is element
    {
        ListNode p = first.next; //Start with the first element
        for(int i = 0; i<length; i++){
            if(p.data.compareTo(d) < 0){ //If you are smaller than the *following* element
                n.next = p.next; //Insert the element after the actual
                p.next = n;
                return; //Return early
            }
            p = p.next;
        }
        //We are greater than any element
        this.append(d);
    }
    }


/**
 * Determines whether this ShortSequenceLinkedList is equal in value to the
 * parameter object. They are equal if the parameter is of class
 * ShortSequenceLinkedList and the two objects contain the same short
 * integer values at each index.
 * 
 * @param other
 *            the object to be compared to this ShortSequenceLinkedList
 * 
 * @return <code>true</code> if the parameter object is a
 *         ShortSequenceLinkedList containing the same numbers at each index
 *         as this ShortSequenceLinkedList, <code>false</code> otherwise.
 */
public boolean equals(Object other) {
    if (other == null || getClass() != other.getClass()
            || length != ((LinkedList) other).length)
        return false;

    ListNode nodeThis = first;
    ListNode nodeOther = ((LinkedList) other).first;
    while (nodeThis != null) {
        // Since the two linked lists are the same length,
        // they should reach null on the same iteration.

        if (nodeThis.data != nodeOther.data)
            return false;

        nodeThis = nodeThis.next;
        nodeOther = nodeOther.next;
    } // while

    return true;
} // method equals
public String printList(){
    String s = "";
    ListNode p = first.next;

    while(p != null){
            s += p.data.toString() + "\n";
            p = p.next;
        }
        return s;

}
 }// class LinkedList

Where is your insert() method?

PM 77-1
– PM 77-1

2014-11-06 15:55:59 +00:00
Commented Nov 6, 2014 at 15:55 — PM 77-1
– PM 77-1, Commented Nov 6, 2014 at 15:55
3rd method in linkedList

Arsenal2105
– Arsenal2105

2014-11-06 16:04:53 +00:00
Commented Nov 6, 2014 at 16:04 — Arsenal2105
– Arsenal2105, Commented Nov 6, 2014 at 16:04

John Bollinger · Accepted Answer · 2014-11-06 16:52:15Z

1

Your insertion code scans up to the number of nodes recorded as the list length. That's not necessarily wrong in itself, but it would be better to just use nodes' next references to determine when you've reached the end. One reason using next would be better is that your code would be less brittle: if, say, it failed to properly manage the list length when a node was inserted before the end, then the insertion code itself would still mostly work.

Here's an alternative way your code could be written:

public void insert(Date212 d) {
    ListNode n = new ListNode(d);
    ListNode p = first;

    // Find the insertion point
    while ((p.next != null) && (p.next.data.compareTo(d) < 0)) {
        p = p.next;
    }

    // Insert the node
    n.next = p.next;
    p.next = n;

    if (n.next == null) {
        last = n;
    }

    // Update the list length
    length++;
}

edited Nov 6, 2014 at 16:52

answered Nov 6, 2014 at 16:03

John Bollinger

191k11 gold badges103 silver badges207 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sertage · Accepted Answer · 2014-11-06 15:56:46Z

0

Instead of insert at the right position I think it would be easier insert the element on the list and after sort the list like Collections.sort(myList,myComparator) does.

answered Nov 6, 2014 at 15:56

Sertage

3,2731 gold badge21 silver badges27 bronze badges

Comments

Abraham Philip · Accepted Answer · 2014-11-06 16:59:16Z

0

In a singly linked list, insertion requires a reference to the node after which the element is to be inserted. So we start with p = first, and traverse the list until we find a p.next which is greater than the element to be inserted. This means we should insert our new element after p and before p.next. This is achieved using a slightly modified version of your code as seen below.

Please note that this is for a list sorted in ascending order. For one sorted in descending order, it would be if(p.next.data.compareTo(d)<0) inside the for loop.

else //There is element
    {
        ListNode p = first; //Start with the head, p will point to the element AFTER which insertion should take place
        for(int i = 0; i<length; i++){
            if(p.next.data.compareTo(d) > 0){ //If ele to insert is lesser than next ele
                n.next = p.next; //Insert the element after the actual
                p.next = n;
                length++;
                return; //Return early
            }
            p = p.next;
        }
        //We are greater than any element
        this.append(d);
    }

edited Nov 6, 2014 at 16:59

answered Nov 6, 2014 at 16:09

Abraham Philip

6689 silver badges19 bronze badges

6 Comments

John Bollinger Over a year ago

This misses the nature of the problem.

Abraham Philip Over a year ago

How so? The problem occurred for two reasons: the original code was inserting the node at the wrong position, and the wrong comparison was being used in the if statement. I believe I've addressed both in my answer. I've also chosen to modify the OP's code itself rather than writing new code so he knows where he's gone wrong and how to correct himself, important aspects of learning to write your own algorithm.

John Bollinger Over a year ago

The problem in the original code was that it looped over length nodes at most, but did not update length when it inserted nodes before the end. Hence the observed behavior of "using only the first element to compare to all the rest" (which, granted, is not very clearly worded). That's what the question was about, regardless of any other issues the original code may have had. Your answer still contains that essential bug.

John Bollinger Over a year ago

I have, however, removed my downvote because you did point out a bona fide issue.

Abraham Philip Over a year ago

I just noticed - my apologies. I've edited my answer to reflect the changes. Thankyou for pointing that out. That wasn't the only bug in the OP's code, though. The if condition used p.data instead of p.next.data, which meant that if Node 1 was lesser than Node 2, it would still get inserted after Node 2, in a list in ascending order.

|

Collectives™ on Stack Overflow

Java, Creating an insert function for a LinkedList to add all inserted elements in ascending order

3 Answers 3

Comments

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related