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
