Typescript での双方向連結リスト

Typescript での双方向連結リストの実装例です。
※2024/02/25 にバグを修正

■プログラム（list.ts）

/**
 *
 * bidirectional linked list
 *
 */


export class Node {
  public obj: any;
  public prev: Node | null = null;
  public next: Node | null = null;
  
  
  constructor(obj: any) {
    this.obj = obj;
  }
}


export class List {
  public length: number = 0;
  public head: Node | null = null;
  public tail: Node | null = null;
  
  
  constructor(arr?: Array<any>) {
    if (arr === undefined) return;
    
    for (let obj of arr) {
      this.push(obj);
    }
  }


  /**
   * add node to tail
   */
  public push_node(node: Node) {
    if (this.head === null) {
      this.head = node;
    }
    
    if (this.tail !== null) {
      this.tail.next = node;
      node.prev = this.tail;
    }

    this.tail = node;
    this.length += 1;
    
    return this;
  }


  /**
   * add new obj to tail
   */
  public push(obj: any) {
    const node = new Node(obj);
    return this.push_node(node);
  }
  

  /**
   * add node to head
   */
  public unshift_node(node: Node) {
    if (this.head === null) {
      this.head = this.tail = node;
    }
    else {
      const head = this.head;
      head.prev = node;
      node.next = head;
      this.head = node;
    }
    
    this.length += 1;
    
    return this;
  }

  /**
   * add new obj to head
   */
  public unshift(obj: any) {
    const node = new Node(obj);
    return this.unshift_node(node);
  }
  

  /**
   * remove tail node
   */
  public pop_node() {
    if (this.tail === null) return null;
    
    const node = this.tail;
    this.tail = node.prev;
    if (node.prev === null) this.head = null;

    node.prev = null;
    node.next = null;
    this.length -= 1;
    
    return node;
  }


  /**
   * remove tail
   */
  public pop() {
    const node = this.pop_node();
    return node.obj;
  }
  
  
  /**
   * remove head node
   */
  public shift_node() {
    if (this.head === null) return null;
    
    // head -> node <-> next
    const node = this.head;
    this.head = node.next;
    if (this.head !== null) this.head.prev = null;
    if (node.next === null) this.tail = null;
    
    node.prev = null;
    node.next = null;
    this.length -= 1;
    
    return node;
  }
  
  
  /**
   * remove head
   */
  public shift() {
    const node = this.shift_node();
    return node.obj;
  }
  
  
  /**
   * return nth node
   */
  public nth_node(n: number) {
    if (n < 0) return null;
    if (n >= this.length) return null;
    
    let node = this.head;
    if (node === null) return null;
    
    for (let i = 0; i < n; i++) {
      if (node.next === null) return null;
      node = node.next;
    }

    if (node === null) return null;
    
    return node;
  }


  /**
   * return nth obj
   */
  public nth(n: number) {
    const node = this.nth_node(n)
    return node.obj;
  }


  /**
   * remove node
   */
  public remove_node(node: Node) {
    if (node === null) return null; // for tsc
    
    if (node.prev === null) {
      this.head = node.next;
    }
    else {
      node.prev.next = node.next;
    }
    
    if (node.next === null) {
      this.tail = node.prev;
    }
    else {
      node.next.prev = node.prev;
    }
    
    this.length -= 1;
    return node.obj;
  }
  

  /**
   * remove nth obj
   */
  public remove(n: number) {
    if (n < 0) return null;
    if (n >= this.length) return null;

    let node = this.head;
    if (node === null) return null; // for tsc
    for (let i = 0; i < n; i++) {
      if (node === null) return null; // for tsc
      node = node.next;
    }

    return this.remove_node(node);
  }


