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.