Project $4$

Improved Linked List

Part A : Implementing a FlexibleLinkedList data structure. $(60\%)$

In class, we discussed how to use a Linked List to implement a Stack data structure with a few simple operations : push, pop, and peek.

For this project, we will build a "better" linked list, with more flexibility regarding the operations it can handle. You will implement a struct called FlexibleLinkedList that consists of two SinglyLinkedLists, like the ones we discussed in class. The 'top' of both singly linked lists will be in the "center" of our FlexibleLinkedList, and both of our SingleLinkedLists will grow outward; the left list will grow towards the left, and the right list will grow towards the right.

Your FlexibleLinkedList should be generic; it should be possible to contain any type T$.$ However, for the examples below, we will assume that it contains integers.

The data structure will look like this:

$[]//$ We push $3$ to the left list. Notice how the left list is a Stack, with value $3$ now on top.

Next, we push to the right list, the value $4$

Now, we push to the right list, the value $5$

Finally, we push to the right list the value $6.$ Notice how the top of the right list is now $6.$ The entire list has the values $1,2,3,6,5,4.$ However, the cursor $\text{'}\_\text{'}$ is still in the center.

In order to explore the list contents, from beginning to end, we must first move the cursor to the leftmost item. We can do this by moving the cursor to the left multiple times, one item at a time. Let's try this once:

We want to move the cursor left

First, we pop the $3$ from the left stack. We then hold the value $3$ temporarily

We then push the $3$ to the right stack. Notice how the order of all the items is still the same, but the cursor has now move to the left one slot. Now, we can insert or remove $($i$.$e$.,$ push or pop$)$ from this new location.

If we repeat this process two more times, then we would end up in this situation:

$]//$ After moving the cursor left twice more, then we now have the left list $($stack$)$ empty, and the right stack contains all the items.

Now, if we try and push to the right, a new value of $7,$ we get this:

In this case, the list contains $7,1,2,3,6,5,4,$ and the cursor is at index $0.$

Similarly, we could push a new value $8$ to the left, and get this:

Now, the list contains the values $8,7,1,2,3,6,5,4$ in that order. The cursor is at index $1.$

Let's imagine that we need to now add an item to index $4.$ First, we can move the cursor to that location, by moving it to the right $3$ times:

Now, the cursor is at index $4,$ and we can insert at this index by either pushing to the left, or pushing to the right. The only difference between these two options would be the new location of the cursor. If we push left, then the cursor would then be located at index $5.$ If we instead push to the right, the cursor would remain at the same index.

Similarly, we could pop from either the left or the right list. In this case though, the side we use matters more, since the removed item is dependent on the side we choose.

Overall, we want to implement the following operations.

push$\_$left$($list$,$ item$)$ : Add the given item to the left stack, at the location of the cursor

push$\_$right$($list$,$ item$)$ : Add the given item to the right stack, at the location of the cursor

pop$\_$left$($list$)$ : Remove the item from the left stack, at the location of the cursor. If there is no item to the left of the cursor, return None. Otherwise, return the removed item. $($Use the Option enum type$).$

pop$\_$right$($list$)$ : Remove the item from the right stack, at the location of the cursor. If there is no item to the right of the cursor, return None. Otherwise, return the removed item. $($Use the Option enum type$).$

peek$\_$left$($list$)$ : Return the item to the left of the cursor. If there is no item to the left of the cursor, return None. $($Use the Option enum type$)$

peek$\_$right$($list$)$ : Return the item to the right of the cursor. If there is no item to the right of the cursor, return None. $($Use the Option enum type$)$

move$\_$left$($list$)$ : Move the cursor one space to the left. If the cursor is already as far left as it can go$,$ leave it where it is$.$ Return true if the cursor moved, and false otherwise.

move$\_$right$($list$)$ : Move the cursor one space to the right. If the cursor is already as far