  public slice(from: number, to?: number) {
    if (from < 0) return null;
    if (from >= this.length) return null;
    if (to === undefined) to = this.length;
    if (to < 0) return null;
    if (to > this.length) return null;

    // skip head
    let node = this.head;
    if (node === null) return null; // for tsc
    for (let i = 0; i < from; i++) {
      if (node === null) return null; // for tsc
      node = node.next;
    }
    if (node === null) return null; // for tsc
    const ret_head = node;
    const head_tail = node.prev;
    
    // slice
    for (let i = from; i < to; i++) {
      if (node === null) return null; // for tsc
      node = node.next;
    }
    if (node === null) return null; // for tsc
    const ret_tail = node.prev;
    const tail_head = node;
    
    // this
    if (head_tail === null) {
      this.head = tail_head;
    }
    else {
      head_tail.next = tail_head;
    }
    
    if (tail_head === null) {
      this.tail = head_tail;
    }
    else {
      tail_head.prev = head_tail;
    }
    this.length -= (to - from);
    
    // ret
    const ret = new List();
    if (ret_head !== null) {
      ret.head = ret_head;
      ret_head.prev = null;
    }
    
    if (ret_tail !== null) {
      ret.tail = ret_tail;
      ret_tail.next = null;
    }
    
    ret.length = to - from;
    
    return ret;
  }
  
  
  public copy() {
    const new_list = new List();
    
    let node = this.head;
    while (node !== null) {
      new_list.push(node.obj);
      node = node.next;
    }
    new_list.length = this.length;
    
    return new_list;
  }


  /**
   * insert list at idx (0 - length)
   */
  public insert(idx: number, list: List) {
    if (idx < 0) return null;
    if (idx > this.length) return null;
    if (list === null) return null;
    if (list.head === null) return this;
    if (list.tail === null) return this;
    
    const new_list = list.copy();
    if (new_list.head === null) return this;
    if (new_list.tail === null) return this;
    
    if (this.head === null) this.head = new_list.head;
    if (this.tail === null) this.tail = new_list.tail;
    if (this.length === 0) {
      this.length = new_list.length;
      return this;
    }
    
    if (idx === 0) {
      const head: Node | null = this.head;
      new_list.tail.next = this.head;
      this.head = new_list.head;
      new_list.tail.next = head;
      this.length += new_list.length;
    }
    else if (idx === this.length) {
      const tail: Node | null = this.tail;
      new_list.head.prev = tail;
      tail.next = new_list.head;
      this.tail = new_list.tail;
      this.length += new_list.length;
    }
    else {
      // skip
      let node: Node | null = this.head;
      for (let i = 0; i < idx; i++) {
	if (node === null) return null;
	node = node.next;
      }
      
      // insert
      if (node === null) return null;
      const prev = node.prev;
      if (prev !== null) prev.next = new_list.head;
      new_list.head.prev = prev;
      new_list.tail.next = node;
      this.length += new_list.length;
    }
    
    return this;
  }
  
  
  public to_array() {
    const arr = new Array(this.length);
    let node = this.head;
    for (let i = 0; i < this.length; i++) {
      if (node === null) return null;
      arr[i] = node.obj;
      node = node.next;
    }
    
    return arr;
  }
}

■動作確認

import { List } from '../lib/list';

