連結リスト（linked list）とは、各要素が「次の要素への参照（リンク）」を持つことで、データを順番に並べるデータ構造です。 配列と違って、メモリ上の連続した場所に並んでいる必要はありません。
null。
節点型: Node
値型: value // この節点が持つデータ
Node型: next // 次の節点への参照（最後なら null）
endtype
| 操作 | 配列 | 連結リスト |
|---|---|---|
| i 番目のアクセス（添字） | O(1) | O(n) |
| 先頭への挿入 | O(n) | O(1) |
| 末尾への挿入 | O(1) ※ | O(n) ※ |
| 中間への挿入 | O(n) | O(1) ※ノードを把握済みなら |
| 削除（ノード把握済み） | O(n) | O(1) |
| メモリの使い方 | 連続 | 分散 |
○ append(Node型: head, 値型: v)
Node型: newNode ← 新しいノード(value=v, next=null)
if ( head が null と等しい )
head ← newNode
return head
endif
Node型: cur ← head
while ( cur.next が null と等しくない )
cur ← cur.next
endwhile
cur.next ← newNode
return head
末尾まで n 個たどるため O(n)。
// A と B の間に新ノード X を挿入 newNode.next ← A.next // 新ノードを B に接続 A.next ← newNode // A を新ノードに接続
A を把握しているなら、ポインタの付け替えだけで O(1)。
// A の次のノード B を削除 A.next ← A.next.next // A の next を B の次（C）に直接つなぐ
「飛ばす」ことで削除完了。これも O(1)。
○ 論理型: search(Node型: head, 値型: target)
Node型: cur ← head
while ( cur が null と等しくない )
if ( cur.value が target と等しい )
return true
endif
cur ← cur.next
endwhile
return false
先頭から1つずつ確認するため O(n)。
各ノードが next だけでなく prev（前のノード）も持つ。前後どちらにも進める。
最後のノードの next が null ではなく、先頭ノードを指す。リング状になる。
連結リストの先頭から3番目の要素にアクセスする計算量はどれですか。
連結リストの「途中のノードA」の直後に、新しいノードを挿入する計算量はどれですか（A は既に把握済み）。
連結リストと配列の特徴の組合せとして、最も適切なのはどれですか。
次のようなノードのつながりがあります。X を削除するために必要な操作はどれですか。
head → A → X → B → null
双方向連結リストが単方向リストに比べて優れている点はどれですか。