In a singly linked list each node in the list stores the contents of the node and a reference (or pointer in some languages) to the next node in the list. It is one of the simplest way to store a collection of items.
In this lesson we cover how to create a linked list data structure and how to use its strengths to implement an O(1) FIFO queue.
/** * Linked list node */ export interface LinkedListNode<T> { value: T next?: LinkedListNode<T> } /** * Linked list for items of type T */ export class LinkedList<T> { public head?: LinkedListNode<T> = undefined; public tail?: LinkedListNode<T> = undefined; /** * Adds an item in O(1) **/ add(value: T) { const node = { value, next: undefined } if (!this.head) { this.head = node; } if (this.tail) { this.tail.next = node; } this.tail = node; } /** * FIFO removal in O(1) */ dequeue(): T | undefined { if (this.head) { const value = this.head.value; this.head = this.head.next; if (!this.head) { this.tail = undefined; } return value; } } /** * Returns an iterator over the values */ *values() { let current = this.head; while (current) { yield current.value; current = current.next; } } }
import { LinkedList } from './linkedList'; test('basic', () => { const list = new LinkedList<number>(); list.add(1); list.add(10); list.add(5); expect(Array.from(list.values())).toMatchObject([1, 10, 5]); expect(list.dequeue()).toBe(1); expect(Array.from(list.values())).toMatchObject([10, 5]); expect(list.dequeue()).toBe(10); expect(list.dequeue()).toBe(5); expect(list.dequeue()).toBe(undefined); expect(Array.from(list.values())).toMatchObject([]); list.add(5); expect(Array.from(list.values())).toMatchObject([5]); });
We can also see the beautiy of Generator with Array.from partten.
Array.from(list.values())
It saves lots of code to keep maintaing the indexing of the array.