Description
Dynamic List ADT
In this assignment, you will implement a dynamic list ADT in Python that allows for inserting and deleting
elements at a specified index and retrieving elements at a specified index. The list should be implemented
as both a dynamic array and a linked list.
1 Implementation Details and Tasks
❼ Implement the DynamicArrayList and LinkedList classes in the accompanying file, listadt.py, in
the accompanying src/ sub-folder.
❼ In the DynamicArrayList and LinkedList classes, implement the following methods:
– insert(index, value): inserts value at the specified index
– delete(index): deletes the element at the specified index
– get(index): returns the element at the specified index
– size(): returns the number of elements in the list
– display(): returns the string representation of the list
❼ The dynamic array should be implemented using Python arrays. Upon creation, the dynamic array
will have a size of one, and all empty items will be initialised as -1.
❼ The dynamic array should dynamically resize itself when necessary to ensure efficient use of memory
i.e., the array should double it’s size when it is full and reduce by half once it is quarter
the size of array.
❼ The cost of resizing the array should be linear in the size of the array.
❼ The linked list should be implemented as a singly linked list.
❼ The program should take as an input a file that specifies which data structure should be used to
implement the dynamic list ADT and which operations should be performed on the list.
❼ The program should read the input file, create the appropriate data structure, and perform the specified
operations. The program should then output the result of each operation.
❼ The function load which parses the input file and saves the output of the program to a given file, has
already been implented in the accompanying file, listadt.py, in the accompanying src/ sub-folder.
1CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
1.1 Input and Output
The input file will specify which data structure should be used to implement the Dynamic List ADT and
which operations should be performed on the list. The input file will have the following format:
<data s t r u c t u r e >
<o p e r a ti o n> <arg1> <arg2>
❼ ⟨data structure⟩ is either array or linkedlist, indicating which data structure should be used to
implement the Dynamic List ADT
❼ ⟨ operation⟩ is one of the following:
– insert: Insert an item into the list. The ⟨arg1⟩ is the index at which to insert the item and ⟨arg2⟩
is the item to be inserted.
– delete: Delete an item from the list. The ⟨arg1⟩ is the index of the item to be deleted.
– get: Return the item at the specified index in the list. The ⟨arg1⟩ is the index of the item to be
returned.
– size: Return the number of items in the list.
– display: Return the string representation of the list.
The output of the program will be the result of each operation, one per line.
1.2 Example
In the following examples, the input file specifies which data structure should be used to implement the
Dynamic List ADT. The program then performs the specified operations on the list and outputs the result
of each operation.
1.2.1 Linked List
l i n k e d l i s t
i n s e r t 0 10
i n s e r t 0 20
i n s e r t 1 30
g e t 0
g e t 1
g e t 2
d e l e t e 1
s i z e
d i s pl a y
Code Listing 1: Sample input file for creating a LinkedList
20
30
10
2
[ 2 0 , 1 0]
Code Listing 2: Sample output generated by the program
Page 2 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
1.2.2 Dynamic Array List
a r r a y
i n s e r t 0 10
d i s pl a y
i n s e r t 0 15
d i s pl a y
i n s e r t 1 5
d i s pl a y
s i z e
i n s e r t 2 30
d i s pl a y
d e l e t e 1
d i s pl a y
d e l e t e 1
d i s pl a y
s i z e
d e l e t e 1
d i s pl a y
Code Listing 3: Sample input file for creating a DynamicArrayList
[ 1 0 ]
[ 1 5 , 1 0]
[ 1 5 , 5 , 1 0 , ❂1]
3
[ 1 5 , 5 , 3 0 , 1 0]
[ 1 5 , 3 0 , 1 0 , ❂1]
[ 1 5 , 1 0 , ❂1, ❂1]
2
[ 1 5 , ❂1]
Code Listing 4: Sample output generated by the program
1.3 Testing
Once you have successfully implemented the DynamicArrayList and LinkedList classes, you can test your
code by reading from the accompanying data file, data/input.txt, and performing operations on the list
adt. For grading purposes, your submission will be tested automatically by GitHub using the accompanying
pytest file, test listadt.py.
Page 3 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
Part II
Skiplists
The solutions to the problems in this part are to be entered inline below. Remove all the other parts and
sections from this document. Enter your team name as the author in the document’s title.
- A Ranked Set
[10 points]
1 Design a version of a skiplist that implements the SSet interface, but also allows fast access to elements
by rank. That is, it also supports the function get(i), which returns the element whose rank is i in
O(log n) expected time. (The rank of an element x in an SSet is the number of elements in the SSet
that are less than x.) Describe how your version differs from a regular skiplist and provide pseudocode
of find(x) and get(i) for this version.
Solution:
To allow for faster access to elements by rank we can alter the regular skiplist such that it keeps track
of the size of the sublist rooted at each node. This will allow us to minimize the time complexity of
get() operation, which returns the element at a given index in the sorted set.
In this altered version we would include two additional pieces of information for each node:
❼ size: the number of elements in each sublist starting at the node
❼ rank: the rank of the node in the SSet, computed using the size
In a regular skiplist, to find the element at a given index, one would need to traverse the list from
the beginning until reaching the desired index. This would take O(n) time, where n is the number
of elements in the set. However, in this altered version of the skiplist, the size of each subtree is
stored at each node, so we can use this information to efficiently locate the element at the given
index.
To do this, we start at the sentinel node and traverse the skiplist, keeping track of the rank of
each node (the total number of elements visited so far, including the subtree sizes). When we reach
a node whose rank equals the desired index, we return its element. This takes O log(n) time on
average, where n is the number of elements in the set.
While this version of skiplist is similar to a regular skiplist in that it uses a linked list with multiple
levels of nodes to provide efficient search, insertion, and deletion operations, it differs in that it
maintains subtree sizes and uses them to efficiently support the get() operation.
The pseudocode of find(x) for this version is given below:
1
def find_pred_node (x):
2
u = sentinel
3
r = h
4
while r >= 0:
5
while u. next [r] is not None and u . next [r].x < x:
6
u = u . next [r]
# go right in
list r
7
r -= 1
# go down
into list r -1
8
return u
9
10
def find ( x):
11
u = find_pred_node ( x)
12
if u. next [0] is None :
13
return None
14
return u. next [0].x
1Adapted from Exercise 4.9 in the textbook.
Page 4 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
The pseudocode of get(i) for this version is given below:
1
def get (i ):
2
if i < 0 or i >= n:
3
raise IndexError ()
4
u = sentinel
5
r = h
6
rank = 0
7
while True :
8
while u. next [r] is not None and rank + u . next [r]. size <= i:
9
rank += u. next [r]. size
10
u = u. next [r]
11
if rank == i:
12
return u.x
13
r -= 1
In both the functions for the modified SSetSkipList, the average time complexity for both find(x)
and get(i) is O log(n).
Page 5 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
- Finger Search
[10 points]
2 A finger in a skiplist is an array that stores the sequence of nodes on a search path at which the search
path goes down. (The variable stack in the add(x) code on page 87 is a finger; the shaded nodes in
Figure 4.3 show the contents of the finger.) One can think of a finger as pointing out the path to a node
in the lowest list, L0.
A finger search implements the find(x) operation using a finger, walking up the list using the finger
until reaching a node u such that u.x < x and u.next = nil or u.next.x > x and then performing a
normal search for x starting from u. It is possible to prove that the expected number of steps required
for a finger search is O(1 + log r), where r is the number values in L0 between x and the value pointed
to by the finger.
Design, i.e. provide the necessary pseudo code for, a version of a skiplist that implements find(x)
operations using an internal finger. This subclass stores a finger, which is then used so that every
find(x) operation is implemented as a finger search. During each find(x) operation the finger is
updated so that each find(x) operation uses, as a starting point, a finger that points to the result of
the previous find(x) operation.
Solution:
To implement a skiplist that uses an internal finger for find(x) operations, we can store the finger
as an attribute of the skiplist. Whenever a find(x) operation is performed, we first use the finger
to perform a finger search and then update the finger to point to the node found by the search.
The find(x) method traverses the skip list from the highest level to the lowest level, moving the
current node pointer down to the next node in the list until it finds a node with a value greater
than or equal to the search value x. If it finds a node with a value equal to x, it returns True and
resets the finger to the head. Otherwise, it updates the finger to point to the last node before x and
returns False. This is done so we are able to use the finger for subsequent find(x) operations and
the only way we can guarantee that the finger points to a valid node is if it points to the node just
before x.
The pseudocode for this version of find(x) is given below:
1
class FingerSkipList :
2
initialize ():
3
head = fsl . Node ( None )
4
finger =
[ head ] * max_level
5
6
def find ( x):
7
i = finger [-1]
# start at the node pointed to by
the finger
8
for level in reversed ( range ( len (i. next ) )):
9
while i. next [ level ] and i. next [ level ]. val < x:
10
i = i . next [ level ]
11
if i . next [0] and i. next [0]. val == x:
12
finger =
[ head ] * max_level
# reset the finger
to the head
13
return True
14
finger =
[ None ] * len (i. next ) +
[i]
15
# update the finger
to point to the last node before x
16
return False
2Adapted from Exercise 4.10 in the textbook.
Page 6 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
Part III
Implementing a Database Index using a
Skiplist
Figure 1: An index over the Name attribute of a table. The index stores values of the Name attribute as
keys with the associated value being the address of the corresponding record in the table.
You have learned about database indexes in CS 355 Database Systems. Indexes in databases are similar
to indexes in books. In a book, an index allows you to find information quickly without reading the entire
book. In a database, an index allows the database program to find data in a table without scanning the
entire table. An index in a book is a sorted list of words with the page numbers that contain each word. An
index in a database is a sorted list of key values with the storage locations of rows in the table that contain
the key value. Each key in the index is associated with a particular pointer to a record in the data file.
Figure 1 shows an index on the Name attribute of an Instructor table stored in a data file. Note that key
values in the figure are not sorted.
The most popular data structure used for indexing in relational databases is Btree (or its variant, such
as B+tree). Btrees rose to popularity because they do fewer disk I/O operations to run a lookup compared
to other balanced trees. SingleStore is the first commercial relational database in production today to use a
skiplist, not a Btree, as its primary index data structure for in-memory data [1].
You are given a data file, data/books.csv, that contains records of books. Each record contains the
following attributes:
❼ Book Code
❼ Title
❼ Category
❼ Price
❼ Number of Pages
For some of the attributes, all the values are unique. Such attributes can be used to index the table. Others
have repeating values and are thus unsuitable to be used for indexing.
2 Implementation Details and Tasks
You are required to provide the missing implementations for the methods in the files, skiplist.py and
db.py, in the accompanying src/ sub-folder. skiplist.py contains classes to implement a skiplist. db.py
Page 7 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
contains a Table class to store records which can be indexed using a skiplist. Every individual field in the
Table is stored as strings. Further details are provided in the doc strings in the files. The methods to be
implemented are identified with a pass in their body.
2.1 Requirement
You will need to install the typing module to support certain type hints used in the code.
2.2 Tips
Below are some tips to avoid the errors that have previously caused tests to fail. Following these may save
you many frustrating hours of debugging!
❼ Store each field that is read from file as a str.
❼ Store a record as a list of field values.
❼ Store a table as a collection of records.
❼ Make sure that the Table can be re-indexed during run-time.
❼ Take care that the keys for the index are the values of the specified attribute. And that the value
associated with each key is not the corresponding record, but a means to locate the record in the table.
❼ For the select_range query, think of an approach better than submitting multiple select queries.
2.3 Testing
Once you have successfully implemented the methods, you can test your code by reading from the accompa
nying data file, data/books.csv, and performing queries on it. For grading purposes, your submission will
be tested automatically by GitHub using the accompanying pytest file, test index.py.
Page 8 of 9CS 201, Spring 2023 HW 2: Skiplists and Dynamic List ADT L5 – Group 3
References
[1] The Story Behind SingleStore’s Skiplist Indexes,
https://www.singlestore.com/blog/
what-is-skiplist-why-skiplist-index-for-memsql/, last accessed on 16 Feb 2022.
Page 9 of 9
