README.md (7990B)
1 <!-- 2 3 @license Apache-2.0 4 5 Copyright (c) 2018 The Stdlib Authors. 6 7 Licensed under the Apache License, Version 2.0 (the "License"); 8 you may not use this file except in compliance with the License. 9 You may obtain a copy of the License at 10 11 http://www.apache.org/licenses/LICENSE-2.0 12 13 Unless required by applicable law or agreed to in writing, software 14 distributed under the License is distributed on an "AS IS" BASIS, 15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 See the License for the specific language governing permissions and 17 limitations under the License. 18 19 --> 20 21 # Linked List 22 23 > Singly linked list. 24 25 <!-- Section to include introductory text. Make sure to keep an empty line after the intro `section` element and another before the `/section` close. --> 26 27 <section class="intro"> 28 29 </section> 30 31 <!-- /.intro --> 32 33 <!-- Package usage documentation. --> 34 35 <section class="usage"> 36 37 ## Usage 38 39 ```javascript 40 var linkedList = require( '@stdlib/utils/linked-list' ); 41 ``` 42 43 #### linkedList() 44 45 Returns a new linked list instance. 46 47 ```javascript 48 var list = linkedList(); 49 // returns <LinkedList> 50 ``` 51 52 ##### list.clear() 53 54 Clears a list. 55 56 ```javascript 57 var list = linkedList(); 58 // returns <LinkedList> 59 60 // Add values to the list: 61 list.push( 'foo' ).push( 'bar' ); 62 63 // Peek at the first value: 64 var v = list.first().value; 65 // returns 'foo' 66 67 // Examine the list length: 68 var len = list.length; 69 // returns 2 70 71 // Clear all list items: 72 list.clear(); 73 74 // Peek at the first value: 75 v = list.first(); 76 // returns undefined 77 78 // Examine the list length: 79 len = list.length; 80 // returns 0 81 ``` 82 83 ##### list.first() 84 85 Returns the first `node`. If the list is currently empty, the returned value is `undefined`. 86 87 ```javascript 88 var list = linkedList(); 89 // returns <LinkedList> 90 91 // Add values to the list: 92 list.push( 'foo' ).push( 'bar' ); 93 94 // Peek at the first value: 95 var v = list.first().value; 96 // returns 'foo' 97 ``` 98 99 ##### list.insert( node, value ) 100 101 Inserts a `value` into the list **after** a provided list `node`. 102 103 ```javascript 104 var list = linkedList(); 105 // returns <LinkedList> 106 107 // Add values to the list: 108 list.push( 'foo' ).push( 'bar' ).push( 'beep' ); 109 110 // Determine the list length: 111 var len = list.length; 112 // returns 3 113 114 // Get the second node: 115 var node = list.first().next; 116 117 // Insert a value after the second node: 118 list.insert( node, 'boop' ); 119 120 // Determine the list length: 121 len = list.length; 122 // returns 4 123 ``` 124 125 ##### list.iterator() 126 127 Returns an iterator for iterating over a list. If an environment supports `Symbol.iterator`, the returned iterator is iterable. 128 129 ```javascript 130 var list = linkedList(); 131 132 // Add values to the list: 133 list.push( 'foo' ).push( 'bar' ); 134 135 // Create an iterator: 136 var it = list.iterator(); 137 138 // Iterate over the list... 139 var v = it.next().value; 140 // returns 'foo' 141 142 v = it.next().value; 143 // returns 'bar' 144 145 var bool = it.next().done; 146 // returns true 147 ``` 148 149 **Note**: in order to prevent confusion arising from list mutation during iteration, a returned iterator **always** iterates over a list "snapshot", which is defined as the list of list elements at the time of `list.iterator()` invocation. 150 151 ##### list.last() 152 153 Returns the last `node`. If the list is currently empty, the returned value is `undefined`. 154 155 ```javascript 156 var list = linkedList(); 157 // returns <LinkedList> 158 159 // Add values to the list: 160 list.push( 'foo' ).push( 'bar' ); 161 162 // Peek at the last value: 163 var v = list.last().value; 164 // returns 'bar' 165 ``` 166 167 ##### list.length 168 169 List length. 170 171 ```javascript 172 var list = linkedList(); 173 174 // Examine the initial list length: 175 var len = list.length; 176 // returns 0 177 178 // Add values to the list: 179 list.push( 'foo' ).push( 'bar' ); 180 181 // Retrieve the current list length: 182 len = list.length; 183 // returns 2 184 ``` 185 186 ##### list.pop() 187 188 Removes a value from the end of the list. If the list is currently empty, the returned value is `undefined`. 189 190 ```javascript 191 var list = linkedList(); 192 193 // Add values to the list: 194 list.push( 'foo' ).push( 'bar' ); 195 196 // Remove the last value: 197 var v = list.pop(); 198 // returns 'bar' 199 200 // Add a new value to the list: 201 list.push( 'beep' ); 202 203 // Remove the last value: 204 v = list.pop(); 205 // returns 'beep' 206 ``` 207 208 ##### list.push( value ) 209 210 Adds a value to the end of the list. 211 212 ```javascript 213 var list = linkedList(); 214 215 // Add values to the list: 216 list.push( 'foo' ).push( 'bar' ); 217 218 // Remove the last value: 219 var v = list.pop(); 220 // returns 'bar' 221 222 // Add a new value to the list: 223 list.push( 'beep' ); 224 225 // Remove the last value: 226 v = list.pop(); 227 // returns 'beep' 228 ``` 229 230 ##### list.remove( node ) 231 232 Removes a `node` from the list. 233 234 ```javascript 235 var list = linkedList(); 236 237 // Add values to the list: 238 list.push( 'foo' ).push( 'bar' ).push( 'beep' ); 239 240 // Determine the list length: 241 var len = list.length; 242 // returns 3 243 244 // Get the second node: 245 var node = list.first().next; 246 247 // Remove the second node: 248 var v = list.remove( node ); 249 // returns 'bar' 250 251 // Determine the list length: 252 len = list.length; 253 // returns 2 254 ``` 255 256 ##### list.shift() 257 258 Removes a value from the beginning of the list. If the list is currently empty, the returned value is `undefined`. 259 260 ```javascript 261 var list = linkedList(); 262 263 // Add values to the list: 264 list.push( 'foo' ).push( 'bar' ); 265 266 // Remove the first value: 267 var v = list.shift(); 268 // returns 'foo' 269 270 // Add a new value to the list: 271 list.push( 'beep' ); 272 273 // Remove the first value: 274 v = list.shift(); 275 // returns 'bar' 276 ``` 277 278 ##### list.toArray() 279 280 Returns an array of list values. 281 282 ```javascript 283 var list = linkedList(); 284 285 // Add values to the list: 286 list.push( 'foo' ).push( 'bar' ); 287 288 // Get an array of list values: 289 var vals = list.toArray(); 290 // returns [ 'foo', 'bar' ] 291 ``` 292 293 ##### list.toJSON() 294 295 Serializes a list as JSON. 296 297 ```javascript 298 var list = linkedList(); 299 300 // Add values to the list: 301 list.push( 'foo' ).push( 'bar' ); 302 303 // Serialize to JSON: 304 var o = list.toJSON(); 305 // returns { 'type': 'linked-list', 'data': [ 'foo', 'bar' ] } 306 ``` 307 308 **Note**: `JSON.stringify()` implicitly calls this method when stringifying a list instance. 309 310 ##### list.unshift( value ) 311 312 Adds a value to the beginning of the list. 313 314 ```javascript 315 var list = linkedList(); 316 317 // Add values to the list: 318 list.unshift( 'foo' ).unshift( 'bar' ); 319 320 // Remove the last value: 321 var v = list.pop(); 322 // returns 'foo' 323 324 // Add a new value to the list: 325 list.unshift( 'beep' ); 326 327 // Remove the last value: 328 v = list.pop(); 329 // returns 'bar' 330 ``` 331 332 </section> 333 334 <!-- /.usage --> 335 336 <!-- Package usage notes. Make sure to keep an empty line after the `section` element and another before the `/section` close. --> 337 338 <section class="notes"> 339 340 </section> 341 342 <!-- /.notes --> 343 344 <!-- Package usage examples. --> 345 346 <section class="examples"> 347 348 ## Examples 349 350 <!-- eslint no-undef: "error" --> 351 352 ```javascript 353 var linkedList = require( '@stdlib/utils/linked-list' ); 354 355 var list; 356 var iter; 357 var len; 358 var v; 359 var i; 360 361 // Create a new linked list: 362 list = linkedList(); 363 364 // Add some values to the list: 365 list.push( 'foo' ); 366 list.push( 'bar' ); 367 list.push( 'beep' ); 368 list.push( 'boop' ); 369 370 // Peek at the first and last list values: 371 v = list.first().value; 372 // returns 'foo' 373 374 v = list.last().value; 375 // returns 'boop' 376 377 // Inspect the list length: 378 len = list.length; 379 // returns 4 380 381 // Remove the last list value: 382 v = list.pop(); 383 // returns 'boop' 384 385 // Inspect the list length: 386 len = list.length; 387 // returns 3 388 389 // Iterate over the list: 390 iter = list.iterator(); 391 for ( i = 0; i < len; i++ ) { 392 console.log( 'List value #%d: %s', i+1, iter.next().value ); 393 } 394 395 // Clear the list: 396 list.clear(); 397 398 // Inspect the list length: 399 len = list.length; 400 // returns 0 401 ``` 402 403 </section> 404 405 <!-- /.examples --> 406 407 <!-- Section to include cited references. If references are included, add a horizontal rule *before* the section. Make sure to keep an empty line after the `section` element and another before the `/section` close. --> 408 409 <section class="references"> 410 411 </section> 412 413 <!-- /.references --> 414 415 <!-- Section for all links. Make sure to keep an empty line after the `section` element and another before the `/section` close. --> 416 417 <section class="links"> 418 419 </section> 420 421 <!-- /.links -->