Dia 51/2019 - Estruturas de dados em JS: lista vinculada

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 51, mostrando o uso de listas.

Código

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
class Node {
constructor(element, next) {
this.element = element;
this.next = next;
}
}

class DoublyNode extends Node {
constructor(element, next, prev) {
super(element, next);
this.prev = prev;
}
}

const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
};

const defaultEquals = (a, b) => {
return a === b;
}

const defaultCompare = (a, b) => {
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
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
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.equalsFn = equalsFn;
this.count = 0;
this.head = undefined;
}

push(element) {
const node = new Node(element);
let current;
if (this.head == null) {
// catches null && undefined
this.head = node;
} else {
current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
this.count++;
}

getElementAt(index) {
if (index >= 0 && index <= this.count) {
let node = this.head;
for (let i = 0; i < index && node != null; i++) {
node = node.next;
}
return node;
}
return undefined;
}

insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
if (index === 0) {
const current = this.head;
node.next = current;
this.head = node;
} else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count++;
return true;
}
return false;
}

removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index === 0) {
this.head = current.next;
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}

remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}

indexOf(element) {
let current = this.head;
for (let i = 0; i < this.size() && current != null; i++) {
if (this.equalsFn(element, current.element)) {
return i;
}
current = current.next;
}
return -1;
}

isEmpty() {
return this.size() === 0;
}

size() {
return this.count;
}

getHead() {
return this.head;
}

clear() {
this.head = undefined;
this.count = 0;
}

toString() {
if (this.head == null) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current != null; i++) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
}
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
class CircularLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}

push(element) {
const node = new Node(element);
let current;
if (this.head == null) {
this.head = node;
} else {
current = this.getElementAt(this.size() - 1);
current.next = node;
}
// set node.next to head - to have circular list
node.next = this.head;
this.count++;
}

insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
let current = this.head;
if (index === 0) {
if (this.head == null) {
// if no node in list
this.head = node;
node.next = this.head;
} else {
node.next = current;
current = this.getElementAt(this.size());
// update last element
this.head = node;
current.next = this.head;
}
} else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count++;
return true;
}
return false;
}

removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index === 0) {
if (this.size() === 1) {
this.head = undefined;
} else {
const removed = this.head;
current = this.getElementAt(this.size() - 1);
this.head = this.head.next;
current.next = this.head;
current = removed;
}
} else {
// no need to update last element for circular list
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
}
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
class DoublyLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn);
this.tail = undefined;
}

push(element) {
const node = new DoublyNode(element);
if (this.head == null) {
this.head = node;
this.tail = node; // NEW
} else {
// attach to the tail node // NEW
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
this.count++;
}

insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new DoublyNode(element);
let current = this.head;
if (index === 0) {
if (this.head == null) { // NEW
this.head = node;
this.tail = node; // NEW
} else {
node.next = this.head;
this.head.prev = node; // NEW
this.head = node;
}
} else if (index === this.count) { // last item NEW
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
node.next = current;
previous.next = node;
current.prev = node; // NEW
node.prev = previous; // NEW
}
this.count++;
return true;
}
return false;
}

removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index === 0) {
this.head = this.head.next;
// if there is only one item, then we update tail as well //NEW
if (this.count === 1) {
// {2}
this.tail = undefined;
} else {
this.head.prev = undefined;
}
} else if (index === this.count - 1) {
// last item //NEW
current = this.tail;
this.tail = current.prev;
this.tail.next = undefined;
} else {
current = this.getElementAt(index);
const previous = current.prev;
// link previous with current's next - skip it to remove
previous.next = current.next;
current.next.prev = previous; // NEW
}
this.count--;
return current.element;
}
return undefined;
}

indexOf(element) {
let current = this.head;
let index = 0;
while (current != null) {
if (this.equalsFn(element, current.element)) {
return index;
}
index++;
current = current.next;
}
return -1;
}

getHead() {
return this.head;
}

getTail() {
return this.tail;
}

clear() {
super.clear();
this.tail = undefined;
}

toString() {
if (this.head == null) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
while (current != null) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}

