The idea and implementation of linked list (Python)

idea implementation 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
版权声明
本文为[The second brother is not like a programmer]所创,转载请带上原文链接,感谢
https://javamana.com/2021/10/20211002150018483z.html

  1. Hadoop Foundation - 03 - hdfs (Hadoop Distributed File System) Basic Concepts
  2. Hadoop Foundation - 05 - hdfs Project (word Frequency Statistics)
  3. Hadoop Foundation - 06 - hdfs Data Read and write
  4. The "monthly test" report card of the new car built under the lack of core: Xiaopeng and Weilai took the lead in "breaking 10000", and the ideal plummeted by 25%
  5. Introduction to making arch linux software package
  6. Hard core observation 407 HTTPS everywhere browser extension is about to retire
  7. How to use busybox on Linux
  8. In 2021, the talent incentive plan of Linux foundation open source software School Park was officially launched
  9. It's not windows or Linux. Shrink is the "God operating system"
  10. Install anydesk on Ubuntu Linux
  11. 2021, can we recommend using Linux to play games?
  12. not exist:org.springframework.kafka.listener.AbstractMessageListenerContaingetContainerProperties()
  13. Are you sure HTTPS is asymmetric encryption for content encryption? See the answers and reasons
  14. MySQL online slow log query
  15. Java JDK server installation
  16. 手把手教你使用Java开发在线生成pdf文档
  17. Questions d'entrevue dans la base de données MySQL (dernière version 2021)
  18. Java零基础小白入门必做题汇总(建议收藏)第一篇
  19. Day15 Java Foundation
  20. Day16 Java Foundation
  21. Day17 Java Foundation
  22. Day18 Java Foundation
  23. Linux installe JDK 1.8 et configure les variables d'environnement
  24. Tutoriel d'utilisation Maven super détaillé
  25. Spring boot reads project parameter configuration
  26. Docker installing rocketmq
  27. Java Zero Basic small white Beginner must make a summary of issues (recommended Collection) Chapitre 1
  28. Manuel pour vous apprendre à utiliser le développement Java pour générer des documents PDF en ligne
  29. 40 + comment les femmes s'habillent - elles pour montrer leur jeunesse?Un manteau et une jupe vous donnent un look haut de gamme tout au long de l'automne et de l'hiver
  30. Tutoriel d'installation Ubuntu 16.04 / Hadoop 3.1.3Configuration autonome / pseudo - distribuée
  31. L'apprentissage le plus détaillé de springboot à l'échelle du réseau - day01
  32. L'apprentissage le plus détaillé de springboot sur le Web - day02
  33. L'apprentissage le plus détaillé de springboot sur le Web - day03
  34. L'apprentissage le plus détaillé de springboot sur le Web - day04
  35. Tutoriel d'utilisation Maven super détaillé
  36. L'apprentissage le plus détaillé de springboot sur le Web - day05
  37. L'apprentissage le plus détaillé de springboot sur le Web - day06
  38. L'apprentissage le plus détaillé de springboot sur le Web - day07
  39. Introduction to JavaScript - write a photo album for your girlfriend
  40. [Hadoop 3. X] HDFS storage type and storage strategy (V) overview
  41. L'apprentissage le plus détaillé de springboot sur le Web - day08
  42. Introduction à la page Web de rabbitmq (3)
  43. No Converter found for return value of type: class java.util.arraylist Error Problem
  44. (16) , spring cloud stream message driven
  45. Que faut - il apprendre de l'architecture des microservices Spring Cloud?
  46. Résolution: erreur: Java: distribution cible invalide: 11problème d'erreur
  47. Springboot démarre en une minute et sort de l'enfer de la configuration SSM!
  48. Maven - un outil de gestion essentiel pour les grands projets d'usine, de l'introduction à la maîtrise![️ Collection recommandée]
  49. ️ Push to interview in Large Factory ᥧ - - Spring Boot Automatic Assembly Principle
  50. [️ springboot Template Engine] - thymeleaf
  51. Springboot - MVC Automatic configuration Principle
  52. Mybatis reverse engineering and the use of new version mybatisplus 3.4 reverse engineering
  53. Base de données MySQL - transactions et index
  54. Sécurité du printemps - [authentification, autorisation, déconnexion et contrôle des droits]
  55. Moteur de base de données InnoDB diffère de myisam
  56. Swagger - [springboot Integrated Swagger, configure Swagger, configure scan Interface, configure API Group]
  57. Cadre de sécurité Shiro - [QUICKstart, login Block, User Authentication, request Authorization]
  58. [Introduction à Java] installation de l'environnement de développement - Introduction à Java et construction de l'environnement
  59. 【 linux】 notes d'utilisation tmux
  60. MySQL + mybatis paging query - database series learning notes