Skip to content

Linked List Queue

Class SLListQueue

Bases: IQueue, Generic[Elem]

A generic unbounded queue -- an implementation of the Queue ADT using a singly, circularly linked list with a dummy header node.

Source code in pydsa/queue/sllist_queue.py 
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
class SLListQueue(IQueue, Generic[Elem]):
    """
    A generic unbounded queue -- an implementation of the Queue ADT using
    a singly, circularly linked list with a dummy header node.
    """

    @dataclass
    class _Node:
        value: Optional[Elem] = None
        next: Optional["SLListQueue._Node"] = None

    def __init__(self, elem_type: ElemTypeName) -> None:
        """Creates an empty queue.
        """
        # dummy node whose successor is tail node of underlying linked list
        # when queue is not empty, `None` otherwise.
        self._header = SLListQueue._Node()
        self._num_elems = 0
        self._elem_type = elem_type

    def __len__(self) -> int:
        """Returns the number of elements in the queue.

        Returns:
            int: Queue size.
        """
        return self._num_elems

    @property
    def element_type(self) -> ElemTypeName:
        """Name of the type of each element in the queue.
        """
        return self._elem_type

    def _tail(self) -> Optional["_Node"]:
        # Gets the underlying linked list's tail node, which corresponds to
        # the last element at the end of the queue.
        return self._header.next

    def _head(self) -> Optional["_Node"]:
        # Gets the underlying linked list's head node, which corresponds to
        # the first element at the front of the queue.
        tail_node = self._tail()
        return tail_node.next if tail_node else None

    def __iter__(self) -> Generator[Elem, None, None]:
        """Iterates over all elements from the front to the end of the queue.

        Yields:
            The next unprocessed element.
        """
        curr_node = self._head()
        if curr_node is not None:
            for _ in range(len(self)):
                yield curr_node.value
                curr_node = curr_node.next

    def front(self) -> Elem:
        """Gets the element at the front of the queue if it is not empty.

        Returns:
            Elem: The front element.

        Raises:
            RuntimeError: If the queue is empty.
        """
        if self.empty:
            raise RuntimeError('cannot peek front element from empty queue')
        front_node = self._head()
        return front_node.value if front_node else None

    def enqueue(self, elem: Elem) -> None:
        """Inserts an element at the end of the queue.

        Args:
            elem (Elem): The element to insert.
        """
        # create new tail node
        new_node = SLListQueue._Node(elem)
        if not self.empty:
            # link new tail node to head node
            new_node.next = self._head()
            # link old tail node to new tail node
            self._tail().next = new_node
        else:
            # link new tail node to itself as new head node
            new_node.next = new_node
        # link header node to new tail node
        self._header.next = new_node
        # increment counter
        self._num_elems += 1

    def dequeue(self) -> Elem:
        """Removes the front element from the queue if it is not empty.

        Returns:
            Elem: The front element removed from the queue.

        Raises:
            RuntimeError: If the queue is empty.
        """
        if self.empty:
            raise RuntimeError('cannot dequeue from an empty queue')

        # get a handle of old head node and its value
        head_node = self._head()
        value = head_node.value
        # link tail node to successor of old head node
        self._tail().next = head_node.next
        # break old front node's link to new head node
        head_node.next = None
        # decrement counter
        self._num_elems -= 1
        # Help garbage collection
        del head_node

        return value

__init__(elem_type)

Creates an empty queue.

Source code in pydsa/queue/sllist_queue.py 
28
29
30
31
32
33
34
35
def __init__(self, elem_type: ElemTypeName) -> None:
    """Creates an empty queue.
    """
    # dummy node whose successor is tail node of underlying linked list
    # when queue is not empty, `None` otherwise.
    self._header = SLListQueue._Node()
    self._num_elems = 0
    self._elem_type = elem_type

__iter__()

Iterates over all elements from the front to the end of the queue.

Yields:

Type Description
Generator[Elem, None, None]

The next unprocessed element.
Source code in pydsa/queue/sllist_queue.py 
62
63
64
65
66
67
68
69
70
71
72
def __iter__(self) -> Generator[Elem, None, None]:
    """Iterates over all elements from the front to the end of the queue.

    Yields:
        The next unprocessed element.
    """
    curr_node = self._head()
    if curr_node is not None:
        for _ in range(len(self)):
            yield curr_node.value
            curr_node = curr_node.next

__len__()

Returns the number of elements in the queue.

Returns:

Name Type Description
int int

Queue size.
Source code in pydsa/queue/sllist_queue.py 
37
38
39
40
41
42
43
def __len__(self) -> int:
    """Returns the number of elements in the queue.

    Returns:
        int: Queue size.
    """
    return self._num_elems

dequeue()

Removes the front element from the queue if it is not empty.

Returns:

Name Type Description
Elem Elem

The front element removed from the queue.

Raises:

Type Description
RuntimeError

If the queue is empty.
Source code in pydsa/queue/sllist_queue.py 
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
def dequeue(self) -> Elem:
    """Removes the front element from the queue if it is not empty.

    Returns:
        Elem: The front element removed from the queue.

    Raises:
        RuntimeError: If the queue is empty.
    """
    if self.empty:
        raise RuntimeError('cannot dequeue from an empty queue')

    # get a handle of old head node and its value
    head_node = self._head()
    value = head_node.value
    # link tail node to successor of old head node
    self._tail().next = head_node.next
    # break old front node's link to new head node
    head_node.next = None
    # decrement counter
    self._num_elems -= 1
    # Help garbage collection
    del head_node

    return value

element_type() property

Name of the type of each element in the queue.

Source code in pydsa/queue/sllist_queue.py 
45
46
47
48
49
@property
def element_type(self) -> ElemTypeName:
    """Name of the type of each element in the queue.
    """
    return self._elem_type

enqueue(elem)

Inserts an element at the end of the queue.

Parameters:

Name Type Description Default
elem Elem

The element to insert.

 required
Source code in pydsa/queue/sllist_queue.py 
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
def enqueue(self, elem: Elem) -> None:
    """Inserts an element at the end of the queue.

    Args:
        elem (Elem): The element to insert.
    """
    # create new tail node
    new_node = SLListQueue._Node(elem)
    if not self.empty:
        # link new tail node to head node
        new_node.next = self._head()
        # link old tail node to new tail node
        self._tail().next = new_node
    else:
        # link new tail node to itself as new head node
        new_node.next = new_node
    # link header node to new tail node
    self._header.next = new_node
    # increment counter
    self._num_elems += 1

front()

Gets the element at the front of the queue if it is not empty.

Returns:

Name Type Description
Elem Elem

The front element.

Raises:

Type Description
RuntimeError

If the queue is empty.
Source code in pydsa/queue/sllist_queue.py 
74
75
76
77
78
79
80
81
82
83
84
85
86
def front(self) -> Elem:
    """Gets the element at the front of the queue if it is not empty.

    Returns:
        Elem: The front element.

    Raises:
        RuntimeError: If the queue is empty.
    """
    if self.empty:
        raise RuntimeError('cannot peek front element from empty queue')
    front_node = self._head()
    return front_node.value if front_node else None