1 |
|
2 |
|
3 |
|
4 | class linkedListNode {
|
5 | constructor(value, next = null) {
|
6 | this.value = value;
|
7 | this.next = next;
|
8 | }
|
9 |
|
10 | toString(callback) {
|
11 | return callback ? callback(this.value) : `${this.value}`;
|
12 | }
|
13 | }
|
14 |
|
15 |
|
16 |
|
17 |
|
18 | class LinkedList {
|
19 | constructor(comparatorFunction) {
|
20 | this.head = null;
|
21 | this.tail = null;
|
22 | this.equal =
|
23 | comparatorFunction ||
|
24 | function(a, b) {
|
25 | return a === b;
|
26 | };
|
27 | }
|
28 |
|
29 |
|
30 | prepend(value) {
|
31 | const node = new linkedListNode(value, this.head);
|
32 | this.head = node;
|
33 | if (!this.tail) {
|
34 | this.tail = node;
|
35 | }
|
36 | return this;
|
37 | }
|
38 |
|
39 |
|
40 | append(value) {
|
41 | const node = new linkedListNode(value);
|
42 | if (!this.head) {
|
43 | this.head = node;
|
44 | this.tail = node;
|
45 | }
|
46 | this.tail.next = node;
|
47 | this.tail = node;
|
48 |
|
49 | return this;
|
50 | }
|
51 |
|
52 |
|
53 | delete(value) {
|
54 | if (!this.head) {
|
55 | return null;
|
56 | }
|
57 |
|
58 | let deleteNode = null;
|
59 |
|
60 |
|
61 |
|
62 | while (this.head && this.equal(this.head.value, value)) {
|
63 | deleteNode = this.head;
|
64 | this.head = this.head.next;
|
65 | }
|
66 |
|
67 | let cur = this.head;
|
68 | if (cur !== null) {
|
69 |
|
70 | while (cur.next) {
|
71 | if (this.equal(cur.next.value, value)) {
|
72 | deleteNode = cur.next;
|
73 | cur.next = cur.next.next;
|
74 | } else {
|
75 | cur = cur.next;
|
76 | }
|
77 | }
|
78 | }
|
79 |
|
80 |
|
81 | if (this.equal(this.tail.value, value)) {
|
82 | thia.tail = cur;
|
83 | }
|
84 | }
|
85 |
|
86 |
|
87 | find({ value = undefined, callback = undefined }) {
|
88 | if (!this.head) {
|
89 | return null;
|
90 | }
|
91 |
|
92 | let cur = this.head;
|
93 | while (cur) {
|
94 | if (callback && callback(cur.value)) {
|
95 | return cur;
|
96 | }
|
97 | if (value != undefined && this.equal(cur.value, value)) {
|
98 | return cur;
|
99 | }
|
100 | cur = cur.next;
|
101 | }
|
102 |
|
103 | return null;
|
104 | }
|
105 |
|
106 |
|
107 | deleteTail() {
|
108 |
|
109 | const node = this.tail;
|
110 | if (this.head === this.tail) {
|
111 | this.head = null;
|
112 | this.tail = null;
|
113 | return node;
|
114 | }
|
115 |
|
116 | let cur = this.head;
|
117 | while (cur.next) {
|
118 | if (!cur.next.next) {
|
119 | cur.next = null;
|
120 | } else {
|
121 | cur = cur.next;
|
122 | }
|
123 | }
|
124 | this.tail = cur;
|
125 | return node;
|
126 | }
|
127 |
|
128 |
|
129 | deleteHead() {
|
130 | if (!this.head) {
|
131 | return null;
|
132 | }
|
133 |
|
134 | const node = this.head;
|
135 | if (this.head.next) {
|
136 | this.head = this.head.next;
|
137 | } else {
|
138 | this.head = null;
|
139 | this.tail = null;
|
140 | }
|
141 | return node;
|
142 | }
|
143 |
|
144 |
|
145 | fromArray(values) {
|
146 | values.forEach(value => this.append(value));
|
147 | }
|
148 |
|
149 |
|
150 | toArray(values) {
|
151 | const nodes = [];
|
152 | let cur = this.head;
|
153 | while (cur) {
|
154 | nodes.push(cur);
|
155 | cur = cur.next;
|
156 | }
|
157 | return nodes;
|
158 | }
|
159 |
|
160 |
|
161 | toString(callback) {
|
162 | return this.this
|
163 | .toArray()
|
164 | .map(node => node.toString(callback))
|
165 | .toString();
|
166 | }
|
167 |
|
168 |
|
169 | reverse() {
|
170 | let cur = this.head;
|
171 | let before = null;
|
172 | let after = null;
|
173 |
|
174 | while (cur) {
|
175 | after = cur.next;
|
176 | cur.next = before;
|
177 | before = cur;
|
178 | cur = after;
|
179 | }
|
180 | this.tail = this.head;
|
181 | this.head = before;
|
182 |
|
183 | return this;
|
184 | }
|
185 | }
|
186 |
|
187 | export default LinkedList;
|