`llist` — Linked list datatypes for Python¶

This module implements linked list data structures. Currently two types of lists are supported: a doubly linked dllist and a singly linked sllist.

All data types defined in this module support efficient O(1) insertion and removal of elements (except removal in sllist which is O(n)). Random access to elements using index is O(n).

`dllist` objects¶

class llist.dllist([iterable])¶

Return a new doubly linked list initialized with elements from iterable. If iterable is not specified, the new dllist is empty.

dllist objects provide the following attributes:

first¶: First dllistnode object in the list. None if list is empty. This attribute is read-only.

last¶: Last dllistnode object in the list. None if list is empty. This attribute is read-only.

size¶: Number of elements in the list. 0 if list is empty. This attribute is read-only.

dllist objects also support the following methods (all methods below have O(1) time complexity unless specifically documented otherwise):

append(x)¶

Add x to the right side of the list and return inserted dllistnode.

Argument x might be a dllistnode. In that case a new node will be created and initialized with the value extracted from x.

appendleft(x)¶

Add x to the left side of the list and return inserted dllistnode.

Argument x might be a dllistnode. In that case a new node will be created and initialized with the value extracted from x.

appendright(x)¶

Add x to the right side of the list and return inserted dllistnode (synonymous with append()).

Argument x might be a dllistnode. In that case a new node will be created and initialized with the value extracted from x.

appendnode(node)¶

Add node to the end of the list. The node must not belong to a list.

The difference between dllist.appendright() and this method is that the former will repack the value from the argument into a new node while the latter will insert the passed node into the list. This makes dllist.appendnode() useful when a subclassed node type must be added to a list.

Raises TypeError if node is not of type dllistnode.

Raises ValueError if node already belongs to a list.

clear()¶: Remove all nodes from the list.

extend(iterable)¶: Append elements from iterable to the right side of the list.

extendleft(iterable)¶: Append elements from iterable to the left side of the list. Note that elements will be appended in reversed order.

extendright(iterable)¶: Append elements from iterable to the right side of the list (synonymous with extend()).

insert(x[, before])¶

Add x to the right side of the list if before is not specified, or insert x to the left side of dllistnode before. Return inserted dllistnode.

Argument x might be a dllistnode. In that case a new node will be created and initialized with the value extracted from x.

Raises TypeError if before is not of type dllistnode.

Raises ValueError if before does not belong to self.

insertafter(x, ref)¶

Insert x after ref and return inserted dllistnode.

Argument x might be a dllistnode. In that case a new node will be created and initialized with the value extracted from x.

Raises TypeError if ref is not of type dllistnode.

Raises ValueError if ref does not belong to self.

This method has O(1) complexity.

insertbefore(x, ref)¶

Insert x before ref and return inserted dllistnode.

Argument x might be a dllistnode. In that case a new node will be created and initialized with the value extracted from x.

Raises TypeError if ref is not of type dllistnode.

Raises ValueError if ref does not belong to self.

This method has O(1) complexity.

insertnode(node[, before])¶

Add node to the right side of the list if before is not specified, or insert node to the left side of dllistnode before. Return inserted dllistnode.

Argument node must be a dllistnode object which does not belong to any list. The node will be inserted directly into self. This makes dllist.insertnode() useful when a subclassed node type must be added to a list.

Raises TypeError if node or before is not of type dllistnode.

Raises ValueError if node belongs to a list or before does not belong to self.

insertnodeafter(node, ref)¶

Insert node after ref and return inserted dllistnode.

Argument node must be a dllistnode object which does not belong to any list. The node will be inserted directly into self. This makes dllist.insertnodebefore() useful when a subclassed node type must be added to a list.

Raises TypeError if ref is not of type dllistnode.

Raises ValueError if node belongs to a list or ref does not belong to self.

This method has O(1) complexity.

insertnodebefore(node, ref)¶

Insert node before ref and return inserted dllistnode.

Argument node must be a dllistnode object which does not belong to any list. The node will be inserted directly into self. This makes dllist.insertnodebefore() useful when a subclassed node type must be added to a list.

Raises TypeError if ref is not of type dllistnode.

Raises ValueError if node belongs to a list or ref does not belong to self.

This method has O(1) complexity.

