Задача «Связанные списки»

Реализовать модуль работы с односвязными списками.

class SList:
    pass


# Все функции трактуют None как пустой список.

def length(lst):
    """ Подсчитать длину списка. """
    ...


def prepend(lst, data):
    """ Добавить в голову. Возвращает новое начало списка. """
    ...


def get(lst, index):
    """ Возвращает данные элемента по его порядковому номеру. """
    ...


def remove(lst, index):
    """ Удаляет элемент по его порядковому номеру. Возвращает его данные и новое начало списка. """
    ...


def append(lst, data):
    """ Добавить в хвост. Возвращает новое начало списка. """
    ...


def get_last(lst):
    """ Возвращает данные последнего элемента. """
    ...


def find(lst, data):
    """ Возвращает индекс первого элемента, равного данному. Если такого элемента нет, то возвращает -1. """
    ...


def remove_first(lst, data):
    """ Удалить первый элемент из списка со значением data. Возвращает новое начало списка. """
    ...


def remove_all(lst, data):
    """ Удалить все элементы из списка со значением data. Возвращает новое начало списка. """
    ...


def copy(lst):
    """ Скопировать список. Возвращает начало копии. """
    ...


def concat(lst1, lst2):
    """ Присоединяет в хвост списка lst1 список lst2. Возвращает новое начало объединенного списка. """
    ...


def foreach(lst, func):
    """ Обход списка. Функции func на каждом шаге передаются данные очередного элемента списка. """
    ...


def find_custom(lst, predicate):
    """ Возвращает значение и индекс первого элемента, для которого данная функция-предикат возвращает истину. """
    ...

Пример использования:

import slist

x = None
x = slist.prepend(x, "bb")
x = slist.prepend(x, "aa")
slist.get(x, 0); # => aa
slist.get(x, 1); # => bb

Примечания

  • Если функциям передается None, они должны внятно его трактовать, как пустой список. Например, length(None) должна вернуть 0.
  • Каждая функция должна быть протестирована с помощью assert. Это значит, что при сдаче задания надо продемонстрировать несколько функций, которые проверяют части интерфейса. Например: тесты для функции добавления, тесты для функции поиска.