Detailed explanation of Python implementation of static linked list case
- 2021-11-30 00:39:18
- OfStack
The difference between static linked list and dynamic linked list
What static linked lists and dynamic linked lists have in common is that the "1-to-1" logical relationship between data is maintained by pointers (called "cursors" in static linked lists).
Static linked list
To use static linked list to store data, it is necessary to apply for a large enough memory space in advance, that is to say, the number of data elements stored in static linked list has been determined from the moment it is created, and cannot be changed later.
Moreover, the static linked list randomly stores each data element in a fixed storage space, which leads to the need to use another linked list (usually called "standby linked list") to record the location of the space storage space in the static linked list, so as to allocate it to newly added elements later.
This means that if you choose to use static linked lists to store data, you need to manipulate two linked lists, one to store data and the other to record the location of free space.
Dynamic linked list
Using dynamic linked list to store data, you don't need to apply for memory space in advance, but only apply for memory when you need it. That is to say, the number of data elements stored in the dynamic linked list is unlimited, and you can store as many as you want.
At the same time, with the whole process of dynamic linked list, you only need to control one linked list to store data. When adding or deleting data elements in a table, you only need to apply for or free space through malloc or free functions, which is relatively simple to implement.
Static linked list implemented by python
The design thinking of static linked list is very clever. The one-way linked list structure is completed by index and cursor. Compared with the list with sequential structure, it saves the expenditure of data shift and memory fragmentation.
python implementation of static linked list code, static linked list using list structure storage.
class Node:
def __init__(self, next, val=None):
self.val = val # Value
self.next = next # Cursor. Finally 1 The cursor of 10 elements must be 0
class SLinkList:
# Allocate the length of the linear table and define the linear table
def __init__(self, size=7):
self.size = size
self.link = [Node((i + 1) % self.size) for i in range(self.size)]
# Linear table emptying
def clearSLL(self):
self.__init__()
# Whether the linear table is empty
def isEmpty(self):
return False if self.link[self.size - 1].next else True
# Find an empty location
def findEmpty(self):
ind = self.size
for i in range(1, self.size - 1):
if self.link[i].val is None:
ind = i
break
return ind
# Insert an element at a specified position
def insert(self, ind, ele):
sua = -1
# Front 1 Elements
pre = self.size - 1
# Insert the position of the element (the first 1 Empty positions)
insertLoc = self.link[0].next
# Conditional judgment
if ind < 1 or ind >= pre or insertLoc >= self.size:
return 0
# No. 1 1 Index of elements
for i in range(1, self.size - 1):
index = self.link[pre].next
if i == ind:
self.link[pre].next = insertLoc
# Element insertion
self.link[insertLoc].val = ele
self.link[insertLoc].next = index
# First element
self.link[0].next = self.findEmpty()
sua = 1
break
if self.link[index].val is None:
break
pre = index
return sua
# Find an element at a position in a linear table
def getByIndex(self, ind):
if ind < 1 or ind >= self.size - 1:
return -1
index = self.link[self.size - 1].next
if index == 0:
return -1
for i in range(1, ind):
index = self.link[index].next
return self.link[index].val
# Find the location of elements in the linear table
def locateElement(self, ele):
index = self.link[self.size - 1].next
ind = -1
if index == 0:
return ind
for i in range(1, self.size - 1):
if self.link[index].val == ele:
ind = i
break
if self.link[index].val is None:
break
index = self.link[index].next
return ind
# Deletes the element at the specified position in the linear table
def deleteElement(self, ind):
sua = -1
# Front 1 Index
pre = self.size - 1
for i in range(1, self.size - 1):
index = self.link[pre].next
# The current position is an empty position
if self.link[index].val is None:
break
# Has been traversed to the i Position
if i == ind:
self.link[pre].next = self.link[index].next
self.link[index].val = None
# Delete the cursor of the element to point to the alternate linked list
self.link[index].next = self.link[0].next
# First element
self.link[0].next = index
sua = 1
break
pre = index
return sua
# Sort linear table traversal by linear table
def travelLink(self):
print("*" * 50)
index = self.link[self.size - 1].next
while self.link[index].val:
print(
f"value = {self.link[index].val} next = {self.link[index].next}"
)
index = self.link[index].next
print("*" * 50)
# Traverse by index
def traversingByIndex(self):
print("*" * 50)
for i in range(self.size):
print(
f"index = {i}, value = {self.link[i].val} next = {self.link[i].next}"
)
print("*" * 50)
if __name__ == '__main__':
ll = SLinkList()
ll.traversingByIndex()
print(ll.isEmpty())
print(ll.insert(1, 'A'))
ll.travelLink()
print(ll.insert(2, 'B'))
ll.travelLink()
print(ll.insert(1, 'C'))
print(ll.insert(4, 'D'))
ll.travelLink()
ll.traversingByIndex()
print(ll.deleteElement(3))
ll.traversingByIndex()
ll.travelLink()
print(ll.isEmpty())
print(ll.getByIndex(2))
print(ll.locateElement('BcA'))
print(ll.clearSLL())