iternodes()¶: Return iterator over all nodes in the list.

itervalues()¶

Return iterator over all values in the list.

Equivalent to iter(lst).

nodeat(index)¶

Return node (of type dllistnode) at index. Negative indices are allowed (to count nodes from the right).

Raises TypeError if index is not an integer.

Raises IndexError if index is out of range.

This method has O(n) complexity, but most recently accessed node is cached, so that accessing its neighbours is O(1). Note that inserting/deleting a node in the middle of the list will invalidate this cache.

pop()¶

Remove and return an element’s value from the right side of the list.

Raises ValueError if self is empty.

popleft()¶

Remove and return an element’s value from the left side of the list.

Raises ValueError if self is empty.

popright()¶

Remove and return an element’s value from the right side of the list (synonymous with pop()).

Raises ValueError if self is empty.

remove(node)¶

Remove node from the list and return the element which was stored in it.

Raises TypeError if node is not of type dllistnode.

Raises ValueError if self is empty, or node does not belong to self.

rotate(n)¶

Rotate the list n steps to the right. If n is negative, rotate to the left. If n is 0, do nothing.

Raises TypeError if n is not an integer.

This method has O(n) time complexity (with regards to the size of the list).

In addition to these methods, dllist supports iteration, cmp(lst1, lst2), rich comparison operators, constant time len(lst), hash(lst) and subscript references lst[1234] for accessing elements by index.

Indexed access has O(n) complexity, but most recently accessed node is cached, so that accessing its neighbours is O(1). Note that inserting/deleting a node in the middle of the list will invalidate this cache.

Subscript references like v = lst[1234] return values stored in nodes. Negative indices are allowed (to count nodes from the right).

Iteration over dllist elements (using for or list comprehensions) will also directly yield values stored in nodes.

Like most containers, dllist objects can be extended using lst1 + lst2 and lst * num syntax (including in-place += and *= variants of these operators).

Example:

>>> from llist import dllist, dllistnode

>>> empty_lst = dllist()                # create an empty list
>>> print(empty_lst)
dllist()

>>> print(len(empty_lst))               # display length of the list
0
>>> print(empty_lst.size)
0

>>> print(empty_lst.first)              # display the first node (nonexistent)
None
>>> print(empty_lst.last)               # display the last node (nonexistent)
None

>>> lst = dllist([1, 2, 3])             # create and initialize a list
>>> print(lst)                          # display elements in the list
dllist([1, 2, 3])

>>> print(len(lst))                     # display length of the list
3
>>> print(lst.size)
3

>>> print(lst.nodeat(0))                # access nodes by index
dllistnode(1)
>>> print(lst.nodeat(1))
dllistnode(2)
>>> print(lst.nodeat(2))
dllistnode(3)

>>> print(lst[0])                       # access elements by index
1
>>> print(lst[1])
2
>>> print(lst[2])
3

>>> node = lst.first                    # get the first node (same as lst[0])
>>> print(node)
dllistnode(1)

>>> print(node.value)                   # get value of node
1
>>> print(node())                       # get value of node
1
>>> print(node.prev)                    # get the previous node (nonexistent)
None
>>> print(node.next)                    # get the next node
dllistnode(2)
>>> print(node.next.value)              # get value of the next node
2

>>> for value in lst:                   # iterate over values in list
...     print(value * 2)
2
4
6

>>> for value in lst.itervalues():      # iterate over values in list explicitly
...     print(value * 2)
2
4
6

>>> for node in lst.iternodes():        # iterate over nodes in list
...     print(node.value * 2)
2
4
6

>>> lst.appendright(4)                  # append value to the right side of the list
<dllistnode(4)>
>>> print(lst)
dllist([1, 2, 3, 4])
>>> new_node = dllistnode(5)
>>> lst.appendright(new_node)           # append value from a node
<dllistnode(5)>
>>> print(lst)
dllist([1, 2, 3, 4, 5])
>>> lst.appendleft(0)                   # append value to the left side of the list
<dllistnode(0)>
>>> print(lst)
dllist([0, 1, 2, 3, 4, 5])
>>> new_node = dllistnode(6)
>>> lst.appendnode(new_node)            # append node to the end of the list
<dllistnode(6)>
>>> print(lst)
dllist([0, 1, 2, 3, 4, 5, 6])
>>> print(lst.last is new_node)
True

