LinkedListとは
LinkedList（双方向連結リスト）は、要素同士をリンク（参照）で繋いだ配列です。
双方向連結リストは要素の挿入や削除がリンクの付け替えだけで済むので、そういった処理はArrayより向いています。
一方、中央の要素を取得するにはリンクを辿っていかなければならず、そういった状況では遅くなってしまうらしいです。
JavaScriptでは
JavaScriptにLinkedListは組み込まれていません。
そのため、使いたければライブラリを使うか自分で実装する必要があります。
この記事では、以下の目的でLinkedListクラスを実装してみます。
- 実装方法の勉強
-
LinkedListとは何かの勉強 - 速度（パフォーマンス）や実用目的ではない
実装方針
-
LinkedListクラスを実装する -
Iterator Helpersを使う
-
mapやforEachなどのメソッドの実装で使用
-
-
LinkedListを反復可能（Iterable）として実装する - TypeScriptで実装する
また、LinkedListの内部では、それぞれのノードを示すListNodeクラスを使用します。
LinkedListの詳細
LinkedListは型パラメータEを取ります。
これはリストの要素の型で、Arrayの型パラメータと似たような役割を持ちます。
今回実装するLinkedListのメソッド群はこちらです。
-
constructor: コンストラクタ- 反復可能オブジェクトから
LinkedListを作れるようにする
- 反復可能オブジェクトから
-
push,pop,unshift,shift: 要素を追加/削除する -
map,filter,find,reduce,forEach: よく使いそうなやつ- Iterator Helpersの力を借りる
ListNodeについて
ListNodeは型パラメータEを取ります。
これはLinkedList<E>と同じものが入ります。
また、3つのプロパティを持ちます。
各プロパティの意味はこちらです。
-
element: 保管したい要素、E型 -
next: 次の要素へのリンク、ListNode<E>型 -
next: 前の要素へのリンク、ListNode<E>型
これらはgetter / setterを使わずに実装します。
実装
このように実装してみました。
class ListNode<E> {
constructor(
public readonly element: E,
public next: ListNode<E> | null,
public prev: ListNode<E> | null,
){}
}
class LinkedList<E> implements Iterable<E, void, E> {
private _head: ListNode<E> | null = null;
private _last: ListNode<E> | null = null;
/** ListNodeでループするほうのイテレーター */
private *listNodeIterator(): Generator<ListNode<E>, void, ListNode<E>> {
let currentNode = this._head
while (true) {
if(currentNode === null) return
yield currentNode
currentNode = currentNode.next
}
}
/** headがnullなら更新する */
private ifNullUpdateHead(element: ListNode<E>) {
if(!this._head) this._head = element
}
/** lastがnullなら更新する */
private ifNullUpdateLast(element: ListNode<E>) {
if(!this._last) this._last = element
}
/** lastとheadの整合性チェック */
private checkLastAndHead() {
// prev / nextのチェック
if (this._head) this._head.prev = null
if (this._last) this._last.next = null
// どちらかがnullならもう片方もnull
if (this._head === null) this._last = null
if (this._last === null) this._head = null
}
constructor(init?: Iterable<E>) {
if(!init) return
const first = Iterator.from(init).next()
if(first.done) return
this._head = new ListNode(first.value, null, null)
this._last = this._head
for (const elem of init) {
const node: ListNode<E> = new ListNode(elem, null, this._last);
this._last.next = node
this._last = node
}
}
/** elementでループするほうのイテレーター */
[Symbol.iterator](): IteratorObject<E, void, E> {
const iterator = this.listNodeIterator()
return iterator.map(e => e.element)
}
/** 要素を最後に追加 */
push(element: E) {
const node = new ListNode(element, null, this._last)
if(this._last) this._last.next = node
this._last = node
this.ifNullUpdateHead(node)
}
/** 要素を最初に追加 */
unshift(element: E) {
const node = new ListNode(element, this._head, null)
if(this._head) this._head.prev = node
this._head = node
this.ifNullUpdateLast(node)
}
/** 最後の要素を削除して返す */
pop(): E | void {
if(!this._last) return void 0
const old = this._last.element
this._last = this._last.prev
this.checkLastAndHead()
return old
}
/** 最初の要素を削除して返す */
shift() {
if(!this._head) return void 0
const old = this._head.element
this._head = this._head.next
this.checkLastAndHead()
return old
}
forEach(func: (element: E, index: number) => void): void {
const iterator = this[Symbol.iterator]()
iterator.forEach(func)
}
map<T>(func: (value: E, index: number) => T): LinkedList<T> {
const iterator = this[Symbol.iterator]()
return new LinkedList<T>(iterator.map(func))
}
toArray(): E[] {
return Array.from(this)
}
find(func: (value: E, index: number) => boolean): E | void {
return this[Symbol.iterator]().find(func)
}
filter(func: (value: E, index: number) => boolean): LinkedList<E> {
return new LinkedList<E>(this[Symbol.iterator]().filter(func))
}
reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E): E;
reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E, initialValue: E): E;
reduce<U>(func: (previousValue: U, currentValue: E, currentIndex: number) => U, initialValue: U): U;
reduce<T>(func: (a: T | E, b: E, c: number) => E, init?: T) {
if(init) return this[Symbol.iterator]().reduce(func, init)
return this[Symbol.iterator]().reduce(func)
}
}
push / unshift
pushはリストの最後に要素を追加するメソッドです。
やっていることはこちらです。
- 追加するノードを作成
- 今の
_last.nextを作成したもので置き換える -
_lastを作成したもので置き換える - 整合性チェック
unshiftはこれの先頭に要素を追加する版です。
_last.nextではなく_head.prevを置き換えています。
pop / shift
popはリストの最後の要素を削除し、その要素を返すメソッドです。
やっていることはこちらです。
- もし
this._lastがなかったらreturn -
this._lastを最後から2番目の要素（this._last.prev）で置き換える - 整合性チェック
shiftはこれの最初の要素を削除する版です。
shiftでは2でthis._headをthis._head.nextに置き換えています。
[Symbol.iterator]
LinkedListを反復可能（Iterable）にするメソッドです。
また、mapやコンストラクタなどの実装で使っています。
といってもここでやっていることは少なく、ベースとなるイテレーターを作っているのはlistNodeIteratorメソッドです。
listNodeIterator
ListNodeを順番に返すイテレーターを返すメソッドです。
このメソッドはジェネレーター関数で実装しています。
/** ListNodeでループするほうのイテレーター */
private *listNodeIterator(): Generator<ListNode<E>, void, ListNode<E>> {
let currentNode = this._head
while (true) {
if(currentNode === null) return
yield currentNode
currentNode = currentNode.next
}
}
ここでは、this._headから始まり、ListNodeのnextを順番に辿ってyieldしています。
[Symbol.iterator]ではこのlistNodeIteratorの呼び出しをmapしています。
マッピング関数ではListNodeをListNode.elementにしています。
[Symbol.iterator](): IteratorObject<E, void, E> {
const iterator = this.listNodeIterator()
return iterator.map(e => e.element)
}
なお、mapメソッドは正規イテレーターを返すので、[Symbol.iterator]()の戻り値も正規イテレーターとなります。
コンストラクタ
コンストラクタでは反復可能オブジェクト（Iterable）を受け取り、それを元にLinkedListを構築しています。
実装はこちらです。
constructor(init?: Iterable<E>) {
if(!init) return
const first = Iterator.from(init).next()
if(first.done) return
this._head = new ListNode(first.value, null, null)
this._last = this._head
for (const elem of init) {
const node: ListNode<E> = new ListNode(elem, null, this._last);
this._last.next = node
this._last = node
}
}
やっていることは大まかにこのような感じになっています。
- （
initがなかったらreturn） - 最初の要素（
this.head）を設定 - イテレーターが新しい値を返さなくなるまでループ
- イテレーターの
nextメソッドを呼び出す -
result.valueを使ってListNodeを作成 -
this._lastを更新
- イテレーターの
反復可能であることのメリット
反復可能オブジェクトにはこんなものがあります。
Array- 正規イテレーター
- ジェネレーター
-
LinkedList<- 重要
先ほども説明した通り、ここではLinkedListを反復可能として実装しています。
つまり、LinkedListのコンストラクタにLinkedListを入れられます。
const baseArray = [1, 3, 5]
const baseList = new LinkedList(baseArray) // 配列は反復可能なのでOK
// LinkedListは反復可能なのでOK
const list = new LinkedList(baseList)
これだけで簡単にシャローコピーできるというメリットがあるのです。
forEach / map / filter / etc
正規イテレーターはイテレーターでありながら反復可能です。
そのため、正規イテレーターを返すメソッドの呼び出し結果を、そのままLinkedListのコンストラクタに入れられます。
const list = new LinkedList([1, 2, 4])
// 正規イテレーター
const iterator = list[Symbol.iterator]()
// mapは正規イテレーターを返す
const mapped = iterator.map(x => x ** 2) // 1, 4, 16
const list2 = new LinkedList(mapped) // OK
これを利用して、それぞれのメソッドをサクッと実装していきます。
forEach
実装方法はこんな感じです。
-
this[Symbol.iterator]()を呼び出して正規イテレーターを取得 - 正規イテレーターの
forEachメソッドを呼び出す
forEach(func: (element: E, index: number) => void): void {
const iterator = this[Symbol.iterator]()
iterator.forEach(func)
}
他のメソッドもこんな感じで実装します。
map
map<T>(func: (value: E, index: number) => T): LinkedList<T> {
const iterator = this[Symbol.iterator]()
return new LinkedList<T>(iterator.map(func))
}
filter
filter(func: (value: E, index: number) => boolean): LinkedList<E> {
return new LinkedList<E>(this[Symbol.iterator]().filter(func))
}
find
find(func: (value: E, index: number) => boolean): E | void {
return this[Symbol.iterator]().find(func)
}
reduce
reduceは型のオーバーロードを書く必要があるので、少し面倒です。
といっても配列のreduceメソッドの型定義とほぼ同じなので、そこまで大変ではありません。
reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E): E;
reduce(func: (previousValue: E, currentValue: E, currentIndex: number) => E, initialValue: E): E;
reduce<U>(func: (previousValue: U, currentValue: E, currentIndex: number) => U, initialValue: U): U;
reduce<T>(func: (a: T | E, b: E, c: number) => E, init?: T) {
if(init) return this[Symbol.iterator]().reduce(func, init)
return this[Symbol.iterator]().reduce(func)
}
参考