1 | import { IIterable, IIterator, IRetroable, IterableOrArrayLike } from '@phosphor/algorithm';
|
2 |
|
3 |
|
4 |
|
5 | export declare class LinkedList<T> implements IIterable<T>, IRetroable<T> {
|
6 | |
7 |
|
8 |
|
9 | constructor();
|
10 | /**
|
11 | * Whether the list is empty.
|
12 | *
|
13 | * #### Complexity
|
14 | * Constant.
|
15 | */
|
16 | readonly isEmpty: boolean;
|
17 | /**
|
18 | * The size of the list.
|
19 | *
|
20 | * #### Complexity
|
21 | * `O(1)`
|
22 | *
|
23 | * #### Notes
|
24 | * This is equivalent to `length`.
|
25 | */
|
26 | readonly size: number;
|
27 | /**
|
28 | * The length of the list.
|
29 | *
|
30 | * #### Complexity
|
31 | * Constant.
|
32 | *
|
33 | * #### Notes
|
34 | * This is equivalent to `size`.
|
35 | *
|
36 | * This property is deprecated.
|
37 | */
|
38 | readonly length: number;
|
39 | /**
|
40 | * The first value in the list.
|
41 | *
|
42 | * This is `undefined` if the list is empty.
|
43 | *
|
44 | * #### Complexity
|
45 | * Constant.
|
46 | */
|
47 | readonly first: T | undefined;
|
48 | /**
|
49 | * The last value in the list.
|
50 | *
|
51 | * This is `undefined` if the list is empty.
|
52 | *
|
53 | * #### Complexity
|
54 | * Constant.
|
55 | */
|
56 | readonly last: T | undefined;
|
57 | /**
|
58 | * The first node in the list.
|
59 | *
|
60 | * This is `null` if the list is empty.
|
61 | *
|
62 | * #### Complexity
|
63 | * Constant.
|
64 | */
|
65 | readonly firstNode: LinkedList.INode<T> | null;
|
66 | /**
|
67 | * The last node in the list.
|
68 | *
|
69 | * This is `null` if the list is empty.
|
70 | *
|
71 | * #### Complexity
|
72 | * Constant.
|
73 | */
|
74 | readonly lastNode: LinkedList.INode<T> | null;
|
75 | /**
|
76 | * Create an iterator over the values in the list.
|
77 | *
|
78 | * @returns A new iterator starting with the first value.
|
79 | *
|
80 | * #### Complexity
|
81 | * Constant.
|
82 | */
|
83 | iter(): IIterator<T>;
|
84 | /**
|
85 | * Create a reverse iterator over the values in the list.
|
86 | *
|
87 | * @returns A new iterator starting with the last value.
|
88 | *
|
89 | * #### Complexity
|
90 | * Constant.
|
91 | */
|
92 | retro(): IIterator<T>;
|
93 | /**
|
94 | * Create an iterator over the nodes in the list.
|
95 | *
|
96 | * @returns A new iterator starting with the first node.
|
97 | *
|
98 | * #### Complexity
|
99 | * Constant.
|
100 | */
|
101 | nodes(): IIterator<LinkedList.INode<T>>;
|
102 | /**
|
103 | * Create a reverse iterator over the nodes in the list.
|
104 | *
|
105 | * @returns A new iterator starting with the last node.
|
106 | *
|
107 | * #### Complexity
|
108 | * Constant.
|
109 | */
|
110 | retroNodes(): IIterator<LinkedList.INode<T>>;
|
111 | /**
|
112 | * Assign new values to the list, replacing all current values.
|
113 | *
|
114 | * @param values - The values to assign to the list.
|
115 | *
|
116 | * #### Complexity
|
117 | * Linear.
|
118 | */
|
119 | assign(values: IterableOrArrayLike<T>): void;
|
120 | /**
|
121 | * Add a value to the end of the list.
|
122 | *
|
123 | * @param value - The value to add to the end of the list.
|
124 | *
|
125 | * #### Complexity
|
126 | * Constant.
|
127 | *
|
128 | * #### Notes
|
129 | * This is equivalent to `addLast`.
|
130 | */
|
131 | push(value: T): void;
|
132 | /**
|
133 | * Remove and return the value at the end of the list.
|
134 | *
|
135 | * @returns The removed value, or `undefined` if the list is empty.
|
136 | *
|
137 | * #### Complexity
|
138 | * Constant.
|
139 | *
|
140 | * #### Notes
|
141 | * This is equivalent to `removeLast`.
|
142 | */
|
143 | pop(): T | undefined;
|
144 | /**
|
145 | * Add a value to the beginning of the list.
|
146 | *
|
147 | * @param value - The value to add to the beginning of the list.
|
148 | *
|
149 | * #### Complexity
|
150 | * Constant.
|
151 | *
|
152 | * #### Notes
|
153 | * This is equivalent to `addFirst`.
|
154 | */
|
155 | shift(value: T): void;
|
156 | /**
|
157 | * Remove and return the value at the beginning of the list.
|
158 | *
|
159 | * @returns The removed value, or `undefined` if the list is empty.
|
160 | *
|
161 | * #### Complexity
|
162 | * Constant.
|
163 | *
|
164 | * #### Notes
|
165 | * This is equivalent to `removeFirst`.
|
166 | */
|
167 | unshift(): T | undefined;
|
168 | /**
|
169 | * Add a value to the beginning of the list.
|
170 | *
|
171 | * @param value - The value to add to the beginning of the list.
|
172 | *
|
173 | * @returns The list node which holds the value.
|
174 | *
|
175 | * #### Complexity
|
176 | * Constant.
|
177 | */
|
178 | addFirst(value: T): LinkedList.INode<T>;
|
179 | /**
|
180 | * Add a value to the end of the list.
|
181 | *
|
182 | * @param value - The value to add to the end of the list.
|
183 | *
|
184 | * @returns The list node which holds the value.
|
185 | *
|
186 | * #### Complexity
|
187 | * Constant.
|
188 | */
|
189 | addLast(value: T): LinkedList.INode<T>;
|
190 | /**
|
191 | * Insert a value before a specific node in the list.
|
192 | *
|
193 | * @param value - The value to insert before the reference node.
|
194 | *
|
195 | * @param ref - The reference node of interest. If this is `null`,
|
196 | * the value will be added to the beginning of the list.
|
197 | *
|
198 | * @returns The list node which holds the value.
|
199 | *
|
200 | * #### Notes
|
201 | * The reference node must be owned by the list.
|
202 | *
|
203 | * #### Complexity
|
204 | * Constant.
|
205 | */
|
206 | insertBefore(value: T, ref: LinkedList.INode<T> | null): LinkedList.INode<T>;
|
207 | /**
|
208 | * Insert a value after a specific node in the list.
|
209 | *
|
210 | * @param value - The value to insert after the reference node.
|
211 | *
|
212 | * @param ref - The reference node of interest. If this is `null`,
|
213 | * the value will be added to the end of the list.
|
214 | *
|
215 | * @returns The list node which holds the value.
|
216 | *
|
217 | * #### Notes
|
218 | * The reference node must be owned by the list.
|
219 | *
|
220 | * #### Complexity
|
221 | * Constant.
|
222 | */
|
223 | insertAfter(value: T, ref: LinkedList.INode<T> | null): LinkedList.INode<T>;
|
224 | /**
|
225 | * Remove and return the value at the beginning of the list.
|
226 | *
|
227 | * @returns The removed value, or `undefined` if the list is empty.
|
228 | *
|
229 | * #### Complexity
|
230 | * Constant.
|
231 | */
|
232 | removeFirst(): T | undefined;
|
233 | /**
|
234 | * Remove and return the value at the end of the list.
|
235 | *
|
236 | * @returns The removed value, or `undefined` if the list is empty.
|
237 | *
|
238 | * #### Complexity
|
239 | * Constant.
|
240 | */
|
241 | removeLast(): T | undefined;
|
242 | /**
|
243 | * Remove a specific node from the list.
|
244 | *
|
245 | * @param node - The node to remove from the list.
|
246 | *
|
247 | * #### Complexity
|
248 | * Constant.
|
249 | *
|
250 | * #### Notes
|
251 | * The node must be owned by the list.
|
252 | */
|
253 | removeNode(node: LinkedList.INode<T>): void;
|
254 | /**
|
255 | * Remove all values from the list.
|
256 | *
|
257 | * #### Complexity
|
258 | * Linear.
|
259 | */
|
260 | clear(): void;
|
261 | private _first;
|
262 | private _last;
|
263 | private _size;
|
264 | }
|
265 | /**
|
266 | * The namespace for the `LinkedList` class statics.
|
267 | */
|
268 | export declare namespace LinkedList {
|
269 | |
270 |
|
271 |
|
272 |
|
273 |
|
274 |
|
275 |
|
276 | interface INode<T> {
|
277 | |
278 |
|
279 |
|
280 |
|
281 |
|
282 | readonly list: LinkedList<T> | null;
|
283 | |
284 |
|
285 |
|
286 |
|
287 |
|
288 |
|
289 | readonly next: INode<T> | null;
|
290 | |
291 |
|
292 |
|
293 |
|
294 |
|
295 |
|
296 | readonly prev: INode<T> | null;
|
297 | |
298 |
|
299 |
|
300 | readonly value: T;
|
301 | }
|
302 | |
303 |
|
304 |
|
305 |
|
306 |
|
307 |
|
308 |
|
309 |
|
310 |
|
311 |
|
312 | function from<T>(values: IterableOrArrayLike<T>): LinkedList<T>;
|
313 | |
314 |
|
315 |
|
316 | class ForwardValueIterator<T> implements IIterator<T> {
|
317 | |
318 |
|
319 |
|
320 |
|
321 |
|
322 | constructor(node: INode<T> | null);
|
323 | /**
|
324 | * Get an iterator over the object's values.
|
325 | *
|
326 | * @returns An iterator which yields the object's values.
|
327 | */
|
328 | iter(): IIterator<T>;
|
329 | /**
|
330 | * Create an independent clone of the iterator.
|
331 | *
|
332 | * @returns A new independent clone of the iterator.
|
333 | */
|
334 | clone(): IIterator<T>;
|
335 | /**
|
336 | * Get the next value from the iterator.
|
337 | *
|
338 | * @returns The next value from the iterator, or `undefined`.
|
339 | */
|
340 | next(): T | undefined;
|
341 | private _node;
|
342 | }
|
343 | /**
|
344 | * A reverse iterator for values in a linked list.
|
345 | */
|
346 | class RetroValueIterator<T> implements IIterator<T> {
|
347 | |
348 |
|
349 |
|
350 |
|
351 |
|
352 | constructor(node: INode<T> | null);
|
353 | /**
|
354 | * Get an iterator over the object's values.
|
355 | *
|
356 | * @returns An iterator which yields the object's values.
|
357 | */
|
358 | iter(): IIterator<T>;
|
359 | /**
|
360 | * Create an independent clone of the iterator.
|
361 | *
|
362 | * @returns A new independent clone of the iterator.
|
363 | */
|
364 | clone(): IIterator<T>;
|
365 | /**
|
366 | * Get the next value from the iterator.
|
367 | *
|
368 | * @returns The next value from the iterator, or `undefined`.
|
369 | */
|
370 | next(): T | undefined;
|
371 | private _node;
|
372 | }
|
373 | /**
|
374 | * A forward iterator for nodes in a linked list.
|
375 | */
|
376 | class ForwardNodeIterator<T> implements IIterator<INode<T>> {
|
377 | |
378 |
|
379 |
|
380 |
|
381 |
|
382 | constructor(node: INode<T> | null);
|
383 | /**
|
384 | * Get an iterator over the object's values.
|
385 | *
|
386 | * @returns An iterator which yields the object's values.
|
387 | */
|
388 | iter(): IIterator<INode<T>>;
|
389 | /**
|
390 | * Create an independent clone of the iterator.
|
391 | *
|
392 | * @returns A new independent clone of the iterator.
|
393 | */
|
394 | clone(): IIterator<INode<T>>;
|
395 | /**
|
396 | * Get the next value from the iterator.
|
397 | *
|
398 | * @returns The next value from the iterator, or `undefined`.
|
399 | */
|
400 | next(): INode<T> | undefined;
|
401 | private _node;
|
402 | }
|
403 | /**
|
404 | * A reverse iterator for nodes in a linked list.
|
405 | */
|
406 | class RetroNodeIterator<T> implements IIterator<INode<T>> {
|
407 | |
408 |
|
409 |
|
410 |
|
411 |
|
412 | constructor(node: INode<T> | null);
|
413 | /**
|
414 | * Get an iterator over the object's values.
|
415 | *
|
416 | * @returns An iterator which yields the object's values.
|
417 | */
|
418 | iter(): IIterator<INode<T>>;
|
419 | /**
|
420 | * Create an independent clone of the iterator.
|
421 | *
|
422 | * @returns A new independent clone of the iterator.
|
423 | */
|
424 | clone(): IIterator<INode<T>>;
|
425 | /**
|
426 | * Get the next value from the iterator.
|
427 | *
|
428 | * @returns The next value from the iterator, or `undefined`.
|
429 | */
|
430 | next(): INode<T> | undefined;
|
431 | private _node;
|
432 | }
|
433 | }
|