catalogue
Implementation of linked list in python
How memory works
When you go to the supermarket, you should see a storage cabinet at the door. When you go to the supermarket, you store your things in the storage cabinet. If you have a lot of things, you may need to open two cabinets to put your things. Then you just need to go to the supermarket with the small ticket of the storage cabinet. After visiting the supermarket, you take out your things with the small ticket. In fact, the working principle of computer memory is roughly like this,. The computer is a collection of lockers at the entrance of the supermarket. Each individual locker has a corresponding ticket and their address.
When we need to store data in memory, we request to the computer, and the computer allocates us a piece of space for storage.
Arrays and linked lists
array
An Array is an ordered sequence of elements. All its elements are connected (close together) in memory.
Linked list
Linked list is a non continuous and non sequential storage structure on the physical storage unit. The logical order of data elements is realized through the pointer link order in the linked list, that is, the elements in the linked list can be stored anywhere in the memory. The linked list stores the address of each element, that is, the next element. Therefore, when inserting elements, it has more advantages than the array, because it only needs to store the elements in memory and then store their address in the previous element. It does not need to abdicate the following elements in turn like the array.
Compare
Overall comparison
| array | Linked list | |
| Memory occupation | Continuous memory space required | No contiguous memory space is required |
| Variable size | It is fixed and allocated as much as possible. It cannot be expanded dynamically, which may waste memory | The size of the linked list can change dynamically |
| Insert (middle) | Slow, you need to move all elements after the inserted element back | Faster, just put it in memory and put its address in the previous element |
| delete | Slow, all elements after deleting elements need to be moved forward | Faster, you only need to modify the address pointed to by the previous element |
| query | Faster and can be accessed directly through subscript | Slow, only by traversing the query |
| Access form | Random access or sequential access | Sequential access only |
| Expansibility | Non dynamically extensible | Can be extended dynamically |
| Storage data type | Must be consistent | Can be inconsistent |
Time complexity
| query | insert | delete | |
| array | O(1) | O(n) | O(n) |
| Linked list | O(n) | O(1) | O(1) |
It should be noted that if the array is randomly queried by subscript, its time complexity is O(1), but if it is accessed in sequence, its time complexity is O(n) as the linked list. However, if it is an ordered array and accessed in sequence, its time complexity is O(logn) according to binary search. The above insertion and deletion are only one operation, The query time is not included. The reason why the time complexity of the array insertion and deletion operation is O(n) is that when the array inserts and deletes an element, the positions of other elements must move accordingly. The time complexity of inserting in the head and tail is O(n), while the linked list only needs to insert elements and add addresses to the previous element. All the time complexity is O(1), Generally speaking, we should not remember the conclusion too much, and we need to analyze the actual situation flexibly.
In real life, arrays are used more often because they support random access. You can directly jump to the element you want by subscript. All of them have faster reading speed. In life, random access is required in many cases.
Implementation of linked list in python
The following will briefly demonstrate the implementation of one-way linked list. Bidirectional linked list, the implementation of circular linked list, you can go to see this article
Linked list of Python data structure - Zhihu
It mainly realizes the functions of one-way list and deletion of knowledge
# @Time:2022/1/2813:21
# @Author: Zhongyi
# @File: linked list py
# @ps:tutu qqnum:2117472285
# #Define node
class Node(object):
#Node of one-way linked list
def __init__(self,item):
self.item=item#item stores data elements
self.next=None#Next is the identification of the next node
class SingleLinkList(object):
#Unidirectional linked list
def __init__(self):
self.head=None
def is_empty(self):
#Determine whether the linked list is empty
return self.head == None
def length(self):
#Linked list length
#The initial pointer points to the head
cur=self.head
count=0
#The pointer to None indicates that the tail is reached
while cur != None:
count+=1
#Pointer down
cur=cur.next
return count
def items(self):
#Traversal linked list
#Get head pointer
cur=self.head
#Loop traversal
while cur is not None:
#Return to generator
yield cur.item
cur=cur.next
def add(self,item):
#Add elements to the head of the linked list
node=Node(item)
#The new node pointer points to the original header node
node.next=self.head
#Modify the header node pointer to a new node
self.head=node
def append(self,item):
#Add element to tail
node=Node(item)
#First judge whether it is an empty linked list
if self.is_empty():
#Empty linked list, with head pointing to the new node
self.head=node
else:
#It is not an empty linked list. Find the tail and point the tail next node to the new node
cur=self.head
while cur.next != None:
cur=cur.next
cur.next=node
def insert(self, index, item):
# Insert element at specified location
# The specified position is inserted in the header before the first element
if index <= 0:
self.add(item)
# If the specified position exceeds the tail, insert it at the tail
elif index > (self.length() - 1):
self.append(item)
else:
# Create element node
node = Node(item)
cur = self.head
# Cycle to where you want to insert
for i in range(index - 1):
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
#Delete element
cur = self.head
pre = None
while cur != None:
# The specified element was found
if cur.item == item:
# If the first one is the deleted node
if not pre:
# Point the header pointer to the next node of the header node
self.head = cur.next
else:
# Point the next of the node before the deletion location to the next node after the deletion location
pre.next = cur.next
return True
else:
# Continue to move the node backward according to the linked list
pre = cur
cur = cur.next
def find(self, item):
#Find whether the element exists
return item in self.items()test
if __name__ == '__main__':
link_list=SingleLinkList()
#Add element
for i in range(5):
link_list.append(i)
print('Node:',end='')
for i in link_list.items():
print(i, end='\t')
#Insert element in header
link_list.add(6)
print('After inserting the header element:',end='')
for i in link_list.items():
print(i, end='\t')
#Add element to tail
link_list.append(10)
print('After adding elements to the tail:',end='')
for i in link_list.items():
print(i,end='\t')
#Middle insert element
print('')
link_list.insert(3,9)
print('After inserting an element in the middle:',end='')
for i in link_list.items():
print(i, end='\t')
#Delete element
link_list.remove(3)
print('After deleting an element:',end='')
for i in link_list.items():
print(i, end='\t')
#Find element
a=link_list.find(4)
print('Find 4 this element:',end='')
print(a)
Operation results:
Select sort
If the counselor asks you to do performance analysis and make you rank the performance points of the whole major from high to low, what should you do?
| full name | GPA |
| Zhang San | 2.1 |
| Li Si | 3.2 |
| Old five | 4.2 |
| Wang Mazi | 0.8 |
One way is to traverse the list and find the person with the highest grade point, then add it to a new list, and then repeat this operation to get a sequential list, which is selective sorting. The time complexity is O(n^2)
Another method is to use the method of selective sorting. The time complexity is O (nlogn), which is faster than selective sorting. Here we only explain the selection sort, and then we will talk about quick sort.
This is a descending order. The idea of descending order is the same
# @Time:2022/1/301:02
# @Author: Zhongyi
# @File: select sort py
# @ps:tutu qqnum:2117472285
#Find the largest element and return its subscript
def find_Max_num(arr):
Max_num=arr[0]
Max_num_index=0
for i in range(1,len(arr)):
if arr[i]>Max_num:
Max_num=arr[i]
Max_num_index=i
return Max_num_index
#sort
def sort_num(arr):
newArr=[]
for i in range(len(arr)):
Max_num_index=find_Max_num(arr)
newArr.append(arr.pop(Max_num_index))#Find one, pop it up once and cycle again
return newArr
if __name__ == '__main__':
arr=[3.1,3.5,0.2,4.2]
new=sort_num(arr)
print(new)
Operation results:
[4.2, 3.5, 3.1, 0.2]
Summary
- Computer memory is like a pile of lockers
- To store multiple elements, you can use arrays or linked lists
- The element addresses of the array are linked together
- The element addresses of the linked list are separated, and each element contains the address of the next element
- There are two ways to access arrays, random access and sequential access. Random access is very fast
- Linked list has only one access mode, sequential access, and the access speed is slow
- The insertion and deletion speed of linked list is very fast, and the array is slow
- In the same array, the types of all elements must be the same, and the linked list can be inconsistent