Problem 4

Implement a linked list which stores integers.

Provide the following operations:

• add_first,

• remove_first,

• remove_last,

• clear,

• is_empty,

• get (at index),

• set (at index), and

• iterate (over all the elements of the list).

(We substantially shortened the text of this problem to only give the crux of the problem and leave out the parts with user input/output. Please refer to the original exercise in German for exact details.)

Classes:

Node(value, next_node)	Represent a node of a linked list containing integers.
Cursor(linked_list)	Provide a cursor to iterate manually over a linked list.
LinkedList([values])	Provide a linked list.

class Node(value: int, next_node: Optional[Node])

Represent a node of a linked list containing integers.

Methods:

__init__(value, next_node)

__init__(value: int, next_node: Optional[Node]) → None

class Cursor(linked_list: LinkedList)

Provide a cursor to iterate manually over a linked list.

Methods:

__init__(linked_list)	Initialize the cursor to point to the beginning of the linked_list.
value()	Retrieve the value point to by the cursor.
set_value(value)	Set the value in the linked list at the cursor.
move()	Move the cursor to the next element.
done()	Return True if the cursor is past the end of linked list.
is_last()	Return True if the cursor points to the last element of the list.
remove()	Remove the node (and the value, respectively) at the cursor.

__init__(linked_list: LinkedList) → None

Initialize the cursor to point to the beginning of the linked_list.

value() → int

Retrieve the value point to by the cursor.

Requires

• not self.done()

set_value(value: int) → None

Set the value in the linked list at the cursor.

Requires

• not self.done()

move() → None

Move the cursor to the next element.

Requires

• not self.done()

done() → bool

Return True if the cursor is past the end of linked list.

is_last() → bool

Return True if the cursor points to the last element of the list.

remove() → int

Remove the node (and the value, respectively) at the cursor.

Requires

• not self.done()

OLD

• .values_without = list(_values_except_node(self._linked_list, self._node))

• .count = self._linked_list.count()

Ensures

• list(self._linked_list.values()) == OLD.values_without

class LinkedList(values: Optional[Iterable[int]] = None)

Provide a linked list.

Establishes

• len(list(self.values())) == self.count()

• self._last is not None ⇒ self._last.next_node is None

• len(list(self.values())) != 0 ^ self.is_empty()

• self.is_empty() ^ (self._first is not None and self._last is not None)

Methods:

__init__([values])	Initialize the list by populating it with the given values.
add_first(value)	Prepend the value to the list.
add_last(value)	Append the value to the list.
count()
remove_first()	Remove first element of the list.
remove_last()	Remove the last element of the list.
clear()	Remove all elements in the list.
is_empty()
get(index)	Retrieve the index-th element of the list.
set(index, value)	Set the index-th element to value.
values()	Iterate over all the values in the list.
cursor()	Get a cursor pointing to the beginning of the list.

__init__(values: Optional[Iterable[int]] = None) → None

Initialize the list by populating it with the given values.

add_first(value: int) → None

Prepend the value to the list.

OLD

• .values = list(self.values())

• .count = self.count()

Ensures

• self.count() == OLD.count + 1

• not self.is_empty()

• [value] + OLD.values == list(self.values())

add_last(value: int) → None

Append the value to the list.

OLD

• .values = list(self.values())

• .count = self.count()

Ensures

• self.count() == OLD.count + 1

• not self.is_empty()

• OLD.values + [value] == list(self.values())

count() → int

remove_first() → int

Remove first element of the list.

Requires

• not self.is_empty()

OLD

• .count = self.count()

• .values = list(self.values())

Ensures

• OLD.values[0] == result

• self.count() == OLD.count - 1

• OLD.values[1:] == list(self.values())

remove_last() → int

Remove the last element of the list.

Requires

• not self.is_empty()

OLD

• .values = list(self.values())

• .count = self.count()

Ensures

• OLD.values[-1] == result

• self.count() == OLD.count - 1

• OLD.values[:-1] == list(self.values())

clear() → None

Remove all elements in the list.

Requires

• not self.is_empty()

Ensures

• self.count() == 0

• self.is_empty()

is_empty() → bool

get(index: int) → int

Retrieve the index-th element of the list.

Requires

• 0 <= index < self.count()

Ensures

• list(self.values())[index] == result

set(index: int, value: int) → None

Set the index-th element to value.

Requires

• 0 <= index < self.count()

Ensures

• list(self.values())[index] == value

values() → Iterator[int]

Iterate over all the values in the list.

cursor() → Cursor

Get a cursor pointing to the beginning of the list.