>>> lst.extendright([7, 8, 9])          # right-extend list with elements from iterable
>>> print(lst)
dllist([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> lst.extendleft([-1, -2, -3])        # left-extend list with elements from iterable
>>> print(lst)
dllist([-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

>>> lst = dllist([0, 1, 2, 3, 4, 5])
>>> node = lst.nodeat(2)
>>> lst.insert(1.5, node)               # insert 1.5 before node
<dllistnode(1.5)>
>>> print(lst)
dllist([0, 1, 1.5, 2, 3, 4, 5])
>>> lst.insert(6)                       # append value to the right side of the list
<dllistnode(6)>
>>> print(lst)
dllist([0, 1, 1.5, 2, 3, 4, 5, 6])
>>> new_node = dllistnode(2.5)
>>> ref_node = lst.nodeat(4)
>>> lst.insertnode(new_node, ref_node)  # insert new_node before ref_node
<dllistnode(2.5)>
>>> print(lst)
dllist([0, 1, 1.5, 2, 2.5, 3, 4, 5, 6])
>>> new_node = dllistnode(6.5)
>>> lst.insertnode(new_node)            # insert new_node at the end of the list
<dllistnode(6.5)>
>>> print(lst)
dllist([0, 1, 1.5, 2, 2.5, 3, 4, 5, 6, 6.5])
>>> ref_node = lst.nodeat(7)
>>> lst.insertbefore(4.5, ref_node)
<dllistnode(4.5)>
>>> print(lst)
dllist([0, 1, 1.5, 2, 2.5, 3, 4, 4.5, 5, 6, 6.5])
>>> ref_node = lst.nodeat(9)
>>> lst.insertbefore(5.5, ref_node)
<dllistnode(5.5)>
>>> print(lst)
dllist([0, 1, 1.5, 2, 2.5, 3, 4, 4.5, 5, 5.5, 6, 6.5])
>>> new_node = dllistnode(0.5)
>>> ref_node = lst.nodeat(1)
>>> lst.insertnodebefore(new_node, ref_node)
<dllistnode(0.5)>
>>> print(lst)
dllist([0, 0.5, 1, 1.5, 2, 2.5, 3, 4, 4.5, 5, 5.5, 6, 6.5])
>>> new_node = dllistnode(3.5)
>>> ref_node = lst.nodeat(6)
>>> lst.insertnodeafter(new_node, ref_node)
<dllistnode(3.5)>
>>> print(lst)
dllist([0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6, 6.5])

>>> lst.popleft()                       # remove leftmost node from the list
0
>>> print(lst)
dllist([0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6, 6.5])
>>> lst.popright()                      # remove rightmost node from the list
6.5
>>> print(lst)
dllist([0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6])
>>> node = lst.nodeat(2)
>>> lst.remove(node)                    # remove 3rd node from the list
1.5
>>> print(lst)
dllist([0.5, 1, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6])
>>> foreign_node = dllistnode()         # create an unassigned node
>>> lst.remove(foreign_node)            # try to remove node not present in the list
Traceback (most recent call last):
  File "/usr/lib/python2.6/doctest.py", line 1253, in __run
    compileflags, 1) in test.globs
  File "<doctest default[39]>", line 1, in <module>
    lst.remove(foreign_node)
ValueError: dllistnode belongs to another list
>>> lst.clear()
>>> print(lst)
dllist()

>>> lst = dllist([1, 2, 3, 4, 5])
>>> lst.rotate(2)
>>> print(lst)
dllist([4, 5, 1, 2, 3])
>>> lst = dllist([1, 2, 3, 4, 5])
>>> lst.rotate(-2)
>>> print(lst)
dllist([3, 4, 5, 1, 2])

>>> dllist() == dllist([])              # list comparison (lexicographical order)
True
>>> dllist() != dllist([])
False
>>> dllist([1, 2, 3]) < dllist([1, 3, 3])
True
>>> dllist([1, 2]) > dllist([1, 2, 3])
False
>>> dllist([1, 2, 3]) <= dllist()
False
>>> dllist([1, 2, 3]) >= dllist([1, 2, 3])
True

>>> lst1 = dllist([1, 2, 3, 4])         # extending lists
>>> lst2 = dllist([5, 6, 7, 8])
>>> ext_lst = lst1 + lst2
>>> print(ext_lst)
dllist([1, 2, 3, 4, 5, 6, 7, 8])

>>> lst = dllist([1, 2, 3, 4])
>>> ext_lst = lst * 2
>>> print(ext_lst)
dllist([1, 2, 3, 4, 1, 2, 3, 4])

>>> lst = dllist([0])
>>> node = lst.first
>>> weak_ref = node.owner               # get reference to the list which owns the node
>>> print(weak_ref() is lst)            # call the reference to obtain the actual list
True
>>> del lst
>>> print(weak_ref())                   # None is returned if list does not exist
None

`dllistnode` objects¶

class llist.dllistnode([value])¶

Return a new doubly linked list node, initialized (optionally) with value.

dllistnode objects provide the following attributes:

next¶: Next node in the list. This attribute is read-only.

prev¶: Previous node in the list. This attribute is read-only.

value¶: Value stored in this node.

owner¶: Weak reference to the list which owns this node. This attribute is read-only. It is possible for nodes to outlive the list they belong to. If the list is no longer alive, calling the owner reference will return None.

Note that value stored in the node can also be obtained through the __call__() method (using standard node() syntax).

`dllistiterator` objects¶

class llist.dllistiterator¶

Return a new doubly linked list iterator.

dllistiterator objects are not meant to be created by user. They are returned by the dllist.__iter__() method to hold iteration state.

Note that iteration using dllistiterator interface will directly yield values stored in nodes, not dllistnode objects.

Example:

>>> from llist import dllist
>>> lst = dllist([1, 2, 3])
>>> for value in lst:
...     print(value * 2)
2
4
6

`sllist` objects¶

class llist.sllist([iterable])¶

Return a new singly linked list initialized with elements from iterable. If iterable is not specified, the new sllist is empty.

sllist objects provide the following attributes:

first¶: First sllistnode object in the list. None if list is empty. This attribute is read-only.

last¶: Last sllistnode object in the list. None if list is empty. This attribute is read-only.

size¶: Number of elements in the list. 0 if list is empty. This attribute is read-only.

sllist objects also support the following methods:

append(x)¶

Add x to the right side of the list and return inserted sllistnode.

Argument x might be a sllistnode. In that case a new node will be created and initialized with the value extracted from x.

This method has O(1) complexity.

appendleft(x)¶

Add x to the left side of the list and return inserted sllistnode.

Argument x might be a sllistnode. In that case a new node will be created and initialized with the value extracted from x.

This method has O(1) complexity.

appendright(x)¶

Add x to the right side of the list and return inserted sllistnode.

Argument x might be a sllistnode. In that case a new node will be created and initialized with the value extracted from x.

This method has O(1) complexity.

appendnode(node)¶

Add node to the end of the list. The node must not belong to a list.

The difference between sllist.appendright() and this method is that the former will repack the value from the argument into a new node while the latter will insert the passed node into the list. This makes sllist.appendnode() useful when a subclassed node type must be added to a list.

Raises TypeError if node is not of type sllistnode.

Raises ValueError if node already belongs to a list.

clear()¶: Remove all nodes from the list.

extend(iterable)¶

Append elements from iterable to the right side of the list.

This method has O(n) complexity (in the size of iterable).

extendleft(iterable)¶

Append elements from iterable to the left side of the list. Note that elements will be appended in reversed order.

This method has O(n) complexity (in the size of iterable).

extendright(iterable)¶

Append elements from iterable to the right side of the list (synonymous with extend()).

This method has O(n) complexity (in the size of iterable).

insertafter(x, ref)¶

Insert x after ref and return inserted sllistnode.

Argument x might be a sllistnode. In that case a new node will be created and initialized with the value extracted from x.

Raises TypeError if ref is not of type sllistnode.

Raises ValueError if ref does not belong to self.

This method has O(1) complexity.

insertbefore(x, ref)¶

Insert x before ref and return inserted sllistnode.

Argument x might be a sllistnode. In that case a new node will be created and initialized with the value extracted from x.

Raises TypeError if ref is not of type sllistnode.

Raises ValueError if ref does not belong to self.

This method has O(n) complexity.

insertnodeafter(node, ref)¶

Add node to the right side of ref. Return inserted sllistnode.

Argument node must be a sllistnode instance which does not belong to any list. The node will be inserted directly into self. This makes sllist.insertnodeafter() useful when a subclassed node type must be added to a list.

Raises TypeError if node or ref is not of type sllistnode.

Raises ValueError if node belongs to another list or ref does not belong to self.

insertnodebefore(node, ref)¶

Add node to the left side of ref. Return inserted sllistnode.

Argument node must be a sllistnode instance which does not belong to any list. The node will be inserted directly into self. This makes sllist.insertnodebefore() useful when a subclassed node type must be added to a list.

Raises TypeError if node or ref is not of type sllistnode.

Raises ValueError if node belongs to another list or ref does not belong to self.

iternodes()¶: Return iterator over all nodes in the list.

itervalues()¶

Return iterator over all values in the list.

Equivalent to iter(lst).

nodeat(index)¶

Return node (of type sllistnode) at index. Negative indices are allowed (to count nodes from the right).

Raises TypeError if index is not an integer.

Raises IndexError if index is out of range.

This method has O(n) complexity.

pop()¶

Remove and return an element’s value from the right side of the list.

Raises ValueError if self is empty.

This method has O(n) time complexity.

popleft()¶

Remove and return an element’s value from the left side of the list.

Raises ValueError if self is empty.

This method has O(1) time complexity.

popright()¶

Remove and return an element’s value from the right side of the list.

Raises ValueError if self is empty.

This method has O(n) time complexity.

remove(node)¶

Remove node from the list.

Raises TypeError if node is not of type sllistnode.

Raises ValueError if self is empty, or node does not belong to self.

This method has O(n) time complexity.

rotate(n)¶

Rotate the list n steps to the right. If n is negative, rotate to the left. If n is 0, do nothing.

Raises TypeError if n is not an integer.

This method has O(n) time complexity (with regards to the size of the list).

In addition to these methods, sllist supports iteration, cmp(lst1, lst2), rich comparison operators, constant time len(lst), hash(lst) and subscript references lst[1234] for accessing elements by index.

Subscript references like v = lst[1234] return values stored in nodes. Negative indices are allowed (to count nodes from the right).

Iteration over sllist elements (using for or list comprehensions) will also directly yield values stored in nodes.

Like most containers, sllist objects can be extended using lst1 + lst2 and lst * num syntax (including in-place += and *= variants of these operators).

Example:

>>> from llist import sllist, sllistnode

>>> empty_lst = sllist()                      # create an empty list
>>> print(empty_lst)
sllist()

>>> print(len(empty_lst))                     # display length of the list
0
>>> print(empty_lst.size)
0

>>> print(empty_lst.first)                    # display the first node (nonexistent)
None
>>> print(empty_lst.last)                     # display the last node (nonexistent)
None

>>> lst = sllist([1, 2, 3])                   # create and initialize a list
>>> print(lst)                                # display elements in the list
sllist([1, 2, 3])

>>> print(len(lst))                           # display length of the list
3
>>> print(lst.size)
3

>>> print(lst.nodeat(0))                      # access nodes by index
sllistnode(1)
>>> print(lst.nodeat(1))
sllistnode(2)
>>> print(lst.nodeat(2))
sllistnode(3)

>>> print(lst[0])                             # access elements by index
1
>>> print(lst[1])
2
>>> print(lst[2])
3

>>> node = lst.first                          # get the first node (same as lst[0])
>>> print(node)
sllistnode(1)

>>> print(node.value)                         # get value of node
1
>>> print(node())                             # get value of node
1
>>> print(node.next)                          # get the next node
sllistnode(2)
>>> print(node.next.value)                    # get value of the next node
2

>>> for value in lst:                         # iterate over list elements
...     print(value * 2)
2
4
6

>>> for value in lst.itervalues():            # iterate over values in list explicitly
...     print(value * 2)
2
4
6

>>> for node in lst.iternodes():              # iterate over nodes in list
...     print(node.value * 2)
2
4
6

>>> lst.appendright(4)                        # append value to the right side of the list
<sllistnode(4)>
>>> print(lst)
sllist([1, 2, 3, 4])
>>> new_node = sllistnode(5)
>>> lst.appendright(new_node)                 # append value from a node
<sllistnode(5)>
>>> print(lst)
sllist([1, 2, 3, 4, 5])
>>> lst.appendleft(0)                         # append value to the left side of the list
<sllistnode(0)>
>>> print(lst)
sllist([0, 1, 2, 3, 4, 5])
>>> new_node = sllistnode(6)
>>> lst.appendnode(new_node)                  # append node to the end of the list
<sllistnode(6)>
>>> print(lst)
sllist([0, 1, 2, 3, 4, 5, 6])
>>> print(lst.last is new_node)
True

>>> lst.extendright([7, 8, 9])                # right-extend list with elements from iterable
>>> print(lst)
sllist([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> lst.extendleft([-1, -2, -3])              # left-extend list with elements from iterable
>>> print(lst)
sllist([-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

>>> lst = sllist([0, 1, 2, 3, 4, 5])
>>> node = lst.nodeat(2)
>>> lst.insertbefore(1.5, node)               # insert 1.5 before node
<sllistnode(1.5)>
>>> print(lst)
sllist([0, 1, 1.5, 2, 3, 4, 5])
>>> lst.insertafter(2.5, node)                # insert 2.5 after node
<sllistnode(2.5)>
>>> print(lst)
sllist([0, 1, 1.5, 2, 2.5, 3, 4, 5])
>>> new_node = sllistnode(3.5)
>>> ref_node = lst.nodeat(6)
>>> lst.insertnodebefore(new_node, ref_node)  # insert new_node before ref_node
<sllistnode(3.5)>
>>> print(lst)
sllist([0, 1, 1.5, 2, 2.5, 3, 3.5, 4, 5])
>>> new_node = sllistnode(4.5)
>>> ref_node = lst.nodeat(7)
>>> lst.insertnodeafter(new_node, ref_node)   # insert new_node after ref_node
<sllistnode(4.5)>
>>> print(lst)
sllist([0, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5])

>>> lst.popleft()                             # remove leftmost node from the list
0
>>> print(lst)
sllist([1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5])
>>> lst.popright()                            # remove rightmost node from the list
5
>>> print(lst)
sllist([1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5])
>>> node = lst.nodeat(1)
>>> lst.remove(node)                          # remove 2nd node from the list
1.5
>>> print(lst)
sllist([1, 2, 2.5, 3, 3.5, 4, 4.5])
>>> foreign_node = sllistnode()               # create an unassigned node
>>> lst.remove(foreign_node)                  # try to remove node not present in the list
Traceback (most recent call last):
  File "/usr/lib/python2.6/doctest.py", line 1253, in __run
    compileflags, 1) in test.globs
  File "<doctest default[39]>", line 1, in <module>
    lst.remove(foreign_node)
ValueError: sllistnode belongs to another list
>>> lst.clear()
>>> print(lst)
sllist()

>>> lst = sllist([1, 2, 3, 4, 5])
>>> lst.rotate(2)
>>> print(lst)
sllist([4, 5, 1, 2, 3])
>>> lst = sllist([1, 2, 3, 4, 5])
>>> lst.rotate(-2)
>>> print(lst)
sllist([3, 4, 5, 1, 2])

>>> sllist() == sllist([])                    # list comparison (lexicographical order)
True
>>> sllist() != sllist([])
False
>>> sllist([1, 2, 3]) < sllist([1, 3, 3])
True
>>> sllist([1, 2]) > sllist([1, 2, 3])
False
>>> sllist([1, 2, 3]) <= sllist()
False
>>> sllist([1, 2, 3]) >= sllist([1, 2, 3])
True

>>> lst1 = sllist([1, 2, 3, 4])               # extending lists
>>> lst2 = sllist([5, 6, 7, 8])
>>> ext_lst = lst1 + lst2
>>> print(ext_lst)
sllist([1, 2, 3, 4, 5, 6, 7, 8])

>>> lst = sllist([1, 2, 3, 4])
>>> ext_lst = lst * 2
>>> print(ext_lst)
sllist([1, 2, 3, 4, 1, 2, 3, 4])

>>> lst = sllist([0])
>>> node = lst.first
>>> weak_ref = node.owner                     # get reference to the list which owns the node
>>> print(weak_ref() is lst)                  # call the reference to obtain the actual list
True
>>> del lst
>>> print(weak_ref())                         # None is returned if list does not exist
None

`sllistnode` objects¶

class llist.sllistnode([value])¶

Return a new singly linked list node, initialized (optionally) with value.

sllistnode objects provide the following attributes:

next¶: Next node in the list. This attribute is read-only.

value¶: Value stored in this node.

owner¶: Weak reference to the list which owns this node. This attribute is read-only. It is possible for nodes to outlive the list they belong to. If the list is no longer alive, calling the owner reference will return None.

Note that value stored in the node can also be obtained through the __call__() method (using standard node() syntax).

`sllistiterator` objects¶

class llist.sllistiterator¶

Return a new singly linked list iterator.

sllistiterator objects are not meant to be created by user. They are returned by the sllist.__iter__() method to hold iteration state.

Note that iteration using sllistiterator interface will directly yield values stored in nodes, not sllistnode objects.

Example:

>>> from llist import sllist
>>> lst = sllist([1, 2, 3])
>>> for value in lst:
...     print(value * 2)
2
4
6

Changes¶

llist-0.7 (2021-04-27)
- fixed repr() and str() for self-referencing lists and nodes (closes issue #10)
- fixed duplicated release of Py_None during destruction of self-referencing lists and nodes (closes issue #11)
- fixed a bug where a list item could be missed if it had been added during preceding step of list iteration (closes issue #12)
- added insertbefore(), insertafter(), insertnodebefore() and insertnodeafter() methods to dllist (closes issue #14)
- implemented iter() method on list iterators
- implemented iternodes() and itervalues() methods on dllist and sllist (closes issue #5)

llist-0.6 (2018-06-30)
- allow subclassing of list and node types
- added appendnode() method to dllist and sllist (contribution from Alex Stennet)
- added insertnode() method to dllist and insertnodeafter()/insertnodebefore() methods to sllist
- support for cyclic garbabe collection

llist-0.5 (2017-11-18)
- changed visibility of internal module functions to hidden
- hash() function now returns different results for lists containing permuted elements
- added owner attribute to nodes (contribution from Anand Aiyer)
- added clearing of neighbour and owner references in removed node

llist-0.4 (2013-01-01)
- Python 3.x support

llist-0.3 (2012-01-22)
- fixed neighbour references (prev and next) in dangling nodes
- implemented clear() method in dllist and sllist
- implemented rotate() method in dllist and sllist
- fixed reference counting of list weakrefs
- fixed segmentation fault when removing a node that does not belong to the list (issue #1)
- implemented extend(), extendleft() and extendright() methods in dllist and sllist
- changed insert_before() to insertbefore() and insert_after() to insertafter()

llist-0.2 (2011-12-30)
- subscript operator lst[x] now directly returns values stored in the list, not dllistnode objects
- implemented nodeat() method in dllist and sllist
- fixed segmentation faults in sllist.insert and sllist.delete methods
- added missing Py_DECREFs to sllist
- added concatenation and in-place concatenation operator
- added repeat operator
- added hash() support

llist-0.1 (2011-12-26)

Initial release

Copyright¶

This module is copyrighted by Adam Jakubek and Rafał Gałczyński.

It is distributed under the MIT license. Please see the LICENSE file included in this package for more details.

`llist` — Linked list datatypes for Python¶

`dllist` objects¶

`dllistnode` objects¶

`dllistiterator` objects¶

`sllist` objects¶

`sllistnode` objects¶

`sllistiterator` objects¶

Changes¶

Copyright¶

Indices and tables¶

Table of Contents

This Page

llist — Linked list datatypes for Python¶

dllist objects¶

dllistnode objects¶

dllistiterator objects¶

sllist objects¶

sllistnode objects¶

sllistiterator objects¶

Changes¶

Copyright¶

Indices and tables¶

`llist` — Linked list datatypes for Python¶

`dllist` objects¶

`dllistnode` objects¶

`dllistiterator` objects¶

`sllist` objects¶

`sllistnode` objects¶

`sllistiterator` objects¶