Skip to content

cs_survival_kit.data_structures.abstract_list

The list abstract data type that the guide's list structures implement.

A list is an ordered collection in which every element has a position. That description says what a list does, not how it is stored, and the difference is the point: DynamicArray keeps its elements in one contiguous block, while a linked list chains nodes together. Both are lists; they differ in what each operation costs.

AbstractList writes the shared contract down as a base class. Code written against it, such as a benchmark, works with any implementation.

AbstractList

Bases: ABC

An ordered collection of elements, each at a position from 0 upward.

This class defines the operations every list implementation provides. It stores nothing and implements nothing itself: a subclass supplies the storage and all six operations, and may add operations of its own that suit its storage, such as an O(1) prepend on a linked list.

A subclass that leaves out any of these operations cannot be instantiated.

Complexity

The interface fixes behaviour only. What each operation costs is set by the implementation, and comparing those costs is what the implementations are for. Each one documents its own.

Operation Required behaviour
len(a) the number of elements
iteration every element, in position order
a[i] the element at position i
item in a whether any element equals item
append add an element after the current last one
repr(a) the class name and the elements, in order

Examples:

The base class cannot be instantiated; an implementation can.

>>> AbstractList()
Traceback (most recent call last):
    ...
TypeError: Can't instantiate abstract class AbstractList...

>>> from cs_survival_kit.data_structures import DynamicArray
>>> isinstance(DynamicArray[int](), AbstractList)
True
Referenced by: Subclassed by:

__len__ abstractmethod 

__len__() -> int

Return the number of elements in the list.

Returns:

Type Description
int

The number of elements, which is 0 for an empty list.
Source code in lib/cs_survival_kit/data_structures/abstract_list.py 
55
56
57
58
59
60
61
62
@abstractmethod
def __len__(self) -> int:
    """Return the number of elements in the list.

    Returns:
        The number of elements, which is 0 for an empty list.
    """
    raise NotImplementedError

__iter__ abstractmethod 

__iter__() -> Iterator[T]

Iterate over the elements in position order.

Yields:

Type Description
T

Each element, starting with the one at position 0.
Source code in lib/cs_survival_kit/data_structures/abstract_list.py 
64
65
66
67
68
69
70
71
@abstractmethod
def __iter__(self) -> Iterator[T]:
    """Iterate over the elements in position order.

    Yields:
        Each element, starting with the one at position 0.
    """
    raise NotImplementedError

__getitem__ abstractmethod 

__getitem__(index: int) -> T

Return the element at position index.

Parameters:

Name Type Description Default
index int

The position of the element. Every implementation accepts 0 <= index < len(self); whether it accepts anything else, such as a negative index, is up to the implementation.

 required

Returns:

Type Description
T

The element at index.

Raises:

Type Description
IndexError

If there is no element at index.
Source code in lib/cs_survival_kit/data_structures/abstract_list.py 
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
@abstractmethod
def __getitem__(self, index: int) -> T:
    """Return the element at position `index`.

    Args:
        index: The position of the element. Every implementation accepts
            `0 <= index < len(self)`; whether it accepts anything else,
            such as a negative index, is up to the implementation.

    Returns:
        The element at `index`.

    Raises:
        IndexError: If there is no element at `index`.
    """
    raise NotImplementedError

__contains__ abstractmethod 

__contains__(item: object) -> bool

Return whether item is in the list.

Parameters:

Name Type Description Default
item object

The value to look for.

 required

Returns:

Type Description
bool

True if some element is item or equals it, otherwise False.
Source code in lib/cs_survival_kit/data_structures/abstract_list.py 
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
@abstractmethod
def __contains__(self, item: object) -> bool:
    """Return whether `item` is in the list.

    Args:
        item: The value to look for.

    Returns:
        `True` if some element is `item` or equals it, otherwise `False`.
    """
    raise NotImplementedError

__repr__ abstractmethod 

__repr__() -> str

Return a string showing the class name and the elements in order.

Returns:

Type Description
str

A string such as DynamicArray([1, 2, 3]).
Source code in lib/cs_survival_kit/data_structures/abstract_list.py 
102
103
104
105
106
107
108
109
@abstractmethod
def __repr__(self) -> str:
    """Return a string showing the class name and the elements in order.

    Returns:
        A string such as `DynamicArray([1, 2, 3])`.
    """
    raise NotImplementedError

append abstractmethod 

append(item: T) -> None

Add item to the end of the list.

Afterwards item is the last element and len(self) is one greater.

Parameters:

Name Type Description Default
item T

The element to add.

 required
Source code in lib/cs_survival_kit/data_structures/abstract_list.py 
111
112
113
114
115
116
117
118
119
120
@abstractmethod
def append(self, item: T) -> None:
    """Add `item` to the end of the list.

    Afterwards `item` is the last element and `len(self)` is one greater.

    Args:
        item: The element to add.
    """
    raise NotImplementedError