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.
We can create linked lists from python lists with the help
of the from_list operation:
>>> lst = range(2)
>>> head = ll.from_list(lst)
>>> head.nxt.data
1
We can also transform linked lists back to python lists by
using the to_list:
>>> lst2 = ll.to_list(head)
>>> print 1 if lst2 == lst else 2
1
We can also iterate through the elements of a linked list
using the iter_list function:
>>> for el in iter_list(head):
... el
...
0
1
2
Also linked lists have a nice string representation:
>>> head
0->1->2
The len function works on linked lists:
>>> len(head)
3
>>> len(head.nxt)
2
One can also reverse a singly linked lists with the
reverse operation:
>>> rhead = ll.reverse(head)
>>> rhead
2->1->0
Working with doubly linked lists¶
All the operations of the singly linked lists(
other than reverse)
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
The from_list function works a little
bit differently for the DLL class and the
class as a different string representation so one can distinguish
between the two different linked list classes:
>>> head = ll.from_list(range(2), True)
>>> head
0<->1<->2
Also we can iterate backwards on doubly linked lists:
>>> for el in iter_list(head.nxt.nxt, True):
... el
...
2
1
0
The len function also works for doubly linked lists, but it always reports the length of the list in both directions:
>>> len(head)
3
>>> len(head.nxt)
3
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
LLandDLLclasses.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
DLLclass.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
LLandDLLclasses.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
DLLclass.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
LLandDLLclasses.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)[source]¶ 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)[source]¶ 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)[source]¶ 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
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.