-
Notifications
You must be signed in to change notification settings - Fork 35
/
84.js
156 lines (134 loc) · 4.22 KB
/
84.js
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
class LinkedListAlt {
constructor(value) {
this.head = {
value: value,
next: null
}
this.tail = this.head; // ultimo nodo que apunta a null
this.size = 1;
}
append(value) {
const newNode = {
value: value,
next: null
}
// apuntamos a tail al nuevo nodo
this.tail.next = newNode;
// convertimos al nuevo nodo en el nuevo tail
this.tail = newNode;
// aumentamos la cantidad total de items
this.size++;
return this;
}
// agregar al principio del linkedlist
prepend(value) {
const newNode = {
value: value,
next: null
}
// el nuevo nodo apuntará a head
newNode.next = this.head;
// reasignamos head
this.head = newNode;
this.size++;
return this;
}
printList() {
const array = [];
let current = this.head;
while (current) {
array.push(current.value);
current = current.next;
}
return array;
}
// insertar item en un index especifico
insert(value, index) {
// revisamos que el indice sea valido
if (index < 0 || index > this.size) return null;
const newNode = {
value: value,
next: null
}
let current = this.head;
let previous;
// Si se quiere agregar el nuevo nodo a la cabeza
if (index === 0) {
// apuntamos el head del nuevo nodo al viejo nodo en head
newNode.next = current;
this.head = newNode;
}
else {
// iteramos hasta el indice
for (let i = 0; i < index; i++) {
// guardamos el nodo anterior
previous = current;
// iteramos al siguiente elemento
current = current.next;
}
// al encontrar el indice, apuntamos el nodo anterior al nuevo nodo
previous.next = newNode;
// apuntamos el nuevo nodo al nodo siguiente del actual
newNode.next = current;
}
this.size++;
return this;
}
reverse() {
// si solo esta el head apuntando a null
if (!this.head.next) {
return this.head; // devolvemos el head
}
// guardamos el primer elemento
let first = this.head;
// tail se vuelve la cabeza ya que ahora irá al final
this.tail = this.head;
// guardamos el segundo elemento
let second = first.next; // es el siguiente de head
// mientras second no sea null
while (second) {
// guardamos el siguiente de second (el tercero)
let next = second.next;
// le asignamos el valor de first a second
second.next = first;
// actualizamos first y second
first = second;
second = next;
}
// apuntamos al viejo head a null
this.head.next = null;
// ahora head es el que era el tail
this.head = first;
}
// eliminar basado en el indice y no en su valor
removeFrom (index) {
// chequear que el param es correcto
if (index < 0 || index > this.size) return null;
let current = this.head;
let previous;
// si se quiere eliminar el primer valor de la lista (head)
if (index === 0) {
// asignamos una nueva head
this.head = current.next;
}
else {
// recorremos hasta el index
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
// le asignamos al que quedo en previus el siguiente del actual
previous.next = current.next;
}
this.size--; // la lista disminuira su tamaño
return current.value; // devuelve lo eliminado
}
}
const newLinked = new LinkedListAlt(1); [1]
newLinked.append(2); [1,2]
newLinked.append(3); [1,2,3]
newLinked.prepend(0); [0,1,2,3]
newLinked.insert(4, 1); [0,4,1,2,3]
console.log(newLinked.printList());
newLinked.reverse();
console.log(newLinked.printList());