• Rahul Nalawade - [email protected]
• Dhwani Raval - [email protected]
• Varun Parashar - [email protected]
• Arpita Agrawal - [email protected]

• Sunday, October 14, 2018

Please read the details about the SkipList.

• Every Entry has height {which tells us how many non-null entries it's next[] has}
• It also has span[], span[i]: storing distance of the Entry in next[i] from the current Entry

• last[]: an array of Entry, last[i]: Entry at which search came down from level i

• distanceTraversed[i]: an array of integers, distanceTraversed[i]: distance traversed on level i, as search came down from last[i] to level i-1

• There are few more attributes which are described at the time of their definition, in the code itself.

• for rebuild(), we have used iterative approach rather than a recursive one (divide-and-conquer). Initially, when we started we couldn't think of it that way, and hope it doesn't affect any EXCELLENCE CREDIT.

• There are some private methods which you may use to print the skip list

  • call printList() to print the list with next[] references.
  • call printListSpan() to print the list with span[] values for each Entry

• Our span[] is of type integer, which could have maximum value as (size+1, when head pointing to tail).

  Now, limit of int is 2^31 - 1. So, size can be no greater than 2^31 - 2.

  But we had our POSSIBLE_LEVELS as 33, which could fit in 2^33 - 1 elements. Hence, our top two levels will always have pointers from head to tail. And we could've set POSSIBLE_LEVELS to 31, instead of 33.

NOTE:

• Time and Memory might change, as you run the test the program on a different system, but they could be comparable to the above values.

Existing Processor: Intel® Core™ i5-8250U CPU @ 1.60GHz × 8 Memory: 7.5 GiB

1. Extract the rsn170330.zip

2. Compile and Run:

$javac rsn170330/*.java
$java rsn170330.SkipListDriver lp2-test/lp2-t14.txt