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 ：
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 .
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
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