(() => {
  // push
  const list1 = new List(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']);
  list1.push('o');
  console.log(`push('o')`);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);
  
  // pop
  let obj;
  obj = list1.pop();
  console.log(`pop()`);
  console.log(obj);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);

  // unshift
  list1.unshift('-');
  console.log(`unshift('-')`);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);

  // shift
  obj = list1.shift();
  console.log(`shift()`);
  console.log(obj);
  console.log(list1.to_array());
  console.log(list1.length);
  if (list1.head == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${list1.head.obj}, prev: ${list1.head.prev}, next: ${list1.head.next}`);

  // nth
  obj = list1.nth(2);
  console.log(`nth(2)`);
  console.log(obj);
  console.log(list1.to_array());

  // remove_node
  let node;
  node = list1.head;
  if (node == null) {
    console.log('error: list1.head is null');
    return;
  }
  console.log(`head: obj: ${node.obj}, prev: ${node.prev}, next: ${node.next}`);
  obj = list1.remove_node(node);
  console.log(`remove_node(head)`);
  console.log(obj);
  console.log(list1.to_array());

  node = list1.head;
  if (node == null) {
    console.log('error: list1.head.next is null');
    return;
  }
  node = node.next;
  if (node == null) {
    console.log('error: list1.head.next is null');
    return;
  }
  list1.remove_node(node);
  console.log(`remove_node(head.next)`);
  console.log(list1.to_array());

  node = list1.tail;
  if (node == null) {
    console.log('error: list1.tail is null');
    return;
  }
  list1.remove_node(node);
  console.log(`remove_node(tail)`);
  console.log(list1.to_array());
  
  // remove
  obj = list1.remove(2);
  console.log(`remove(2)`);
  console.log(obj);
  console.log(list1.to_array());

  // slice
  obj = list1.slice(1, 4);
  console.log(`slice(1, 4)`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.to_array());

  // copy
  obj = list1.copy();
  console.log(`copy()`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.to_array());
  
  // insert
  const list2 = new List(['x', 'y', 'z']);
  obj = list1.insert(1, list2);
  console.log(`insert(1, ['x', 'y', 'z'])`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.length);
  
  obj = list1.insert(0, new List(['-']));
  console.log(`insert(0, ['-'])`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.length);

  obj = list1.insert(8, new List(['--']));
  console.log(`insert(8, ['--'])`);
  if (obj !== null) console.log(obj.to_array());
  console.log(list1.length);

})();

■実行例

push('o')
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n', 'o'
]
15
head: obj: a, prev: null, next: [object Object]
pop()
o
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n'
]
14
head: obj: a, prev: null, next: [object Object]
unshift('-')
[
  '-', 'a', 'b', 'c',
  'd', 'e', 'f', 'g',
  'h', 'i', 'j', 'k',
  'l', 'm', 'n'
]
15
head: obj: -, prev: null, next: [object Object]
shift()
-
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n'
]
14
head: obj: a, prev: null, next: [object Object]
nth(2)
c
[
  'a', 'b', 'c', 'd',
  'e', 'f', 'g', 'h',
  'i', 'j', 'k', 'l',
  'm', 'n'
]
head: obj: a, prev: null, next: [object Object]
remove_node(head)
a
[
  'b', 'c', 'd', 'e',
  'f', 'g', 'h', 'i',
  'j', 'k', 'l', 'm',
  'n'
]
remove_node(head.next)
[
  'b', 'd', 'e', 'f',
  'g', 'h', 'i', 'j',
  'k', 'l', 'm', 'n'
]
remove_node(tail)
[
  'b', 'd', 'e', 'f',
  'g', 'h', 'i', 'j',
  'k', 'l', 'm'
]
remove(2)
e
[
  'b', 'd', 'f', 'g',
  'h', 'i', 'j', 'k',
  'l', 'm'
]
slice(1, 4)
[ 'd', 'f', 'g' ]
[
  'b', 'h', 'i',
  'j', 'k', 'l',
  'm'
]
copy()
[
  'b', 'h', 'i',
  'j', 'k', 'l',
  'm'
]
[
  'b', 'h', 'i',
  'j', 'k', 'l',
  'm'
]
insert(1, ['x', 'y', 'z'])
[
  'b', 'x', 'y', 'z',
  'h', 'i', 'j', 'k',
  'l', 'm'
]
10
insert(0, ['-'])
[
  '-', 'b', 'x', 'y',
  'z', 'h', 'i', 'j',
  'k', 'l', 'm'
]
11
insert(8, ['--'])
[
  '-',  'b', 'x', 'y',
  'z',  'h', 'i', 'j',
  '--', 'k', 'l', 'm'
]
12