1. Linear list
Python’s list and tuple adopt the implementation technology of sequence table, which has all the properties of sequence table .
2. Link table
The node of the one-way link table is a two-tuple.
The table element field elem holds the data item (or the associated information of the data item) as a table element, and the link field next holds the identification of the next node in the same table.
First define a simple table node class:
class LNode:
def __init__(self,elem,next_=None):
self.elem = elem
self.next = next_
There is only one initialization method in this class, which assigns values to two fields of the object. The second parameter of the method uses the name next_ to avoid the same name as the Python standard function next. This is also a convention for naming in Python programs. The second parameter also provides a default value, just for ease of use.
2.1 Basic linked list operations
Create an empty linked list
Just set the corresponding header variable to an empty link, and set it to None in the Python language .
Delete linked list
All nodes in this linked list should be discarded. The realization of this operation is related to the specific language environment. In some languages (such as C language), it is necessary to release the storage used by each node through explicit operations. In Python, this operation is very simple, just simply assign the table pointer to None to discard all the original nodes of the linked list. The storage management system of the Python interpreter will automatically reclaim unused storage.
Judging whether the table is empty
Compare the value of the table header variable with the empty link. In the Python language, it is to check whether the value of the corresponding variable is None.
Judging whether the table is full
Generally speaking, the linked list will not be full unless the program runs out of available storage space.
Add element
When adding a new element to the linked list, there is no need to move the existing data. You only need to arrange a new node for the new element, and then add The new node is connected to the correct element in the table. In other words, the operation of inserting a new element is achieved by modifying the link and accessing a new node, thereby changing the table structure.
Join the head of the table
-
Create a new node and save the data
-
Put the original data The link of the first node is stored in the link field next of the new node. This operation links a series of nodes of the original table after the new node just created.
-
Modify The header variable makes it point to the new node. This operation makes the new node actually the node pointed to by the header variable, that is, the first node of the table
q = LNode(13)
q.next = head.next
head = q
Note that even if head refers to an empty table before inserting, the above three steps can be completed correctly jobs. This insertion only arranges new storage and several assignments once, and the operation has constant time complexity.
General element insertion
If you want to insert a new node at a certain position in the singly linked list, you must first find the node before that position, because the new node needs After inserting it, you need to modify its next field
Set the variable pre to point to the previous node where the element is to be inserted. The operation is also divided into three steps:
q = LNode (13)
q.next = pre.next
pre.next = q
Delete element
Delete the first element of the table
General element deletion
Scan, locate and traverse
Complexity of linked list operation
Operation to find table
def length( head):
p,n = head,0
while p is not None:
n += 1
p = p.next
return n