cllist
— 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
.
Efficency / Complexity¶
All data types defined in this module support efficient O(1) insertion.
You should always choose to use a dllist
(double-linked list) over an sllist
for performance reasons.
The dllist
implementation holds the traditional references to “start” and “end”, as well as a unique implementation wherein the “middle” node is also tracked.
This ensures that the worst-case time complexity for an operation in a dllist
is O( n/4 ), with average complexity for non-O(1) operations at O( n / 8 ).
On the other hand, sllist
has many operations which are worst-case O(n), average access at O(n/2), and some operations (such as appending to the right) are O(n)!
With dllist
, the shortest distance (from start, from middle, or from end, bi-directional) is alaways calculated before performing an operation, which minimizes the amount of nodes that have to be touched.
A dllist will outperform or at least be equal in performance to a native python list, depending on the usage scenario.
dllist
objects¶
-
class
cllist.
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.
-
middle
¶ Middle
dllistnode
object in the list, if the list size is greater-than 10 elements, or None if the list has 10 or fewer elements.This is a unique extension of the doubly-linked list unique to the “cllist” implementation, and ensures that worst-case time for most operations is O( n/4 ) and average O(n / 8 ).
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 withappend()
).Argument x might be a
dllistnode
. In that case a new node will be created and initialized with the value extracted from x.
-
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.
-
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 inserteddllistnode
.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 typedllistnode
.Raises
ValueError
if before does not belong to self.
-
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/4) worst-case complexity, and averages O( n/8 ) [for n = list size] due to the use of “middle” and bi-directional walking in this implementation.
-
pop
([index])¶ Remove and return the element’s value from a given index. If index is not provided, will pop from the right side of the list.
Raises
ValueError
if self is empty.
-
index
(value)¶ Returns the first index of a value
Raises
ValueError
if value is not present
-
rindex
(value)¶ Returns the last index of a valuea
Raises
ValueError
if value is not present
-
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 typedllistnode
.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 the same time complexity as finding an element, thus averages out at O(n / 8 ) (with regards to the size of the list).
In addition to these methods,
dllist
supports iteration,cmp(lst1, lst2)
, rich comparison operators, constant timelen(lst)
,__contains__ (in operator)
,mappings
,slicing
, and subscript referenceslst[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
dllist
elements (using for or list comprehensions) will also directly yield values stored in nodes.Like most containers,
dllist
objects can be extended usinglst1 + lst2
andlst * num
syntax (including in-place+=
and*=
variants of these operators).Example:
>>> from cllist 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 list elements ... print(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]) >>> lst.extendright([6, 7, 8]) # right-extend list with elements from iterable >>> print(lst) dllist([0, 1, 2, 3, 4, 5, 6, 7, 8]) >>> 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]) >>> 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]) >>> lst.popleft() # remove leftmost node from the list 0 >>> print(lst) dllist([1, 1.5, 2, 3, 4, 5, 6]) >>> lst.popright() # remove rightmost node from the list 6 >>> print(lst) dllist([1, 1.5, 2, 3, 4, 5]) >>> node = lst.nodeat(1) >>> lst.remove(node) # remove 2nd node from the list 1.5 >>> print(lst) dllist([1, 2, 3, 4, 5]) >>> 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])
-
dllistnode
objects¶
-
class
cllist.
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.
Note that value stored in the node can also be obtained through the
__call__()
method (using standardnode()
syntax).-
dllistiterator
objects¶
-
class
cllist.
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, notdllistnode
objects.Example:
>>> from cllist import dllist >>> lst = dllist([1, 2, 3]) >>> for value in lst: ... print(value * 2) 2 4 6
sllist
objects¶
-
class
cllist.
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.
-
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.
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, node)¶ Inserts x after node 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 node is not of typesllistnode
.Raises
ValueError
if before does not belong to self.This method has O(1) complexity.
-
insertbefore
(x, node)¶ Inserts x before node 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 node is not of typesllistnode
.Raises
ValueError
if before does not belong to self.This method has O(n) complexity.
-
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
([index])¶ Remove and return the element’s value from a given index. If index is not provided, will pop from the right side of the list.
Raises
ValueError
if self is empty.This method has O(n) time complexity.
-
index
(value)¶ Returns the first index of a value
Raises
ValueError
if value is not present
-
rindex
(value)¶ Returns the last index of a valuea
Raises
ValueError
if value is not present
-
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 typesllistnode
.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 timelen(lst)
,__contains__ (in operator)
,mappings
,slicing
, and subscript referenceslst[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 usinglst1 + lst2
andlst * num
syntax (including in-place+=
and*=
variants of these operators).Example:
>>> from cllist 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 >>> 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]) >>> lst.extendright([6, 7, 8]) # right-extend list with elements from iterable >>> print(lst) sllist([0, 1, 2, 3, 4, 5, 6, 7, 8]) >>> 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]) >>> 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]) >>> lst.popleft() # remove leftmost node from the list 0 >>> print(lst) sllist([1, 1.5, 2, 2.5, 3, 4, 5]) >>> lst.popright() # remove rightmost node from the list 5 >>> print(lst) sllist([1, 1.5, 2, 2.5, 3, 4]) >>> node = lst.nodeat(1) >>> lst.remove(node) # remove 2nd node from the list 1.5 >>> print(lst) sllist([1, 2, 2.5, 3, 4]) >>> 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])
-
sllistnode
objects¶
-
class
cllist.
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.
Note that value stored in the node can also be obtained through the
__call__()
method (using standardnode()
syntax).-
sllistiterator
objects¶
-
class
cllist.
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, notsllistnode
objects.Example:
>>> from cllist import sllist >>> lst = sllist([1, 2, 3]) >>> for value in lst: ... print(value * 2) 2 4 6
Changes¶
- cllist-1.0.3 - Jun 18 2017
- Some cleanups in the build process
cllist-1.0 - Apr 12 2017
Forked from python-llist to python-cllist
Work by Tim Savannah:
- Implement pop(idx) to pop any given index
- Implement “contains” sequence method, so the “in” operator doesn’t run the whole list multiple times
- Implement “index” and “rindex” methods to return an index/rindex
- Remove “last_accessed_idx” and “last_accessed” node from dllist, replace with “middle” which is used when
- the list size exceeds a certain value (defined as 10). This greatly improves random-access and random-pop performance on dllist to be comprable or better to that of a base python list
- Remove the “hash” function, which did NOT generate unique hashes (very easy to construct two linked lists with same hash,
- such as [1, 5, 7] and [5, 1, 7] or [2, 1] and [3]
- Remove all compiler warnings
- Add some basic benchmarks
- Add some more tests
- Some minor cleanups
- Move types into headers, make generic LList node and list structures, which are common to both double and single linked lists.
- Allow a double-linked list to extend with a single-linked list, and a single-linked list to extend with a double (for much higher performance)
- Implement mappings on sllist and dllist
- Implement slicing (including with step) on both sllist and dllist
- Add __version__ and __version_tuple__
- Some general optimizations
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.