Data Access Using a Skip List Variant
Before the invention of the skip lists there were other similar data structures that used indexes into ordered linked lists to speed up processing. Your programming assignment is to create one of these we will call an indexed linked list (since I don't remember its proper name).
The basic idea is quite simple and described below.
1. First, create an ordered, doubly-linked list class implemented with pointers. The list access pointer will point to the first element in the list. (Optionally, you may use a singly-linked list.)
To load the initial data, generate random numbers, sort them and add them to the list one at a time simply by adding them to the beginning of the list, last to first.
2. Create another class called Access241 which contains an array, listAccess, of pointers that will point to nodes in the list. The size of the array will depend upon the max number of items expected to appear in the list. The middle (1/2 position) element in the array will point to the middle node in the list. The element in the 1/4 position points to the element 1/4 of the way through the list. The element in the 3/4 position points to the element 3/4 of the way through the list, etc. The number of elements in listAccess should be a parameter passed to a function that will create listAccess. The selected number of elements will constitute a trade-off between time and space efficiency.
You will need a function, organizeList, that will traverse the list, counting nodes and adjusting pointers in listAccess. organizeList will need to know the starting address of the list. Periodically the list will need to be reorganized as additions and/or deletions create access inefficiencies.
3. You will need to create the following methods.
- isEmpty - returns true if the list is empty and false otherwise
- findItem - returns true if item is in the list and false otherwise
- addItem - adds the item to the list
- delItem - deletes the item from the list
Your main menu should look something like the following:
0. Exit
1. Find an item (determine if it exists)
2. Add an item
3. Delete an item
4. Compute efficiency of structure
5. Reorganize structure.
6. List the items
"Compute efficiency" should use the formula given in lab using runsize. I.e., for each run of nodes accumulate
(R2 + R)/2 where R is the size of the run.
"Reorganize structure" should allow the user to specify the number of elements in the access pointer array.
Here is a link to the start to the program (actually, most of it).
Exercise:
Assume that the pointers divide the list into equal sublists. Suppose that we search for an item, x, using the following algorithm.
- Search through the pointer array until the first entry in the linked list that is greater than or equal to x is found. Let p = PA[i] point to the node containing the 1st key >=x
- if p = NULL return the null string
- If x is found then return the data in the node containing x.
- else search the linked list from P[i-1] to P[i] for x.
- if x is found then return the data in the node containing x.
- else return the null string.
If the number of pointers (elements of PA) = the square root of the number of nodes then, on average,
A) how many lookups are required to find an element that is in the linked list?
B) how many lookups are required to discover that an element is not in the list?
Describe the difference in the results obtained by using a queue as opposed to a stack for solving a puzzle such as a maze.
Top of this page 
Home page 
