llist module in Python
Last Updated :
25 Nov, 2022
Up until a long time Python had no way of executing linked list data structure. It does support list but there were many problems encountered when using them as a concept of the linked list like list are rigid and are not connected by pointers hence take a defined memory space that may even be wasted if the list is not fully filled. In fact, to overcome the problems possessed by list Python’s dequeue data structure could also be employed to work like a linked list. But all of this has been covered because of llist.
llist module in Python
llist is an extension module of CPython that provides a basic linked list structure. They are significantly faster than dequeue and even the standard list for that matter.
Installation
To make use of benefits provided by llist it has to be installed like any other python extension or module, using pip. The following command will do the job.
pip install llist
If not for this, it can be manually downloaded from http://pypi.python.org/pypi , then unpack resources and compile them with “python setup.py install”. Once the module is successfully installed you only need to import this module whenever needed.
Methods provided
Currently, llist provides the following two types of linked lists:
- singly linked list(sllist) : a linked list in which the nodes point to the node next to it.
- doubly linked list(dllist) : a linked list in which the nodes point to the node after it as well as to the one before it.
This module contains following objects:
- dllist : object to implement doubly linked list
- dllistnode : returns a new doubly linked list node, initialized optionally
- dllistiterator: an iterator object for dllist
- sllist : object to implement singly linked list
- sllistnode : a singly linked list node, initialized optionally
- sllistiterator : an iterator object for sllist
The following examples will help you understand better. They give basic ideas about the execution of the two types of list supported by llist: Example 1: sllist
Python3
import llist
from llist import sllist, sllistnode
lst = sllist(['first', 'second', 'third'])
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
lst.append('fourth')
node = lst.nodeat(2)
lst.insertafter('fifth', node)
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
lst.pop()
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
node = lst.nodeat(1)
lst.remove(node)
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
|
Output:
sllist([first, second, third])
sllistnode(first)
sllistnode(third)
3
sllist([first, second, third, fifth, fourth])
sllistnode(first)
sllistnode(fourth)
5
sllist([first, second, third, fifth])
sllistnode(first)
sllistnode(fifth)
4
sllist([first, third, fifth])
sllistnode(first)
sllistnode(fifth)
3
Example 2: dllist
Python3
import llist
from llist import dllist, dllistnode
lst = dllist(['first', 'second', 'third'])
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
lst.append('fourth')
node = lst.nodeat(2)
lst.extendleft(['fifth', 'sixth'])
new_node = dllistnode('seventh')
ref_node = lst.nodeat(2)
lst.insertnode(new_node, ref_node)
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
lst.pop()
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
node = lst.nodeat(1)
lst.remove(node)
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
|
Output:
dllist([first, second, third])
dllistnode(first)
dllistnode(third)
3
dllist([sixth, fifth, seventh, first, second, third, fourth])
dllistnode(sixth)
dllistnode(fourth)
7
dllist([sixth, fifth, seventh, first, second, third])
dllistnode(sixth)
dllistnode(third)
6
dllist([sixth, seventh, first, second, third])
dllistnode(sixth)
dllistnode(third)
5
Please Login to comment...