Source code for linked_list.tools
from ll import LL
from dll import DLL
[docs]def pushback(lst, node):
"""This pushes an element to the end of the linked list.
Has an :math:`\mathcal{O}(n)` where :math:`n` is the distance
of *lst* from the end of the list. Also works with both
:class:`~linked_list.ll.LL` and :class:`~linked_list.dll.DLL` classes.
:param lst: Is a member of the list where we want to insert the *node*.
:param node: The node which we want to insert into the linked list.
:returns: Returns *node* after inserting it.
:Example:
>>> import linked_list as ll
>>> lst = ll.LL(1)
>>> node = ll.LL(2)
>>> ll.pushback(lst, node)
>>> lst.nxt.data
2
"""
tn = type(node)
assert tn == type(lst)
assert tn in (LL, DLL)
curr = lst
while curr.nxt is not None:
curr = curr.nxt
curr.nxt = node
if tn == DLL:
node.prev = curr
return node
[docs]def pushfront(lst, node):
"""Pushes an element to the beginning of the linked list.
Has an :math:`\mathcal{O}(n)` where :math:`n` is the distance
of *lst* from the beginning of the list so most of the time
:math:`\mathcal{O}(1)`. This function only works with the
:class:`~linked_list.dll.DLL` class.
:param lst: Is a member of the list where we want to insert the *node*.
:param node: The node which we want to insert into the linked list.
:returns: The *node* that we inserted.
:Example:
>>> import linked_list as ll
>>> lst = ll.DLL(1)
>>> node = ll.DLL(2)
>>> ll.pushfront(lst, node)
>>> lst.prev.data
2
"""
assert type(node) == type(lst)
assert type(node) == DLL
curr = lst
while curr.prev is not None:
curr = curr.prev
curr.prev = node
node.nxt = curr
return node
[docs]def popfront(lst):
"""This pops the element from the beginning of the linked list.
Has an :math:`\mathcal{O}(n)` where :math:`n` is the distance
of *lst* from the beginning of the list. This works with the
:class:`~linked_list.dll.DLL` class.
:param lst: Is a member of the list where we want to pop
the first element from.
:returns: The first node.
:Example:
>>> import linked_list as ll
>>> lst = ll.DLL(1)
>>> node = ll.DLL(2)
>>> ll.pushback(lst, node)
>>> popfront(lst).data
1
"""
assert type(lst) == DLL
if lst.prev is None:
if lst.nxt is not None:
lst.nxt.prev, lst.nxt = None, None
return lst
curr = lst
while curr.prev is not None:
curr = lst.prev
curr.nxt.prev, curr.nxt, curr.prev = None, None, None
return curr
[docs]def popback(lst):
"""This pops the element from the end of the linked list.
Has an :math:`\mathcal{O}(n)` where :math:`n` is the distance
of *lst* from the end of the list. This works with both the
:class:`~linked_list.ll.LL` and :class:`~linked_list.dll.DLL`
classes.
:param lst: Is a member of the list where we want to pop
the last element from.
:returns: Returns the last node.
:Example:
>>> import linked_list as ll
>>> lst = ll.LL(1)
>>> node = ll.LL(2)
>>> ll.pushback(lst, node)
>>> popback(lst).data
2
"""
tl = type(lst)
assert tl in (LL, DLL)
if lst.nxt is None:
if tl == DLL and lst.prev is not None:
lst.prev.nxt, lst.prev = None, None
return lst
prev = lst
curr = lst.nxt
while curr.nxt is not None:
prev, curr = curr, curr.nxt
prev.nxt = None
if tl == DLL:
curr.prev = None
return curr
[docs]def delete(ancestor, node):
"""This deletes an element from the linked list.
Has an :math:`\mathcal{O}(n)` where :math:`n` is the distance
of *ancestor* from the *node*. Note that *ancestor* must come
before *node* in the list. This works with both the
:class:`~linked_list.ll.LL` and :class:`~linked_list.dll.DLL`
classes.
:param ancestor: Is a member of the list from where we want to
delete the *node* member.
:param node: The node we want to delete from the list.
:Example:
>>> import linked_list as ll
>>> lst = ll.LL(1)
>>> node = ll.LL(2)
>>> ll.pushback(lst, node)
>>> ll.pushback(lst, ll.LL(3))
>>> ll.delete(lst, node)
>>> lst.nxt.data
3
"""
tn = type(node)
assert tn == type(ancestor)
assert tn in (LL, DLL)
curr = ancestor
while curr.nxt not in (None, node):
curr = curr.nxt
curr.nxt = node.nxt
if tn == DLL and node.nxt is not None:
node.nxt.prev = curr
node.delete()
[docs]def from_list(lst, doubly=False):
"""This creates a new (doubly) linked list from a list.
The function is quite straightforward and creates a (doubly)
linked list in :math:`\mathcal{O}(n)` time.
:param lst: The python list from which we create the (doubly)
linked list from.
:param doubly: If `True` the function creates a doubly linked
list. By default it's `False`.
:returns: The created (doubly) linked list
:Example:
>>> import linked_list as ll
>>> lst = [1, 2]
>>> head = from_list(lst)
>>> (head.data, head.nxt.data, head.nxt.nxt)
(1, 2, None)
"""
if len(lst) == 0:
return None
cls = LL if not doubly else DLL
ret = curr = cls(0)
for el in lst:
curr.data = el
curr = pushback(curr, cls(0))
popback(ret)
return ret
[docs]def to_list(head):
"""This creates a list from a (doubly) linked list.
The function creates a list from a (doubly) linked
list in :math:`\mathcal{O}(n)` time.
:param head: The head node of the linked list or
any node of the doubly linked list.
:returns: The created list.
:Example:
>>> import linked_list as ll
>>> head = ll.DLL(0)
>>> ll.pushback(head, ll.LL(1))
>>> ll.pushback(head, ll.LL(2))
>>> ll.to_list(head.nxt)
[0, 1, 2]
"""
assert type(head) in (LL, DLL)
ret, curr = [], head
if type(curr) == DLL:
while curr.prev is not None:
curr = curr.prev
while curr is not None:
ret.append(curr.data)
curr = curr.nxt
return ret
[docs]def iter_list(node, backward=False):
"""Iterates through the elements of a list.
This function iterates through the elements
of the (doubly) linked list. If backward
is `True` and it's a doubly linked list
then it iterates backwards.
:param node: The node where the iteration
starts from.
:param backward: This is `False` by default.
If it's set to `True` then
it iterates backwards.
:Example:
>>> import linked_list as ll
>>> head = ll.from_list(range(3))
>>> for el in iter_list(head):
... el
...
0
1
2
"""
tn = type(node)
assert tn in (LL, DLL)
if backward:
assert tn == DLL
while node is not None:
yield node
node = node.prev if backward else node.nxt
raise StopIteration
[docs]def reverse(head):
"""Reverses a singly linked list.
Reverses a singly linked list in
:math:`\mathcal{O}(n)` time.
:param head: The head of the list to be
reversed.
:returns: The reversed list.
"""
stack = []
for el in iter_list(head):
stack.append(el.data)
ret = cret = LL(0)
while stack:
cret.data = stack.pop()
if stack:
cret = pushback(cret, LL(0))
return ret