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
     
       {  value: T  next?: LinkedListNode
      
       }/** * Linked list for items of type T */export class LinkedList
       
         {  public head?: LinkedListNode
        
          = undefined;  public tail?: LinkedListNode
         
           = 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
     
      ();  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]);});