Jump to content

  • Log In with Google      Sign In   
  • Create Account

Cody Seibert

Member Since 14 Jun 2009
Offline Last Active Jun 08 2016 09:47 PM

#5044205 Trouble understand code: how does insert and delete of SortedList work?

Posted by on 18 March 2013 - 07:29 AM

Here is a quick explanation of insertion.  Try to figure out delete by following the same process in the figure:





To sum it up, the loop increments curr and sets prev to the last node you were at.  Once we found the optimal insertion location, when x is less than curr, we insert it by rearranging the pointers on each of the list nodes.  We need the new node, lets say Y, to be placed between 5 and 184; therefore, we need to set the next of the Y to curr, and the next of prev to Y.


Note that there is one other case which we must check for: if the list is empty (either curr == null or prev == null), we assign head to this new node Y.

Another instance which might be confusing will be when Y needs to be inserted at the end of the list.  Since curr will be null, Y's next is set to null, and the prev is set to Y

Hope this helps!