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).
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 dllistnode object in the list. None if list is empty. This attribute is read-only.
Last dllistnode object in the list. None if list is empty. This attribute is read-only.
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):
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.
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.
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.
Add x to the right side of the list if before and after are not specified, or if before specified, insert x to the left side of dllistnode before, otherwise, insert x to the right side of dllistnode after. 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.
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.
Iterate over the list starting from the first node. If to is specified, iteration stops when the current node becomes equal to argument to.
Remove and return an element’s value from the right side of the list.
Raises ValueError if self is empty.
Remove and return an element’s value from the left side of the list.
Raises ValueError if self is empty.
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 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.
In addition to these methods, dllist supports iteration, cmp(lst1, lst2), 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 pyllist 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
>>> for node in lst.iternodes(): # iterate over list nodes
... print node,
dllistnode(1) dllistnode(2) dllistnode(3)
>>> for node in lst.nodeat(1).iternext(): # iterate starting node with index 1
... print node,
dllistnode(2) dllistnode(3)
>>> for node in lst.nodeat(1).iterprev(): # iterate back starting node with index 2
... print node,
dllistnode(2) dllistnode(1)
>>> 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])
>>> 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
>>> cmp(dllist(), dllist([])) # list comparison (lexicographical order)
0
>>> cmp(dllist([1, 2, 3]), dllist([1, 3, 3]))
-1
>>> cmp(dllist([1, 2]), dllist([1, 2, 3]))
-1
>>> cmp(dllist([1, 2, 3]), dllist())
1
>>> 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])
Return a new doubly linked list node, initialized (optionally) with value.
dllistnode objects provide the following attributes:
Next node in the list. This attribute is read-only.
Previous node in the list. This attribute is read-only.
Value stored in this node. Read-write attribute.
dllistnode objects also support the following methods:
Iterate to the tail of the list starting from the current node. If to is specified, iteration stops when the current node becomes equal to argument to.
Iterate to the head of the list starting from the current node. If to is specified, iteration stops when the current node becomes equal to argument to.
Note that value stored in the node can also be obtained through the __call__() method (using standard node() syntax).
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 sllistnode object in the list. None if list is empty. This attribute is read-only.
Last sllistnode object in the list. None if list is empty. This attribute is read-only.
Number of elements in the list. 0 if list is empty. This attribute is read-only.
sllist objects also support the following methods:
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.
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.
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.
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 type sllistnode.
Raises ValueError if node does not belong to self.
This method has O(1) complexity.
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 type sllistnode.
Raises ValueError if node does not belong to self.
This method has O(n) complexity.
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.
Iterate over the list starting from the first node. If to is specified, iteration stops when the current node becomes equal to argument to.
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 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.
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 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.
In addition to these methods, sllist supports iteration, cmp(lst1, lst2), 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 pyllist 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 node in lst.iternodes(): # iterate over list nodes
... print node,
sllistnode(1) sllistnode(2) sllistnode(3)
>>> for node in lst.nodeat(1).iternext(): # iterate starting node with index 1
... print node,
sllistnode(2) sllistnode(3)
>>> 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])
>>> node = lst.nodeat(2)
>>> lst.insert(1.5, node) # insert 1.5 before node
<sllistnode(1.5)>
>>> print lst
sllist([0, 1, 1.5, 2, 3, 4, 5])
>>> lst.insert(6) # append value to the right side of the list
<sllistnode(6)>
>>> print lst
sllist([0, 1, 1.5, 2, 3, 4, 5, 6])
>>> lst.popleft() # remove leftmost node from the list
0
>>> print lst
sllist([1, 1.5, 2, 3, 4, 5, 6])
>>> lst.popright() # remove rightmost node from the list
6
>>> print lst
sllist([1, 1.5, 2, 3, 4, 5])
>>> node = lst.nodeat(1)
>>> lst.remove(node) # remove 2nd node from the list
1.5
>>> print lst
sllist([1, 2, 3, 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
>>> cmp(sllist(), sllist([])) # list comparison (lexicographical order)
0
>>> cmp(sllist([1, 2, 3]), sllist([1, 3, 3]))
-1
>>> cmp(sllist([1, 2]), sllist([1, 2, 3]))
-1
>>> cmp(sllist([1, 2, 3]), sllist())
1
>>> 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])
Return a new singly linked list node, initialized (optionally) with value.
sllistnode objects provide the following attributes:
Next node in the list. This attribute is read-only.
Value stored in this node. Read-write attribute.
sllistnode objects also support the following method:
Iterate to the tail of the list starting from the current node. If to is specified, iteration stops when the current node becomes equal to argument to.
Note that value stored in the node can also be obtained through the __call__() method (using standard node() syntax).
pyllist-0.1.1 (2013-03-02)
Values stored in nodes are mutable.
of the list (or a node specified in the argument ‘to’).
An example of usage can be found in ./examples/insertion_sort.py
lst.insert() has new attribute [after] in addition to the existing [before]
pyllist-0.1 (2012-01-01)
Initial release
This module is copyrighted by Adam Jakubek, Rafał Gałczyński and Oleksandr Pryymak.
It is distributed under the MIT license. Please see the LICENSE file included in this package for more details.