2 連結リスト，双方向リスト

2.1 連結リスト

　リストを表現するためのデータ構造の一つである．「自身のデータ」以外に「別のデータへの参照を保存するフィールド」を持っている．
　挿入や削除では配列よりも優れている．なぜなら，配列によるリストに新たなデータを挿入する場合は，それ以降の要素をすべてずらす必要があるが，連結リストでは参照する要素の付け替えだけで済むからだ
　しかし，探索では配列の二分探索に負ける．

2.1.1 実装例

　連結リストは以下のコードのように実装することができる．次の要素を指し示す多面は余分な領域が必要である．

class MyLinkedData{
    String key;
    String data;
    MyLinkedData next;
};

MyLinkedData p = header;
while(p!=null){
    System.out.println("" + p);
    p = p.next;
}
        

2.1.2 欠点

• 次しかさかのぼれない
　挿入や削除をする際に「対象となる場所の前のノードの参照情報が必要」
• 前にもさかのぼれれば上記の問題は解決する
　次(next)だけでなく，前(prev)の情報も保持するデータ構造．
• 双方向リストを取り上げる

2.2 双方向リスト

　リストの先頭(head)と末尾(tail)に特殊なデータを置く．

2.2.1 実装例

　双方向リストは以下のコードのように実装することができる．次の要素を指し示す多面は余分な領域が必要である．

class MyDoublyLinkedData{
    private String key;
    private String data;
    MyDoublyLinkedData prev;
    MyDoublyLinkedData next;
}
        

p.prev.next = n;
n.prev = p.prev;
n.next = p;
p.prev = n;
        

p.prev.next = n;
n.prev = p.prev;
n.next = p;
p.prev = n;
        

p.prev.next = p.next;
p.next.prev = p.prev;
        

p.prev.next = p.next; // p.prev.next = null; と同義
if(p.next!=null){
    p.next.prev = p.prev;
}
        

3 連結リストの計算量

• 探索：O(n)
　先頭から1個ずつ探さないといけないため，最悪データの個数だけ比較が必要である．
• 削除：O(n) or O(1)
　削除する箇所の間への参照が既知ならO(1),
わからない場合は探索が必要である(O(n))．
• 挿入：O(n) or O(1)
　削除する箇所の間への参照が既知ならO(1),
わからない場合は探索が必要である(O(n))．