A linked list is a non-sequential and non-sequential storage structure on a physical storage unit, and the logical order of data elements is realized through the link order of pointers in the linked list. The linked list is composed of a series of nodes (each element in the linked list is called a node), and the nodes can be dynamically generated at runtime. Each node consists of two parts: one is a data field that stores data elements, and the other is a pointer field that stores the address of the next node. Compared with the linear list sequential structure, the operation is more complicated. Since it does not have to be stored in order, the linked list can reach the complexity of O(1) when inserting, which is much faster than another linear list sequence table, but it takes O(n) to find a node or access a specific numbered node time, and the corresponding time complexities of linear table and sequential table are O(logn) and O(1) respectively.
Using the linked list structure can overcome the shortcoming that the array linked list needs to know the data size in advance, and the linked list structure can make full use of the computer memory space and realize flexible memory dynamic management. However, the linked list loses the advantage of random read of the array, and at the same time, the linked list has a relatively large space overhead due to the increase of the pointer field of the node. The most obvious advantage of the linked list is that the way the conventional array arranges the associated items may be different from the order of these data items in memory or on the disk, and the access of data often needs to be converted in different arrangement orders. Linked lists allow insertion and removal of nodes at arbitrary positions on the list, but do not allow random access. There are many different types of linked lists: singly linked lists, doubly linked lists, and circular linked lists.
Here we will briefly implement the singly linked list, and implement its most basic operations such as adding, deleting, modifying, checking, inserting, etc.
First, implement a single element of the linked list – node. The method of class is used to create the node. It is worth noting that python has no pointer, but there is next, which can approximately replace the function of the pointer. The specific code is as follows:
class Node():
def __init__(self, elem):
'''Node'''
self.elem = elem # element field
self.next = None # pointer field
After implementing the node class, we then implement a linked list class, which includes operations such as addition, deletion, modification, query, and insertion.
First of all, the initialization of the linked list is relatively simple, because the linked list only needs one head node. Therefore, the linked list only needs to realize the initialization of the head node during the initialization process. If it is necessary to initialize the head node to some specified The value of , only needs to be slightly changed in the code to realize, the initialization of the linked list is as follows:
class Linklist():
def __init__(self):
'''Create head node'''
self.head = None
After the initialization is complete, let’s implement some basic linked list property operations, such as the length of the linked list, whether it is empty, etc. The specific code is as follows:
def is_empty(self):
# Since the head node of the initialized linked list is empty, as long as the head node of the linked list is empty, the linked list is empty
return self.head == None
def lenght(self):
cur = self.head # counting starts from head
count = 0
while cur is not None: # count end position
count + = 1
cur = cur. next
return count
Next, the operation of increasing is realized. There are two operations for increasing here: head insertion method and tail insertion method. Suppose we use the first element passed into the linked list as the head of the table, the head does not move, and the head is inserted after the head The first position is used as the insertion point, and the last position is used as the insertion point for tail insertion. The code for head insertion and tail insertion is as follows:
# tail insertion method
def add(self,elem):
node = Node(elem) # Instantiate the incoming value as a node class
if self.head is None: #If the head node is empty, hang on to the head node
self.head = node
else:
cur = self.head
# Here choose cur.next as the judgment condition of the loop, mainly because it is easy to operate
# Since cur.next is empty when exiting the loop, that is, cur at this time is the last element on the left at the end of the linked list. At this time, just mount the node directly after the linked list
# If cur is selected as the condition for judging loop exit, then cur is empty when exiting, and it will not be able to link with the linked list at this time
while cur.next is not None:
cur = cur. next
cur.next = node
# header interpolation
def add_head(self, elem):
node = Node(elem)
node.next = self.head.next
self.head.next = node
The code is relatively simple, so I won’t go into details here. If you have any unclear children’s shoes, you can refer to the following example. The picture is from Baidu and slightly modified:
For the insertion and deletion operations, since the code is similar to the above operations, I won’t go into details here, just upload the code directly. If you have any questions, you can send a private message to the blogger, and I will answer you as soon as possible!
def insert_(self,pos,elem):
cur = self.head
temp = 0
while temp < pos-1: # Pay attention to the shift, which is one less than the insertion position
cur = cur. next
temp + = 1
node = Node(elem)
node.next = cur.next
cur.next = node
def remove_index(self,ind): # Delete by pressing the index
cur = self.head
count = 0
while count < ind-1:
cur = cur. next
count + = 1
cur.next = cur.next.next # delete operation
def remove_val(self,val): # remove by value
cur = self.head
while cur is not None:
# For ease of operation, cur.next will be selected here as a reference for easy deletion
if cur.next.elem == val:
cur.next = cur.next.next # delete operation
return
cur = cur. next
else:
# If the loop is executed normally, that is, the above return operation does not appear, it means that the value does not exist in the linked list
print("None!")
return
As for the search operation, in fact, the above process already includes its operation idea. The specific operation is basically the same as the delete by value. The code is as follows:
def search(self,val):
count = 0
cur = self.head
while cur.next is not None:
if cur.elem == val:
return count
count + = 1
cur = cur. next
else:
print("None!")
return
At this point, the basic operations of the linked list have been realized. The following are some experimental examples and complete codes:
'''one-way linked list'''
class Node():
def __init__(self, elem):
'''Node'''
self.elem = elem
self. next = None
class Linklist():
def __init__(self):
'''Create head node'''
self.head = None
def is_empty(self):
return self.head == None
def lenght(self):
cur = self.head # counting starts from head
count = 0
while cur is not None:
count + = 1
cur = cur. next
return count
def travel(self):
cur = self.head
while cur is not None:
print(cur.elem, end = ' ')
cur = cur. next
def add(self,elem):
node = Node(elem)
if self.head is None:
self.head = node
else:
cur = self.head
while cur.next is not None:
cur = cur. next
cur.next = node
def add_head(self, elem):
node = Node(elem)
node.next = self.head.next
self.head.next = node
def insert_(self, pos, elem):
cur = self.head
temp = 0
while temp < pos-1: # Pay attention to the shift, which is one less than the insertion position
cur = cur. next
temp + = 1
node = Node(elem)
node.next = cur.next
cur.next = node
def remove_index(self, ind):
cur = self.head
count = 0
while count < ind-1:
cur = cur. next
count + = 1
cur.next = cur.next.next
def remove_val(self, val):
cur = self.head
while cur is not None:
if cur.next.elem == val:
cur.next = cur.next.next
return
cur = cur. next
else:
print("None!")
return
def search(self, val):
count = 0
cur = self.head
while cur.next is not None:
if cur.elem == val:
return count
count + = 1
cur = cur. next
else:
print("None!")
return
if __name__=="__main__":
import os
os.system("cls")
link = Linklist()
print(link. is_empty())
for i in range(10):
link. add(i)
print('length: ', link. length())
link. travel()
print()
for j in range(10,20):
link. add_head(j)
print('length: ', link. length())
link. travel()
print()
link.insert_(3,100)
link. travel()
print()
link. remove_index(2)
link. travel()
print()
link. remove_val(10)
link. travel()
print()
ind = link. search(19)
print(ind)
The above is the entire content of this article. If you have any corrections or doubts, welcome to discuss in the comment area!
The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treehomepage overview 46162 people are studying systematically