fork 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):
  17.         self.value = value
  18.         self.next = next
  19.  
  20.     def __str__(self):
  21.         return "{0} : ({1}, {2})".format(printAddr(self),
  22.           self.value, printAddr(self.next) )
  23.  
  24. class SimpLinkedList:
  25.     def __init__(self):
  26.         self.head = None
  27.  
  28.     def __str__(self):
  29.         cn = self.head
  30.         r = "["
  31.         while cn :
  32.             r = "[" if cn == self.head else r + ", "
  33.             r = "{0}{1}".format(r, str(cn.value))
  34.             cn = cn.next
  35.         return r + "]"
  36.  
  37.     def __len__(self) :
  38.         if self.isEmpty() : return 0
  39.  
  40.         p = self.head
  41.         c = 0
  42.         while p :
  43.             c += 1
  44.             p = p.next
  45.  
  46.         return c
  47.  
  48.     #Insere no inicio da Lista
  49.     def insert(self, value):
  50.         newNode = Node(value, self.head)
  51.         self.head = newNode
  52.         return newNode
  53.  
  54.     #Remove um nó baseado no valor
  55.     def remove(self, val):
  56.         if self.isEmpty() : return False
  57.  
  58.         ant = None
  59.         p = self.head
  60.  
  61.         #Procura por val e o nó anterior
  62.         while p and p.value != val :
  63.             ant = p
  64.             p = p.next
  65.  
  66.         #Verifica se achou o valor. Caso não achou retorna falso
  67.         if not p : return False
  68.  
  69.         #Liberação de p para remoção
  70.         #Se ant e None então passa a ref de p para head
  71.         if not ant :
  72.             self.head = p.next
  73.         else: # Senao remove a referencia de p do ant
  74.             ant.next = p.next
  75.  
  76.         del p
  77.         return True
  78.  
  79.     #Limpa todos os elementos da lista
  80.     def clear(self) :
  81.         p = self.head
  82.         self.head = None
  83.         t = None
  84.         while p :
  85.             t = p.next
  86.             del p
  87.             p = t
  88.  
  89.     #Verifica se a lista está vazia
  90.     def isEmpty(self) : return self.head == None
  91.  
  92.     def debug(self) :
  93.         cn = self.head
  94.         r = "["
  95.         while cn :
  96.             r = "[" if cn == self.head else r + ", "
  97.             r = "{0}{1}({2}, {3})".format(r, str(cn.value), printAddr(cn),
  98.                 printAddr(cn.next))
  99.             cn = cn.next
  100.         return r + "]"
  101. # Fim classe
  102.  
  103. #Exemplos de uso
  104. print("Node addr:", str(id(None))[10:])
  105. print("Criação nós:")
  106. n1 = Node(10, None)
  107. print(n1)
  108. n2 = Node(20, n1)
  109. print(n2)
  110.  
  111. print("\nCriação lista:")
  112. ll = SimpLinkedList()
  113.  
  114. print("Inserindo no início")
  115. ll.insert(11)
  116. ll.insert(30)
  117. print(ll, len(ll), ll.isEmpty())
  118. print(ll.debug())
  119.  
  120. print("Removeu" if ll.remove(55) else "Não Removeu")
  121. print("Remoção:", ll)
  122. ll.clear()
  123. print(ll, ll.isEmpty(), len(ll))
  124.  
Success #stdin #stdout 0.02s 27696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Node addr: 2320
Criação nós:
35176 : (10, None)
35288 : (20, 35176)

Criação lista:
Inserindo no início
[30, 11] 2 False
[30(35624, 35568), 11(35568, None)]
Não Removeu
Remoção: [30, 11]
[] True 0
https://ideone.com/QUqMG8
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!