TL;DR: Implement some methods of the List interface, submit a Java file for one class. Some code copying is permitted.

Motivation

The purpose of this assignment is to implement a balanced binary tree$-$based variation of a list and to investigate its time complexity for some of the list operations.

Introduction

This assignment will involve $($partially$)$ implementing a List interface. The List interface provides four methods for positional $($indexed$)$ access to list elements, two methods to search for a specified object, and two methods to insert and remove multiple elements at an arbitrary point in the list.

While some of these operations often execute in constant time, others may execute in time proportional to the index value, depending on an implementation $($the LinkedList class, for example, is not very efficient when accessing elements in the middle of the list using an index, and ArrayList does not allow for efficient insertion or deletion unless the element is at the end of the list$).$

Treap is a data structure that allows O$($logn$)$O$($logn$)$ search complexity $($expected$)$ as well as O$($logn$)$O$($logn$)$ insertion complexity within an ordered sequence of nn elements. While normally one uses such binary search trees to implement maps, with small modifications, one can also use them to implement lists where indices range from zero to list size $($inclusive$/$exclusive$).$

Implementation

In this assignment, you will have to write a treap$-$based partial implementation of the List interface. Unlike the existing implementations $($e$.$g$.,$ java.util.LinkedList or java.util.ArrayList$),$ your implementation will allow for faster operations in the middle of the list.

You may start with an existing treap implementation $($remember to cite any code you use that is not your own$).$ You will need to modify it to allow access by indices $($those are going to be treated similarly to ranks$)$ and all the other behaviors expected from lists. Note that you cannot just use indices as keys$$i$.$e$.,$ wrapping your calls around a map implementation, as doing so would require the indices to be renumbered every time an item is added to or removed from a list $($this would take up to O$($nlogn$)$O$($nlogn$)).$ Instead, you will use subtree sizes in every node and base the insertions on those when given indices.

In fact, the items in your list will be ordered only by their list indices. In summary, your treap nodes will probably contain:

Some data $($has no effect on the tree structure$).$

Priority $($randomly generated values, used for balancing in the treap algorithm$).$

References to neighboring nodes $($as in most linked tree representations$).$

Subtree sizes $($used to compute indices in logarithmic time$).$

Part $1$

Implement the following public methods in your implementation of the List interface, called TreapList:

boolean add$($E e$)$

void add$($int index, E element$)$

E remove$($int index$)$

E get$($int index$)$

int size$()$

void clear$()$

Iterator iterator$()$

String toString$()($see Java API: AbstractCollection$)$

One public constructor should exist in your implementation: one that takes no parameters and creates an empty list when the class is instantiated. The first four methods should run in expected logarithmic time. Also, it should be possible to iterate through the list and print it in linear time with respect to the list size.

The class should use generics. The behavior of the methods in your implementation should be equivalent to that of Java Standard Library$$s classes $($e$.$g$.,$ ArrayList; please refer to the class API online$),$ except some operations are going to take logarithmic time now $($add$,$ remove, get$).$ For the methods of the interface that you do not need to implement, you may either leave them empty or throw an exception:

java

Copy code

public type someUnneededMethod$()\{$ throw new UnsupportedOperationException$()$; $\}$

Of course, you are free to implement any private or protected methods and classes as you see fit. However, the methods mentioned above $($or the ones present in the List interface or in the class$$ superclasses$)$ are the only public methods your class may contain. Furthermore, your code should not have any side effects, such as printing debug information to the console.

Part $2$

Nothing needs to be submitted for this part; however, completing this part will provide you an opportunity to investigate if your implementation is correct and to improve your understanding of balanced trees.

Create some tester class and use it with your list implementation to investigate its running time complexity as the number of items in the list increases and as you vary the indices of the elements you are trying to operate on$.$