連結リストの擬似言語

科目B頻出の連結リスト操作。挿入・削除・走査を擬似言語で読みこなします。

日野 こむぎ

連結リストって、配列とどう違うんだっけ?

藤森 さやか 先生

配列はメモリ上で連続だけど、連結リストは「各ノードが次のノードへのポインタを持つ」構造よ。

青木 澪

ノードは「value (値)」と「next (次のノードへのリンク)」を持つ。
先頭要素を head、末尾の next は null (空)、で表現するの。

/* リストの先頭に挿入 */
○ 手続: addFirst(ノード型: head, 整数型: value)
  ノード型: newNode
  newNode ← 新しいノード
  newNode.value ← value
  newNode.next ← head    /* 既存の先頭を新ノードの次に */
  return newNode          /* 新ノードが新しい先頭 */

/* リストの走査 (全要素を出力) */
○ 手続: traverse(ノード型: head)
  ノード型: cur
  cur ← head
  while (cur ≠ null)
    print(cur.value)
    cur ← cur.next
  endwhile

桃井 すみれ

削除はどうするんですかぁ?

青木 澪

「削除対象の前のノードの next」を「削除対象の next」に書き換えるだけよ。

/* リストから値 target のノードを削除 */
○ 手続: delete(ノード型: head, 整数型: target)
  ノード型: cur, prev
  if (head = null) return null
  if (head.value = target)
    return head.next      /* 先頭を削除 */
  endif
  prev ← head
  cur ← head.next
  while (cur ≠ null)
    if (cur.value = target)
      prev.next ← cur.next  /* 削除 */
      return head
    endif
    prev ← cur
    cur ← cur.next
  endwhile
  return head

日野 こむぎ

ポインタの付け替えだけで削除できるんだ、メモリも軽そう!
連結リストって賢いね!

藤森 さやか 先生

そうなのよ。
配列と違って要素を物理的に動かさなくていいの。
挿入・削除が O(1) なのが連結リストの最大の利点ね。

青木 澪

ただし、特定の要素にアクセスするには先頭から辿る必要があって O(n) になるの。
検索が多いなら配列やハッシュのほうが向いているわ。