Inserting an object into a sorted linked list

[taylor.mitchell.353]

I have to insert State objects into the link list, but the linklist is sorted I placed my notes in my code. Any help would be appreciated.

public void insertAddStack()
    {   
        int probe=0, index=0;
        States key=null;

        for (;
                index < addStackItems;
                index++) //loops through keys
        {
            for (;
                    probe < numStates;
                    probe++)
            {
            if (myStates[index].getStateName().equals
               (addStack.pop().getStateName())) //compares stateNames
                    break; //ends inner for loop
            }
        }//end inner for loop
            if (probe == numStates) 
                // returns can not find key when probes equal number of states
            {
                myList.insertAfter(key, addStack.pop());<---the Key here should be set to a 
                                                            State object to add the popped object after
                                                            I cannot figure out how I would get that. I'm 
                                                            not asking for code, but just to be pointed in 
                                                            the right direction here. I know I need two  
                                                            pointers it needs to do a search(binary maybe?) 
                                                            and then possibly use the comparable startswith 
                                                            method, but I know I can't use startswith "A" 
                                                            or something it has to compare and place this 
                                                            object in the right order(a few states start 
                                                            with "A")
            }//end if 
            else //returns found key with linear probe count 
            {
                System.out.println("Dupe Add Attempted"
                        + "\nFound " + addStack.pop().getStateName());
            }//end else

[Taywin]

Line 15, you pop an object from the stack and do not store it, so it is gone if the value is not equal to the index you are comparing. You should pop() the object and store it in a variable before you do anything else. Because you pop one in line 15, your line 22 will attempt to pop the second time which would result in wrong item or NullPointerException.

For readability sake, your lines 6~8 should be written similary to for(index=0; index<addStackItems; index++). I expect that the addStackItems is a number. The same goes to lines 10~12. It is not nice to write codes in cryptic way like that. The iteration index of for-loop should be declared there if you know what it is. If you want a forever loop, use while-loop instead. Though, your loop is NOT an infinite loop.

Your logic of comparison is flaw. The outter loop should be for each of the stack and should be a while-loop with condition of "the stack is not empty." The inner loop should be the index of your myStats array. When you pop an object from the stack, compare the object value (State) with each of your myStates array. If you found the state, add it to your list and exit the loop. If not, display an error.

[taylor.mitchell.353]

I don't think my code is at all the way to go. I am looking into using a binary search to get a currentindex which would be the key for insert after. I've only done a binary search for an array though so I'm trying to figure it out.

public void insertAddStack() 
    {  
        for (int curIn = 0; curIn < addStackItems; curIn++) //loops current index
        {
            States key;
            String curAddIndex = addStack.pop().getStateName();
            int index = findInsertionPoint(curAddIndex);

            if (index != -1) //if add item is found returns error
            {
                System.out.println("Dupe Add Attempted"
                        + "\nFound " + addStack.pop().getStateName());

            }//end if(index!=-1)
            else 
            //if add value is not found returns current index as a state for key
            {
            *Here is where I need it to define the key. I am just not sure how*
                myList.insertAfter(key, addStack.pop());
            }//end else
        }//end for(int curIn=0; curIn<numKeys; curIn++)
    }//end binarySearch()

    /**
     * @param left
     * @param right
     * @param curIn
     * @param key
     * @return curIn/ -1
     */
    private int findInsertionPoint(String curAddIndex) 
    {
        int right = 0;
        int left = numStates - 1;
        int curIn;

        while (right <= left) //loops through right or left side of binary tree
        {
            curIn = right + (left - right) / 2; //creates a current index
            if (myStates[curIn].getStateName().compareTo(curAddIndex) > 0) 
                //compares left side of binary tree of states to key
            {
                left = curIn - 1; //loops left side
            }//end if
            else if (myStates[curIn].getStateName().compareTo(curAddIndex) < 0) 
            //compares right side of binary tree of states to current add index
            {
                right = curIn + 1; //loops right side
            }//end else if
            else //if key not found
            {
                return curIn; //returns current index
            }//end else
        }//end while(lo <= hi)
        return -1; //returns -1
    }//end findInsertionPoint(String curAddIndex

The curAddIndex is a string of the objects stateName. It needs to use the name it stopped at as a current point to insert after, but use the entire object. The add stack items was defined in another method. It is set by the objects inserted from a text file. It's how I am supposed to do that.

[Taywin]

If you are implementing a linked list, you are not supposed to search for insertion point using binary search. It is against the purpose of a linked list. What you are supposed to do is to traversal the list (in linear fashion) to find the location and insert the object right where you find it because you cannot get to the exact index of the list without going through the head node again. If you are going to do a binary search, array structure is what you are looking for.

When you talk about a linked list, you must understand the concept of what it is and why it is a linked list. Each node in a linked list is tied with a link (for singly linked list) which, in Java, is actually another node's object reference. Even though you could store the size of the list, it is not necessary to know the lenght of the list at all. Everything works in a linear line.

A linked list will have nodes, so you would have a Node class and your LinkedList class. The LinkedList class would have a head node and that's all. When you want to insert a node in sorted order, simply traversal the list and see if the next node either has value greater than the node you want to insert or has null value. There is NO binary search involved. If your requirement is to implement a linked list, your current implementation is off.

Now, I would like to know your requirements. The thread header is about linked list, so I am not sure that you are really implementing it or something else???

[taylor.mitchell.353]

It is a linked list. I guess I used the wrong logic. I used a linear search on the one at the top, but got rid of it because I didn't think it was correct. I couldn't figure out where it got the insertion point from. My LinkedList is read from a file into an array of State Objects(Below).

myStates[numStates] = new States(name, cap, abbr, pop, reg, regnum);

name=StateName(String) cap=Capital(String) abbr=Abbreviation(String) pop=Population(int) reg=Region(String) regnum=Region Number(int)

Then is placed into a LinkedList with

public void insertLinks()
    {
        for(int index=0; //index is a local variable for state objects
                index < numStates;
                index++) 
         //for loop to continue making state objects stopping at numStates(50)
        {
            myList.insertLast(myStates[index]);
        }//end for loop
        System.out.println("Display States With Front Pointers");
        myList.displayForward();
        System.out.println("Display States With Backward Pointers");
        myList.displayBackward();
    }//end insertLinks()

Then I have to obtain two stacks from one file. One to add to the list and one to delete from the list. I have the stacks, and I can add them, but it's sorted already and I don't know how to insert into a sorted list. I then have to delete which I have down except for one NPE below

public States deleteKey(States key)   // delete item w/ given key
      {                              // (assumes non-empty list)
      States current = first;          // start at beginning
      while(!key.getStateName().equals(current.next.getStateName()))    
         {
         current = current.next;     // move to next link
         if(current == null) 
         {
             System.out.println("Delete Key '" + 
                     key.getStateName() + "' Not Found");
             return null;

         }             // didn't find it

      if(current.next == first) 

         first = current.next; // first --> old next
      else 

         current.previous.next = current.next;// old previous --> old next 
      if(current.next == last)
         last = current.previous; // old previous <-- last
      else 
         current.next.previous = current.previous; <---NullPointerException with this line for some reason 
         }
      return current; // return value
      }

I will go back to my initial thought in the very top with the linear search, but I'm not quite sure how to get the insertionpoint or I believe I have it defined as the key.

[Taywin]

OK, so your linked list is a doubly linked list (has a link forward and backward). When you do an insertion, your data is from an array which is read from a file, correct? If so, you don't need to worry about whether or not the reading collection/array is sorted. Simply iterate through your collection/array and take each item from it and insert into your linked list.

Now the question becomes how your linked list is implemented? A standard linked list class should have its own insert() method/function which will insert at the end of the list. But if you want to insert it while sorting as well, the linked list should have a method/function to do so as well. Taking your first portion of code, it could be modified to somewhat as follows.

public void insertLinks()  {
    for(int index=0; index<numStates; index++) {
      myList.insertAndSort(myStates[index]);
    } //end for loop
    System.out.println("Display States With Front Pointers");
    myList.displayForward();
    System.out.println("Display States With Backward Pointers");
    myList.displayBackward();
}//end insertLinks()

public void insertAndSort(State item) {  // sorted in ascending order
  if (first==null) {
    // the list is currently empty, it is the first node
  }
  else {
    Node prevNode = null;   // the neibor node which comes right before
    Node currNode = first;  // current traversal node
    // if the currNode is null, it is at the tail of the list
    // if the currNode value is less than item, the item should come after
    // how to traversal a linked list
    while (currNode!=null && compareValue(currNode, item)<0) {
      prevNode = currNode;
      currNode = currNode.next;
    }
    // Now the prevNode is the last item which has the value
    //   immediately less than the node to be inserted.
    // ********************************************************
    // Properly connect the link between prevNode, item, and currNode
    // Remember there are 3 cases
    //   1)prevNode is null --> replace the first node with the item
    //     and reconnect the link
    //   2)currNode is null --> insert at the tail
    //   3)both prevNode & currNode are not null --> insert the node and
    //     reconnect the link in the middle of these 2 nodes
    // I will show you the #3 because it seems that you may be confused
    // from what you wrote. Look below (for #3 only)
    Node newNode = new Node(item);
    prevNode.next = newNode;
    currNode.previous = newNode;
    newNode.previous = prevNode;
    newNode.next = currNode;

    /*
    The graphic of what happens above is as follows:

      Original link
      +----------+    +----------+
   <--| prevNode |<-->| currNode |-->
      +----------+    +----------+

      Node newNode = new Node(item);
      +---------+
      | newNode |  Create a new node from item
      +---------+

      prevNode.next = newNode;
      +----------+    +----------+
   <--| prevNode |<---| currNode |-->
      +----------+    +----------+
           |
           |
           V
      +---------+
      | newNode |
      +---------+

      currNode.previous = newNode;
      +----------+    +----------+
   <--| prevNode |    | currNode |-->
      +----------+    +----------+
           |               |
           |               .
           V              /
      +---------+        /
      | newNode |<------'
      +---------+

      newNode.previous = prevNode;
      +----------+    +----------+
   <--| prevNode |    | currNode |-->
      +----------+    +----------+
           ^               |
           |               .
           V              /
      +---------+        /
      | newNode |<------'
      +---------+

      newNode.next = currNode;
      +----------+    +----------+
   <--| prevNode |    | currNode |-->
      +----------+    +----------+
           ^               ^
           |               |
           V              /
      +---------+        /
      | newNode |<------'
      +---------+
    */
  }  // end dealing with non-empty list
}  // insertAndSort(State)

private int compareValue(Node item1, State item2) {
  // do the comparison of 2 items in whatever way you want
  // return 0 if they both are equal
  // return 1 if the item1 has greater value than item2
  // otherwise, return -1
  ...
  ...
}

[taylor.mitchell.353]

I will work on that now and let you know. I still have to sort it as an array because before adding it I have to display the original Linked List. I actually am looking to not have a link/node class. That is our Object class, but I may change that because personally I don't find that efficient, but that was what our teacher suggested, although not required.