inverseToString() {
if (this.tail == null) {
return '';
}
let objString = `${this.tail.element}`;
let previous = this.tail.prev;
while (previous != null) {
objString = `${objString},${previous.element}`;
previous = previous.prev;
}
return objString;
}
}
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
class SortedLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
super(equalsFn);
this.equalsFn = equalsFn;
this.compareFn = compareFn;
}

push(element) {
if (this.isEmpty()) {
super.push(element);
} else {
const index = this.getIndexNextSortedElement(element);
super.insert(element, index);
}
}

insert(element, index = 0) {
if (this.isEmpty()) {
return super.insert(element, index === 0 ? index : 0);
}
const pos = this.getIndexNextSortedElement(element);
return super.insert(element, pos);
}

getIndexNextSortedElement(element) {
let current = this.head;
let i = 0;
for (; i < this.size() && current; i++) {
const comp = this.compareFn(element, current.element);
if (comp === Compare.LESS_THAN) {
return i;
}
current = current.next;
}
return i;
}
}
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
class StackLinkedList {
constructor() {
this.items = new DoublyLinkedList();
}

push(element) {
this.items.push(element);
}

pop() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items.removeAt(this.size() - 1);
return result;
}

peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items.getElementAt(this.size() - 1).element;
}

isEmpty() {
return this.items.isEmpty();
}

size() {
return this.items.size();
}

clear() {
this.items.clear();
}

toString() {
return this.items.toString();
}
}
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
/*
* Singly
***********************************/
const list = new LinkedList();

list.push(13);
console.log(list.indexOf(13));
// 0
list.push(10);
console.log(list.toString());
// 13,10
console.log(list.indexOf(10));
// 1
list.push(11);
list.push(19);
console.log(list.toString());
// 13,10,11,19
list.removeAt(1);
console.log(list.toString());
// 13,11,19
list.insert(20, 0);
list.insert(21, 1);
console.log(list.toString());
// 20,21,13,11,19
list.remove(20);
console.log(list.toString());
// 21,13,11,19

/*
* Doubly
***********************************/
const list2 = new DoublyLinkedList();

list2.push(5);
console.log(list2.toString());
// 5
list2.push(9);
list2.push(10);
list2.removeAt(0);
console.log(list2.toString());
// 9,10
list2.insert(8, 0);
list2.insert(11, 3);
console.log(list2.toString());
// 8,9,10,11
list2.removeAt(list2.size() - 1);
console.log(list2.toString());
// 8,9,10

/*
* Circular
***********************************/
const list3 = new CircularLinkedList();

list3.push(20);
console.log(list3.toString());
// 20
list3.insert(15, 0);
list3.insert(15.5, 1);
console.log(list3.toString());
// 15,15.5,20
list3.removeAt(0);
list3.removeAt(1);
console.log(list3.toString());
// 15.5

/*
* Sorted
***********************************/
const list4 = new SortedLinkedList();

for (let i = 5; i > 0; i--) {
list4.push(i);
}

console.log(list4.toString());
// 1,2,3,4,5

list4.removeAt(1);
list4.remove(5)

console.log(list4.toString());
// 1,3,4

// SortedLinkedList with custom sorting function
class Example {
constructor(item1, item2) {
this.item1 = item1;
this.item2 = item2;
}
toString() {
return `${this.item1.toString()}|${this.item2.toString()}`;
}
}

const exampleCompare = (a, b) => a.toString().localeCompare(b.toString());
const sll = new SortedLinkedList(defaultEquals, exampleCompare);

sll.push(new Example(4, 5));
sll.push(new Example(1, 2));
console.log(sll.toString());
// 1|2,4|5
sll.insert(new Example(0, 0), 3);
console.log(sll.toString());
// 0|0,1|2,4|5

/*
* Stack
***********************************/
const list5 = new StackLinkedList();

console.log(list5.isEmpty());
// true
list5.push(5);
list5.push(10);
console.log(list5.toString());
// 5,10
console.log(list5.peek());
// 10
list5.push(15);
list5.pop();
console.log(list5.size());
// 2

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.