dackdive's blog

新米webエンジニアによる技術ブログ。JavaScript(React), Salesforce, Python など

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

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

amazon

これまでのメモ

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

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

メモ

連結リストとは

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

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

f:id:dackdive:20200126015508p:plain:w320

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を実装する

f:id:dackdive:20200126015359p:plain:w400

push(x)操作は

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

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

f:id:dackdive:20200126015416p:plain:w400

pop()操作は

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

SLListでQueueを実装する

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

SLListの欠点

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

f:id:dackdive:20200126021021p:plain:w320