「みんなのデータ構造」学習メモ：3.1 SLList 単方向連結リスト

みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート

amazon

これまでのメモ

• 「みんなのデータ構造」学習メモ：2.1 ArrayStack
• 「みんなのデータ構造」学習メモ：2.3 ArrayQueue
• 「みんなのデータ構造」学習メモ：2.4 ArrayDeque

2章の後半をすっ飛ばして、第3章の連結リストに入る。
今回は「[P55] 3.1 SLList: 単方向連結リスト」。

TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/SLList.ts

メモ

連結リストとは

第3章でも第2章と同じくListインターフェースの実装を扱うが、データ構造として配列ではなく連結リストを使う。

連結リストとは、「実際のデータ」と「他の要素への参照（ポインタ）」を持った ノード を繋げて列を作ったもの。

Listインターフェースの実装に連結リストを使うのは、配列を使う場合と比較して以下の長所と短所がある。

• 長所：動的な操作がしやすい
  • ノードへの参照uがあれば、uの削除やuの隣へのノードの挿入が定数時間でできる（配列は i 番めに入れるかによって O(1 + min{i, n - i}) の実行時間だった）
• 短所：get(i)やset(i, x)がすべての要素に対して定数時間ではなくなる

SLList（単方向連結リスト）とは

文字通り、ノードが一方向への参照しか持たない連結リストのこと。
各ノードuは

• データ u.x
• 次のノードへの参照 u.next （末尾は null）

を持つ。

SLListの実行時間

SLListはStackとQueueインターフェースを実装する。
push(x)、pop()、add(x)、remove()の実行時間はいずれも O(1)。

SLListでStackを実装する

push(x)操作は

1. 新しいノード u を作成する
2. u.next はそれまでの head をセット
3. head を u にする
4. n++

なので、定数時間で終わる。

pop()操作は

1. headを削除
2. headをhead.nextに移動
3. n--

SLListでQueueを実装する

省略。
先頭の削除はStackのpop()と同じだし、末尾への追加はtail.next = uとするだけ。

SLListの欠点

SLListでDequeの操作を実装しようとしたとき、末尾を削除する操作が足りない。
末尾を削除するためにはtailが指すノードを1つ前にずらす必要があるが、このようなノード（u.next = tail であるノード）を見つけるには先頭から順にノードをたどらなくてはいけない。