Explication détaillée de l'utilisation des définitions de listes chaînées des structures de données et des algorithmes Python

Cet article présente principalement la définition et l'utilisation des listes chaînées dans les structures de données et les algorithmes Python. Il analyse en détail les définitions, les méthodes d'utilisation et les précautions associées des listes chaînées simples, des listes chaînées circulaires, etc. dans le besoin peuvent se référer à Suivant

Les exemples de cet article décrivent la définition et l'utilisation de listes chaînées dans les structures de données et les algorithmes Python. Partagez-le avec tout le monde pour votre référence, comme suit :

Cet article vous expliquera :

(1) À partir de la définition des nœuds de liste chaînée, utilisez des méthodes de classe et des idées orientées objet pour créer des listes chaînées Conception

(2) Conditions aux limites qui doivent être prises en compte lors de l'implémentation de fonctions membres telles que l'insertion et la suppression de classes de listes chaînées,
prepend (insertion de tête), pop (suppression de tête), append (insertion de queue), pop_last (suppression de queue)

2.1 Insertion :

Liste chaînée vide
La longueur de la liste chaînée est de 1
Insérer jusqu'à la fin

2.2 Supprimer

Liste chaînée vide
La longueur de la liste chaînée est 1
Supprimer l'élément de fin

(3) De nombreuses variantes de la liste à chaînage unique à la liste à chaînage unique :

Liste à chaînage unique avec nœud de queue
Liste à chaînage unique cyclique
Liste à chaînage double

1. Définition des nœuds de liste chaînée

class LNode:
 def __init__(self, elem, next_=None):
  self.elem = elem
  self.next = next_

2. Mise en œuvre d'une liste chaînée unique

Concentrez-vous sur la compréhension de la mise en œuvre. d'insertion et de suppression et les conditions aux limites qui doivent être prises en compte :

class LinkedListUnderflow(ValueError):
 pass
class LList:
 def __init__(self):
  self._head = None
 def is_empty(self):
  return self._head is None
 def prepend(self, elem):
  self._head = LNode(elem, self._head)
 def pop(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop')
  e = self._head.elem
  self._head = self._head.next
  return e
 def append(self, elem):
  if self._head is None:
   self._head = LNode(elem)
   return
  p = self._head
  while p.next is not None:
   p = p.next
  p.next = LNode(elem)
 def pop_last(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop_last')
  p = self._head
  if p.next is None:
   e = p.elem
   self._head = None
   return e
  while p.next.next is not None:
   p = p.next
  e = p.next.elem
  p.next = None
  return e

Résumé simple :

(0) La condition préalable pour pouvoir accéder à p.next.next est que p.next ne soit pas vide
(1) Insertion de la queue, Si la liste chaînée n'est pas vide, il suffit de changer le pointeur de la queue ; node;
(2) Suppression de la queue, si la longueur de la liste chaînée n'est pas vide, il suffit de changer le pointeur de l'avant-dernier nœud.

Variation simple d'une liste à chaînage unique : liste à chaînage unique avec nœud de queue

class LList1(LList):
 def __init__(self):
  LList.__init__(self)
  self._rear = None
 ...

Tout ce que nous devons réécrire est : Insertion de tête, insertion de queue, suppression de queue

def prepend(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._head = LNode(elem, self._head)
def append(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._rear.next = LNode(elem)
  self._rear = self._rear.next
def pop_last(self):
 if self._head is None:
  raise LinkedListUnderflow('in pop_last')
 p = self._head
 if p.next is None:
  e = p.elem
  self._head = None
  return e
 while p.next.next is not None:
  p = p.next
 e = p.next.elem
 self._rear = p
 p.next = None
 return e

Variation de liste chaînée simple : liste chaînée simple cyclique

class LCList:
 def __init__(self):
  self._rear = None
 def prepend(self, elem):
  if self._rear is None:
   self._rear = LNode(elem)
   self._rear.next = self._rear
  else:
   self._rear.next = LNode(elem, self._rear.next)
 def append(self, elem):
  self.prepend(elem)
  self_rear = self._rear.next
 def pop(self):
  if self._rear is None:
   raise LinkedListUnderflow('in pop')
  p = self._rear.next
  if p is None:
   self._rear = None
  else:
   self._rear.next = p.next
  return p.elem
 def printall(self):
  if self._rear is None:
   raise ...
  p = self._rear.next
  while True:
   print(p.elem)
   if p is self._rear:
    break
   p = p.next

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!