Problem 2

Add an operation split to the linked list from Exercise 6, Problem 4.

The operation split takes in an argument n and removes all the items from the list which are greater-equal n.

The operation creates an additional list and inserts in it all the removed elements (in the same order as in the original list). The resulting second list is finally returned to the caller.

(The original problem statements includes an additional requirement that the caller should be able to iterate over the original list by adding extra pointers old_next to the original nodes. We deliberately remove this part of the problem as it introduces, in our opinion, complexity in the code with no or only marginal insights about the nature of the code contracts).

Functions:

same_order(lst, old_values)

Check that the values in lst follow the order of the old_values.

split(lst, n)

Remove the elements greater-equal n from the lst.
same_order(lst: List[int], old_values: List[int]) → bool[source]

Check that the values in lst follow the order of the old_values.

Requires

  • len(lst) <= len(old_values)

split(lst: LinkedList, n: int) → LinkedList[source]

Remove the elements greater-equal n from the lst.

return

The elements removed from the lst

OLD

  • .values = list(lst.values())

  • .count = lst.count()

Ensures

  • lst.count() + result.count() == OLD.count

  • all(value >= n for value in result.values())

  • all(value < n for value in lst.values())

  • same_order(list(lst.values()), OLD.values)

  • same_order(list(result.values()), OLD.values)