The idea and implementation of linked list (Python)

Linked list

1. The concept of linked list

​ The structure of the linked list is like the chain seen in daily life , It's a ring over ring structure . In the linked list of data structure , Each ring consists of “ Data fields ” and “ Pointer to the domain ” Two parts make up . The specific structure is shown in the following figure :

 Insert picture description here

​ As shown in the figure, it is the structure of the linked list , Data fields The user stores the element information of the current node , Pointer to the domain Used to link the next node , It should be noted that the linked list is out of order , That is, we just need to maintain the relative position between the elements , There is no need to maintain this location information in a continuous memory space .

2. Creation of linked list

​ The creation of linked list is the same as its principle , We need to initialize each node , Nodes contain data fields data And pointer fields next, After having nodes, we also need to formulate the pointing function of nodes so that nodes can be linked , The specific implementation method is as follows :

class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
# Gets the value of the node 
def getData(self):
return self.data
# Get the next node address 
def getNext(self):
return self.next
# Set the value of the node 
def setData(self, newData):
self.data = newData
# Set node pointing 
def setNext(self, newnext):
self.next = newnext

​ The test results are as follows :

# Set the data field of the node 
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)
# Set the position pointed by the node pointer 
temp1.next = temp2
temp2.next = temp3
temp1.setNext(temp3)
# Get the value of the node 
temp2.getNext().getData()
# Output 
95

3. The realization of linked list function

​ For a linked list , In addition to creating linked lists , We also need to create a class to realize the function of linked list .

  • printlink: Realize the printing of linked list ;
  • length: Realize the calculation of the length of the linked list ;
  • search: Realize the search of elements in the linked list ;
  • remove: Realize the removal of elements in the linked list .

​ The specific implementation is as follows :

class UnorderedList:
# No elements build an empty list 
def __init__(self):
self.head = None
# Determine whether the list is empty 
def isEmpty(self):
return self.head == None
# Add a node 
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
# Traversing the linked list 
def printlink(self):
if self.head == None:
print(" The linked list is empty !")
p = self.head
while p != None:
print(p.getData(), end="->")
p = p.getNext()
# The length of the list 
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
# Look for the element 
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
# Remove elements 
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())

​ The test results are as follows :

# Set the data field of the node 
temp1 = Node(93)
temp2 = Node(94)
temp3 = Node(95)
# Set the position pointed by the node pointer 
linklist = UnorderedList()
linklist.head = temp1
temp1.next = temp2
temp2.next = temp3
# Use... In the function class add Add elements 
linklist.add(9)
# Print the length of the linked list 
print(linklist.length())
# Output 
4

​ Use a loop to construct a linked list :

link_list = UnorderedList()
for i in range(5):
link_list.add(i)
node = link_list.head
node.getData()
# Output 
4
Please bring the original link to reprint ,thank
Similar articles