4. This exercise is about to implement a skip list using linked structure with Python. A sample definition for the node and heap class is given on the course website. Recall the discussion in class. Each node has an entry with two attributes, key and name, where key is an integer and name is a string, as well as four links: prev, next, up, down. In order to manage multiple lists used in the skip list, we use the data structure, list, of Python. The methods in the skip list include:

addEmptyList(): This is to pad the skip list when the number of copies of the inserted node is more than the height (number of lists used) of the current skip list when inserting nodes;

search(v) This method searches the skip list with the given node v using the key;

delete(v): This method will delete the given node v from the skip list;

insert(v): This is to insert the given node v to the skip list.

--------------------------------------------------

The Python program starts with function create SkipLists() which reads the input file, inFile.txt. In the input file, each line contains only one entry: key and string and as follows: 10 mary

25 john 35 mars 50 lowe An example of input file is also provided on the course website. The execution should be as below and corresponding list operations are posted on the website.

>>> HeapwithEntriesInserted()

(-99999,)(8,kids)(27,luis)(40,kite)(99999,)

(-99999,)(8,kids)(27,luis)(40,kite)(99999,)

(-99999,)(27,luis)(99999,) (-99999,)(99999,)

Insert (88, luke)

(-99999,)(8,kids)(27,luis)(40,kite)(88,luke)(99999,)

(-99999,)(8,kids)(27,luis)(40,kite)(99999,)

(-99999,)(27,luis)(99999,) (-99999,)(99999,)

delete (40, kite) (-99999,)(8,kids)(27,luis)(88,luke)(99999,)

(-99999,)(8,kids)(27,luis)(99999,) (-99999,)(27,luis)(99999,) (-99999,)(99999,) Insert (27, eric) Key found in the skip lists and will not inert the new node

(-99999,)(8,kids)(27,luis)(88,luke)(99999,)

(-99999,)(8,kids)(27,luis)(99999,) (-99999,)(27,luis)(99999,) (-99999,)(99999,) delete (45, lisa) Key not found in the skip lists and will not perform the deletion

(-99999,)(8,kids)(27,luis)(88,luke)(99999,)

(-99999,)(8,kids)(27,luis)(99999,) (-99999,)(27,luis)(99999,) (-99999,)(99999,) delete (27, luis) (-99999,)(8,kids)(88,luke)(99999,) (-99999,)(8,kids)(99999,) (-99999,)(99999,) delete (8, kids) (-99999,)(88,luke)(99999,) (-99999,)(99999,) delete (88, luke) (-99999,)(99999,)