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