/
linkedList.js
124 lines (106 loc) · 2.29 KB
/
linkedList.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
import ListNode from './listNode.js';
export default class LinkedList {
constructor() {
this._head = null;
this._size = 0;
}
push(val) {
const node = new ListNode(val);
if (this.isEmpty()) {
this._head = node;
} else {
let current = this._head;
while(current && current.next !== null) {
current = current.next;
}
current.next = node;
}
this._size++;
}
insert(val, index) {
if (!this._isSafeIndex(index, true)) {
return false;
}
const node = new ListNode(val);
let current = this._head;
if (index === 0) {
node.next = current;
this._head = node;
} else {
const prev = this.getNodeAt(index - 1);
current = prev.next;
prev.next = node;
node.next = current;
}
this._size++;
return true;
}
remove(val) {
const removeIndex = this.indexOf(val);
if (removeIndex >= 0) {
this.removeAt(removeIndex);
}
}
removeAt(index) {
if (!this._isSafeIndex(index)) {
return;
}
let current = this._head;
if (index === 0) {
this._head = current.next;
} else {
const prev = this.getNodeAt(index - 1);
current = prev.next;
prev.next = current.next;
}
this._size--;
}
getNodeAt(index) {
if (!this._isSafeIndex(index)) {
return null;
}
let current = this._head;
for (let i = 0; i < index && current !== null; i++) {
current = current.next;
}
return current;
}
getSize() {
return this._size;
}
getHead() {
return this._head;
}
isEmpty() {
return this._size === 0;
}
indexOf(val) {
let current = this._head;
for (let i = 0; i < this._size && current !== null; i++) {
if (current.val === val) {
return i;
}
current = current.next;
}
return -1;
}
toString() {
let str = '';
if (this.isEmpty()) {
return str;
}
let current = this._head;
str = `${current.val}`;
for (let i = 1; i < this._size && current != null; i++) {
current = current.next;
str += `,${current.val}`;
}
return str;
}
_isSafeIndex(index, needLast) {
const lastResult = needLast
? index <= this._size
: index < this._size;
return index >= 0 && lastResult;
}
}