Hướng dẫn python linked list library

Linked list is a simple data structure in programming, which obviously is used to store data and retrieve it accordingly. To make it easier to imagine, it is more like a dynamic array in which data elements are linked via pointers (i.e. the present record points to its next record and the next one points to the record that comes after it, this goes on until the end of the structure) rather than being tightly packed.

There are two types of linked list:

1. Single-Linked List: In this, the nodes point to the node immediately after it
2. Doubly Linked List: In this, the nodes not only reference the node next to it but also the node before it.

Linked List in Python:

To start with Python, it does not have a linked list library built into it like the classical programming languages. Python does have an inbuilt type list that works as a dynamic array but its operation shouldn’t be confused with a typical function of a linked list. This doesn’t mean one cannot implement a linked list in Python, they can but it will not be straight up. The following methods can be used to implement a linked list in Python since it does not have an inbuilt library for it:

Method 1: Using deque() package.
This is an inbuilt class in Python, obviously used for dequeue but can be implemented in such a way that it works like a linked list under certain conditions. 

Below is the implementation of the linked list:

Python3

import collections

linked_lst = collections.deque()

linked_lst.append('first')

linked_lst.append('second')

linked_lst.append('third')

print("elements in the linked_list:")

print(linked_lst)

linked_lst.insert(1, 'fourth')

print("elements in the linked_list:")

print(linked_lst)

linked_lst.pop()

print("elements in the linked_list:")

print(linked_lst)

linked_lst.remove('fourth')

print("elements in the linked_list:")

print(linked_lst)

 Output:

elements in the linked_list:
deque(['first', 'second', 'third'])
elements in the linked_list:
deque(['first', 'fourth', 'second', 'third'])
elements in the linked_list:
deque(['first', 'fourth', 'second'])
elements in the linked_list:
deque(['first', 'second'])

When to use deque() as a linked list?

• Inserting and deleting elements at front and back respectively is the only need. Inserting and removing elements from the middle becomes time-consuming.
• In-place reversal since Python now allows elements to be reversed in the place itself.
• Storage is preferred over performance and not all elements get a separate node of their own

Method 2: Using llist package.

The llist is an extension module for CPython providing basic linked list data structures. The type is given below command in your command line: 

pip install llist

Below is the implementation of the linked list:

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

Method 3: Using StructLinks package

StructLinks is used to easily Access and visualize different Data structures including Linked lists, Doubly Linked lists, Binary trees, Graphs, Stacks, and Queues.

The structlinks.LinkedList and structlinks.DoublyLikedList modules could be used to make linked lists. All the operations that could be performed with a list could also be performed with structlinks.LinkedList class.

Click to go to the documentation 

Type the command in your command line:

pip install structlinks

Below is the implementation of some methods of the linked list:

Python3

import structlinks

from structlinks import LinkedList

lst = LinkedList()

lst = LinkedList([1, 10.0, 'string'])

print(lst)

print()

print('Elements of list:')

element0 = lst[0]

element1 = lst[1]

element2 = lst[2]

print(f'first element : {element0}')

print(f'second element : {element1 }')

print(f'third element : {element2}')

print()

print('Length of list:')

length = len(lst)

print(f'size of the list : {length}')

print()

print('Set item:')

lst[0] = 10

print(f'list after setting lst[0] to 10 : {lst}')

print()

print('Append And Insert:')

lst.append('another string')

lst.insert(1, 0.0)

print(f'list after appending and inserting: {lst}')

print()

print('Pop and Remove')

element = lst.pop(0)

lst.remove(10.0)

print(f'list after popping and removing : {lst}')

print(f'pop function also returns the element : {element}')

Output: 

[1 -> 10.0 -> string]

Elements of list:
1
10.0
string

Length of list:
3

Set item:
list after setting lst[0] to 10 : [10 -> 10.0 -> string]

Append and Insert:
list after appending and inserting: [10 -> 0.0 -> 10 -> string -> another string]

Pop and Remove:
list after popping and removing: [0.0 -> string -> another string]