データ構造/双方向リスト - nkym_memo @ ウィキ

双方向リスト

• 双方向リスト(doubly-linked list),双方向連結リスト,双方向リスト,重連結リスト 連結リストが一方向なセルの移動に対して、前後に自由にたどることのできるリスト

• 前/後へのポインタprev/nextをセルのメンバに持たせる

  struct CELL {
  	struct CELL *prev;
  	struct CELL *next;
  	int value;
  };

• 自由な挿入・削除が可能
• セルに２個のポインタがオーバーヘッドとなる

双方向リストの操作

• 初期化 この場合の初期化は空リストにすることに相当する 変数headのメンバprevとnextがともにhead自身を指している

  head.prev = head.next = &head;

セルの挿入

• 直前のセルへの挿入 　⇒１つ前のセルの直後に挿入 ポインタpで指されるセルの直後に、ポインタxが指すセルを挿入する

  x->prev = p;
  	x->next = p->next;
  	p->next->prev = x;
  	p->next = x;

  ※空リストでも同様の手順で可能
• ポインタpで指されるセルの直前に挿入するとき

  p = p->prev;

  としてから、上の手順を実行

セルの削除

ポインタpで指されるセルを削除する。 ※リストの頭を削除しないように注意

if(p == &head){
		fprintf(stderr,"リストの頭は削除できない");
	}
	p->prev->next = p->next;
	p->next->prev = p->prev;

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)