0
# Yallist
1

2
Yallist (Yet Another Linked List) is a high-performance doubly-linked list implementation for JavaScript and TypeScript. It provides array-like operations optimized for frequent insertions and deletions at arbitrary positions, with comprehensive bidirectional iteration capabilities.
3

4
## Package Information
5

6
- **Package Name**: yallist
7
- **Package Type**: npm  
8
- **Language**: TypeScript
9
- **Installation**: `npm install yallist`
10

11
## Core Imports
12

13
```typescript
14
import { Yallist, Node } from "yallist";
15
```
16

17
For CommonJS:
18

19
```javascript
20
const { Yallist, Node } = require("yallist");
21
```
22

23
## Basic Usage
24

25
```typescript
26
import { Yallist } from "yallist";
27

28
// Create a new list from an array
29
const list = new Yallist([1, 2, 3]);
30

31
// Add elements
32
list.push(4, 5);           // Add to tail
33
list.unshift(0);           // Add to head
34

35
// Access elements  
36
console.log(list.get(0));  // 0 (from head)
37
console.log(list.getReverse(0)); // 5 (from tail)
38

39
// Iterate
40
list.forEach((value, index) => console.log(value));
41
list.forEachReverse((value, index) => console.log(value));
42

43
// Transform data
44
const doubled = list.map(x => x * 2);
45
const sum = list.reduce((acc, val) => acc + val, 0);
46

47
// Convert to array
48
console.log(list.toArray()); // [0, 1, 2, 3, 4, 5]
49
```
50

51
## Architecture  
52

53
Yallist consists of two main classes:
54

55
- **Yallist**: The main container class managing the linked list with head/tail pointers and length tracking
56
- **Node**: Individual list elements containing values and bidirectional references
57
- **Bidirectional Operations**: Most operations have both forward and reverse variants for optimal performance
58
- **Iterator Protocol**: Implements JavaScript's iterable interface for native loop support
59
- **Type Safety**: Full TypeScript generic support with proper type inference
60

61
## Capabilities
62

63
### List Construction
64

65
Create and initialize linked lists from iterables or using factory methods.
66

67
```typescript { .api }
68
/**
69
 * Main doubly-linked list class with generic type support
70
 */
71
class Yallist<T = unknown> {
72
  /** First node in the list */
73
  head?: Node<T>;
74
  /** Last node in the list */
75
  tail?: Node<T>;  
76
  /** Number of nodes in the list */
77
  length: number;
78

79
  /**
80
   * Create a new list from an iterable
81
   * @param list - Iterable to initialize the list from
82
   */
83
  constructor(list?: Iterable<T>);
84

85
  /**
86
   * Factory method to create a new list
87
   * @param list - Iterable to initialize the list from  
88
   * @returns New Yallist instance
89
   */
90
  static create<T = unknown>(list?: Iterable<T>): Yallist<T>;
91
}
92
```
93

94
### Element Access
95

96
Retrieve values by position from either end of the list.
97

98
```typescript { .api }
99
/**
100
 * Get the value at position n from the head
101
 * @param n - Index from head (0-based)
102
 * @returns Value at position or undefined if out of bounds
103
 */
104
get(n: number): T | undefined;
105

106
/**
107
 * Get the value at position n from the tail
108
 * @param n - Index from tail (0-based) 
109
 * @returns Value at position or undefined if out of bounds
110
 */
111
getReverse(n: number): T | undefined;
112
```
113

114
### Element Addition
115

116
Add elements to the head or tail of the list.
117

118
```typescript { .api }
119
/**
120
 * Add elements to the tail of the list
121
 * @param args - Elements to add
122
 * @returns New length of the list
123
 */
124
push(...args: T[]): number;
125

126
/**
127
 * Add elements to the head of the list
128
 * @param args - Elements to add
129
 * @returns New length of the list
130
 */
131
unshift(...args: T[]): number;
132
```
133

134
### Element Removal  
135

136
Remove and return elements from either end of the list.
137

138
```typescript { .api }
139
/**
140
 * Remove and return the tail element
141
 * @returns Tail value or undefined if list is empty
142
 */
143
pop(): T | undefined;
144

145
/**
146
 * Remove and return the head element
147
 * @returns Head value or undefined if list is empty
148
 */
149
shift(): T | undefined;
150
```
151

152
### Node Operations
153

154
Direct manipulation of Node objects for advanced use cases.
155

156
```typescript { .api }
157
/**
158
 * Remove a specific node from the list
159
 * @param node - Node to remove (must belong to this list)
160
 * @returns Next node after the removed node, or undefined if removing tail
161
 * @throws Error with message "removing node which does not belong to this list"
162
 */
163
removeNode(node: Node<T>): Node<T> | undefined;
164

165
/**
166
 * Move a node to the head of the list
167
 * @param node - Node to move (will be removed from its current list if any)
168
 */
169
unshiftNode(node: Node<T>): void;
170

171
/**
172
 * Move a node to the tail of the list
173
 * @param node - Node to move (will be removed from its current list if any)
174
 */
175
pushNode(node: Node<T>): void;
176
```
177

178
### Iteration
179

180
Iterate through the list in either direction with callback functions.
181

