Documentation for the linked_list module¶

Getting started with the linked_list module¶

Working with singly linked lists¶

So for example you create a singly linked list(LL) with 5 elements in the following way using the pushback operation:

>>> import linked_list as ll
>>> lst = ll.LL(1)
>>> for i in xrange(2, 6):
...   ll.pushback(ll.LL(i))

This creates a linked list with 5 nodes and lst as the head element. Suppose now we want to pop the last element. We can do it with the popback operation like this:

>>> ll.popback(lst).data
4

Now our list has only 4 elements. Now suppose we want to delete the third element. We can do this with the delete operation:

>>> ll.delete(lst, lst.nxt.nxt)
>>> lst.nxt.nxt.data
3

As we can see this deleted the third element from the list.

Working with doubly linked lists¶

All the operations of the singly linked lists also support doubly linked lists(DLL). Let’s create a linked list by pushing elements with pushfront to the beginning of the list:

>>> import linked_list as ll
>>> lst = ll.DLL(4)
>>> for i in xrange(3, -1, -1):
...   ll.pushfront(lst, ll.DLL(i))
...   lst = lst.prev

So our list will have 5 elements just like in the singly linked list example but now it’s a doubly linked list. The only operation that we haven’t seen before is the popfront operation. Let’s see an example for that one too:

>>> lst = lst.nxt
>>> ll.popfront(lst).data
0

And basically that’s all what this package is currently capable of.

Operations on linked lists¶

Functions to add elements to the linked list¶

linked_list.tools.pushback(lst, node)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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)[source]¶

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

The node classes¶

class linked_list.ll.LL(data=None, nxt=None)[source]¶

Node class for the singly linked list.

The class has 2 members which are the following:

data: This is the the data that is stored in

the current node. By default it’s None.
nxt: Points to the next node in the linked

or it’s None if there is no next node.

class linked_list.dll.DLL(data=None, prev=None, nxt=None)[source]¶

Node class for the doubly linked list.

The class has 3 members which are the following:

data: This is the the data that is stored in

the current node. By default it’s None.
prev: Points to the previous node in the

linked list or it’s None if there is no previous node.
nxt: Points to the next node in the linked

or it’s None if there is no next node.