Operations on linked lists

Functions to add elements to the linked list

linked_list.tools.pushback(lst, node)

This pushes an element to the end of the linked list.

Has an \(\mathcal{O}(n)\) where \(n\) is the distance of lst from the end of the list. Also works with both LL and DLL classes.

Parameters:

• lst – Is a member of the list where we want to insert the node.
• 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

linked_list.tools.pushfront(lst, node)

Pushes an element to the beginning of the linked list.

Has an \(\mathcal{O}(n)\) where \(n\) is the distance of lst from the beginning of the list so most of the time \(\mathcal{O}(1)\). This function only works with the DLL class.

Parameters:

• lst – Is a member of the list where we want to insert the node.
• 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

Functions to remove elements from a linked list

linked_list.tools.popback(lst)

This pops the element from the end of the linked list.

Has an \(\mathcal{O}(n)\) where \(n\) is the distance of lst from the end of the list. This works with both the LL and DLL classes.

Parameters: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

linked_list.tools.popfront(lst)

This pops the element from the beginning of the linked list.

Has an \(\mathcal{O}(n)\) where \(n\) is the distance of lst from the beginning of the list. This works with the DLL class.

Parameters: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

linked_list.tools.delete(ancestor, node)

This deletes an element from the linked list.

Has an \(\mathcal{O}(n)\) where \(n\) is the distance of ancestor from the node. Note that ancestor must come before node in the list. This works with both the LL and DLL classes.

Parameters:

• ancestor – Is a member of the list from where we want to delete the node member.
• 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

Functions to transform linked lists to and from python lists.

linked_list.tools.to_list(head)

This creates a list from a (doubly) linked list.

The function creates a list from a (doubly) linked list in \(\mathcal{O}(n)\) time.

Parameters: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]

linked_list.tools.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 \(\mathcal{O}(n)\) time.

Parameters:

• lst – The python list from which we create the (doubly) linked list from.
• 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)

Functions to iterate through the elements of the linked list.

linked_list.tools.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.

Parameters:

• node – The node where the iteration starts from.
• 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

Miscellaneous functions

linked_list.tools.reverse(head)

Reverses a singly linked list.

Reverses a singly linked list in \(\mathcal{O}(n)\) time.

Parameters:head – The head of the list to be reversed. Returns:The reversed list.