182
```typescript { .api }
183
/**
184
 * Execute a function for each element from head to tail
185
 * @param fn - Function to execute for each element (receives value, index, and list)
186
 * @param thisp - Value to use as 'this' when executing fn (optional)
187
 */
188
forEach(fn: (value: T, index: number, list: Yallist<T>) => any, thisp?: any): void;
189

190
/**
191
 * Execute a function for each element from tail to head
192
 * @param fn - Function to execute for each element (receives value, index, and list)
193
 * @param thisp - Value to use as 'this' when executing fn (optional)
194
 */
195
forEachReverse(fn: (value: T, index: number, list: Yallist<T>) => any, thisp?: any): void;
196

197
/**
198
 * Make the list iterable (head to tail)
199
 * @returns Iterator that yields values from head to tail
200
 */
201
[Symbol.iterator](): IterableIterator<T>;
202
```
203

204
### Transformation
205

206
Create new lists by transforming elements while preserving the list structure.
207

208
```typescript { .api }
209
/**
210
 * Create a new list with transformed values (head to tail)
211
 * @param fn - Transformation function (receives value and list)
212
 * @param thisp - Value to use as 'this' when executing fn (optional)
213
 * @returns New Yallist with transformed values
214
 */
215
map<R = any>(fn: (value: T, list: Yallist<T>) => R, thisp?: any): Yallist<R>;
216

217
/**
218
 * Create a new list with transformed values (tail to head)
219
 * @param fn - Transformation function (receives value and list)
220
 * @param thisp - Value to use as 'this' when executing fn (optional)
221
 * @returns New Yallist with transformed values
222
 */
223
mapReverse<R = any>(fn: (value: T, list: Yallist<T>) => R, thisp?: any): Yallist<R>;
224
```
225

226
### Reduction
227

228
Reduce the list to a single value using accumulator functions.
229

230
```typescript { .api }
231
/**
232
 * Reduce list to single value without initial value (head to tail)
233
 * @param fn - Reducer function
234
 * @returns Reduced value
235
 * @throws TypeError with message "Reduce of empty list with no initial value"
236
 */
237
reduce(fn: (left: T, right: T, index: number) => T): T;
238

239
/**
240
 * Reduce list to single value with initial value (head to tail)
241
 * @param fn - Reducer function
242
 * @param initial - Initial accumulator value
243
 * @returns Reduced value
244
 */
245
reduce<R = any>(fn: (acc: R, next: T, index: number) => R, initial: R): R;
246

247
/**
248
 * Reduce list to single value without initial value (tail to head)
249
 * @param fn - Reducer function
250
 * @returns Reduced value
251
 * @throws TypeError with message "Reduce of empty list with no initial value"
252
 */
253
reduceReverse(fn: (left: T, right: T, index: number) => T): T;
254

255
/**
256
 * Reduce list to single value with initial value (tail to head)
257
 * @param fn - Reducer function
258
 * @param initial - Initial accumulator value
259
 * @returns Reduced value
260
 */
261
reduceReverse<R = any>(fn: (acc: R, next: T, index: number) => R, initial: R): R;
262
```
263

264
### Array Conversion
265

266
Convert the list to standard JavaScript arrays in either direction.
267

268
```typescript { .api }
269
/**
270
 * Convert list to array from head to tail
271
 * @returns Array containing all list values
272
 */
273
toArray(): T[];
274

275
/**
276
 * Convert list to array from tail to head
277
 * @returns Array containing all list values in reverse order
278
 */
279
toArrayReverse(): T[];
280
```
281

282
### List Slicing
283

284
Extract portions of the list as new Yallist instances.
285

286
```typescript { .api }
287
/**
288
 * Extract a slice of the list (head to tail)
289
 * @param from - Start index (inclusive, default 0)
290
 * @param to - End index (exclusive, default list.length)
291
 * @returns New Yallist containing the slice
292
 */
293
slice(from?: number, to?: number): Yallist<T>;
294

295
/**
296
 * Extract a slice of the list (tail to head)
297
 * @param from - Start index (inclusive, default 0)
298
 * @param to - End index (exclusive, default list.length)
299
 * @returns New Yallist containing the slice in reverse order
300
 */
301
sliceReverse(from?: number, to?: number): Yallist<T>;
302
```
303

304
### List Modification
305

306
Modify the list by removing/inserting elements at arbitrary positions.
307

308
```typescript { .api }
309
/**
310
 * Remove elements and/or insert new elements at a specific position
311
 * @param start - Start index for modification (negative indices count from end)
312
 * @param deleteCount - Number of elements to remove (default 0)
313
 * @param nodes - New elements to insert at the start position
314
 * @returns Array of removed elements
315
 */
316
splice(start: number, deleteCount?: number, ...nodes: T[]): T[];
317

318
/**
319
 * Reverse the list in place
320
 * @returns This list (for chaining)
321
 */
322
reverse(): Yallist<T>;
323
```
324

325
## Types
326

327
```typescript { .api }
328
/**
329
 * Individual node in the doubly-linked list
330
 */
331
class Node<T = unknown> {
332
  /** The data stored in this node */
333
  value: T;
334
  /** Reference to the next node in the list */
335
  next?: Node<T>;
336
  /** Reference to the previous node in the list */
337
  prev?: Node<T>;
338
  /** Reference to the list this node belongs to */
339
  list?: Yallist<T>;
340

341
  /**
342
   * Create a new node
343
   * @param value - The value to store in the node
344
   * @param prev - Previous node reference
345
   * @param next - Next node reference  
346
   * @param list - List this node belongs to
347
   */
348
  constructor(
349
    value: T,
350
    prev?: Node<T>,
351
    next?: Node<T>,
352
    list?: Yallist<T>
353
  );
354
}
355
```