fork(2) download
copy 
  1. # -*- coding: utf-8 -*-
  2. # Usado conceito de classe para representar a implementação da lista encadeada simples.
  3.  
  4. # O nó é implementado pela classe Node
  5.  
  6. #Função para imprimir endereço de memoria da variável
  7. def printAddr(v):
  8.     if v is None :
  9.         return "None"
  10.     else:
  11.         s = str(id(v))
  12.         cropS = len(s)-5
  13.         return s[cropS:]
  14.  
  15. class Node:
  16.     def __init__(self, value, next=None, prior=None):
  17.         self.value = value
  18.         self.next = next
  19.         self.prior = prior
  20.  
  21.     def __str__(self):
  22.         return "{0} : ({1}, {2}, {3})".format(printAddr(self),
  23.           self.value, printAddr(self.next), printAddr(self.prior) )
  24.  
  25. class DoubleLinkedList:
  26.     def __init__(self):
  27.         self.head = None
  28.  
  29.     def __str__(self):
  30.         cn = self.head
  31.         r = "["
  32.         while cn :
  33.             r = "[" if cn == self.head else r + ", "
  34.             r = "{0}{1}".format(r, str(cn.value))
  35.             cn = cn.next
  36.         return r + "]"
  37.  
  38.     def __len__(self) :
  39.         if self.isEmpty() : return 0
  40.  
  41.         p = self.head
  42.         c = 0
  43.         while p :
  44.             c += 1
  45.             p = p.next
  46.  
  47.         return c
  48.  
  49.     #Busca um elemento na lista e retorna o nó encontrado
  50.     def find(self, v):
  51.         if self.isEmpty() : return None
  52.  
  53.         p = self.head
  54.         while p :
  55.             if p.value == v :
  56.                 return p
  57.             p = p.next
  58.  
  59.         return None
  60.  
  61.     #Insere no inicio da Lista
  62.     def insert(self, value):
  63.         newNode = Node(value, self.head)
  64.         if not self.isEmpty() :
  65.             self.head.prior = newNode
  66.         self.head = newNode
  67.         return newNode
  68.  
  69.     #Remove um nó baseado no valor
  70.     def remove(self, val):
  71.         #Busca pelo nó p na lista
  72.         p = self.find(val)
  73.         if not p : return False
  74.  
  75.         #Caso p seja o primeiro, atualiza head com o próximo dele
  76.         if self.head == p :
  77.             self.head = p.next
  78.         else: # Neste caso atualiza o próximo no anterior de p para o próximo de p
  79.             p.prior.next = p.next
  80.  
  81.         #Caso p tenha próximo, atualiza o anterior do próximo de p com o anterior de p
  82.         if p.next : p.next.prior = p.prior
  83.  
  84.         del p #Remove p da memória
  85.         return True
  86.  
  87.     #Limpa todos os elementos da lista
  88.     def clear(self) :
  89.         p = self.head
  90.         self.head = None
  91.         t = None
  92.         while p :
  93.             t = p.next
  94.             del p
  95.             p = t
  96.  
  97.     #Verifica se a lista está vazia
  98.     def isEmpty(self) : return self.head == None
  99.  
  100.     #Retorna representação em string da lista com as informação sobre apontamentos
  101.     def debug(self) :
  102.         cn = self.head
  103.         r = "["
  104.         while cn :
  105.             r = "[" if cn == self.head else r + ", "
  106.             r = "{0}{1}({2}, {3}, {4})".format(r, str(cn.value), printAddr(cn),
  107.                 printAddr(cn.next), printAddr(cn.prior))
  108.             cn = cn.next
  109.         return r + "]"
  110. # Fim classe
  111.  
  112. #Exemplos de uso
  113. print("Node addr:", str(id(None))[10:])
  114. print("Criação nós:")
  115. n1 = Node(10, None)
  116. print(n1)
  117. n2 = Node(20, n1)
  118. print(n2)
  119.  
  120. print("\nCriação lista:")
  121. ll = DoubleLinkedList()
  122.  
  123. print("Inserindo no início")
  124. ll.insert(10)
  125. ll.insert(20)
  126. ll.insert(30)
  127. print(ll, len(ll), ll.isEmpty())
  128. print(ll.debug())
  129. print(ll.find(20))
  130.  
  131. print("Remove 55:", "Removeu" if ll.remove(55) else "Não Removeu")
  132. print(ll.debug())
  133. print("Remove 20:", "Removeu" if ll.remove(20) else "Não Removeu")
  134. print(ll.debug())
  135. print("Remove 10:", "Removeu" if ll.remove(10) else "Não Removeu")
  136. print(ll.debug())
  137. print("Remove 30:", "Removeu" if ll.remove(30) else "Não Removeu")
  138. print(ll.debug())
  139.  
  140. ll.insert(10)
  141. ll.insert(20)
  142. ll.insert(30)
  143. print(ll.debug())
  144. ll.clear()
  145. print(ll, ll.isEmpty(), len(ll))
Success #stdin #stdout 0.01s 27712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Node addr: 2272
Criação nós:
86024 : (10, None, None)
86080 : (20, 86024, None)

Criação lista:
Inserindo no início
[30, 20, 10] 3 False
[30(86416, 86360, None), 20(86360, 86304, 86416), 10(86304, None, 86360)]
86360 : (20, 86304, 86416)
Remove 55: Não Removeu
[30(86416, 86360, None), 20(86360, 86304, 86416), 10(86304, None, 86360)]
Remove 20: Removeu
[30(86416, 86304, None), 10(86304, None, 86416)]
Remove 10: Removeu
[30(86416, None, None)]
Remove 30: Removeu
[]
[30(86584, 86360, None), 20(86360, 86416, 86584), 10(86416, None, 86360)]
[] True 0
https://ideone.com/Vbv4sg
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!