Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
class NodoLista:
"""Esta classe representa um nodo de uma lista encadeada."""
def __init__(self, dado=0, proximo_nodo=None, anterior_nodo = None):
self.dado = dado
self.proximo = proximo_nodo
self.anterior = anterior_nodo
class ListaEncadeada():
"""Esta classe representa uma lista encadeada."""
def __init__(self):
self.cabeca = None
def __repr__(self):
return "[" + str(self.cabeca) + "]"
def print_lista(self):
corrente = self.cabeca
print("[ " , end="")
while corrente.proximo != None:
print( str(corrente.dado), "-> <- ", end="")
corrente = corrente.proximo
print(corrente.dado,"]\n")
def insere_no_inicio(lista, novo_dado):
if lista.cabeca == None:
novo_nodo = NodoLista(novo_dado)
novo_nodo.proximo = None
novo_nodo.anterior = None
lista.cabeca = novo_nodo
else:
novo_nodo = NodoLista(novo_dado)
first = lista.cabeca
novo_nodo.proximo = first
novo_nodo.anterior = None
first.anterior = novo_nodo
lista.cabeca = novo_nodo
def swap(lista, valor1, valor2):
a = busca(lista,valor1)
b = busca(lista,valor2)
if id(a) < id(b):
temp = a
a = b
b = temp
if a.anterior == None and a.proximo == b: #juntos no comeco
lista.cabeca = b
a.proximo = b.proximo
a.anterior = b
b.anterior = None
b.proximo = a
elif b.proximo == None: #juntos no final
b.anterior = a.anterior
b.proximo = a
a.anterior.proximo = b
a.anterior = b
a.proximo = None
elif a.anterior != None and b.proximo != None and a.proximo == b and b.anterior == a: #juntos no meio
a.anterior.proximo = b
b.proximo.anterior = a
b.anterior = a.anterior
a.proximo = b.proximo
a.anterior = b
b.proximo = a
elif a.anterior == None and b.proximo != None and a.proximo == b and b.anterior == a: # cabeca e meio
lista.cabeca = b
a.proximo.anterior = b
aux = a.proximo
a.proximo = b.proximo
a.anterior = b.anterior
b.anterior.proximo = a
b.proximo.anterior = a
b.proximo = aux
b.anterior = None
elif a == b:
print("Posicoes iguais, ou seja, o mesmo node")
def busca(lista, valor):
corrente = lista.cabeca
while corrente and corrente.dado != valor:
corrente = corrente.proximo
return corrente
items = [10,9,8,7,6,5,4,3,2,1]
lista = ListaEncadeada()
for i in items:
insere_no_inicio(lista, i)
print("Lista Original:")
lista.print_lista()
print("juntos no comeco", 1, 2)
swap(lista,2,1)
lista.print_lista()
print("juntos no final", 9, 10)
swap(lista,10,9)
lista.print_lista()
print("juntos no meio", 5, 6)
swap(lista,6,5)
lista.print_lista()
print("comeco e meio", 2, 5)
swap(lista,2,5)
lista.print_lista()