双方向リンクリスト
Doubly linked list
コレクションの一種
基本的には以下の構造を持ったデータ構造
基本情報としてリストの先頭と最後尾へのリンクがある。
あるオブジェクトからその前後のオブジェクトへのリンクがある。
https://bugbearr.github.io/images/double_linked_list.drawio.svg
prev, next の終端をリストのヘッダにする方法がある。
この方式だと終端の NULL の特例(リストヘッダの特例)がなくなり、すべて同じ双方向リンクの繋ぎ直しのみで実装できるようになる。
その代わり、終端判定はリストヘッダのポインタと等しいかどうかの判定になる。
リストヘッダにリストアイテムと同じ構造を使う方法と、キャストして同じように見せる方法とがある。
https://scrapbox.io/files/67dcf21d967db543e1d676fd.svg
prev を構造体先頭を指さずに、構造体の prev を指す方式もある。
この方法だと、単方向リストの処理をそのまま使うことができる。
ただし、構造体へのオフセットの補正が必要になる。(この分結局遅くなりそう)
これも、ヘッダをリストアイテムと同じ構造にする方法がある。
https://bugbearr.github.io/images/double_linked_list_by_single.drawio.svg
リストアイテム全体を表に出すか、データ部分だけを表に出すかでAPIの設計が変わる。
データサイズが固定的ならば、リンクも含めてメモリ確保するのが簡単。
最大数が明確で少ないならば、配列で取ってしまう方法もある。
配列と違って、順番を自由に繋ぎ直すことができるところに利点がある。
頻出するリンクの付け替え処理をコピペできるように。
以下は、リストヘッダは専用、番兵にNULLを使う、リストアイテム全体を表に出す方式
検索、n番目の要素の取得はリンクリストをたどるだけなので割愛
code:c
typedef struct DoublyLinkedItem {
struct DoublyLinkedItem *pNext;
struct DoublyLinkedItem *pPrev;
char data1;
} DoublyLinkedItem_t;
typedef struct DoublyLinkedList {
DoublyLinkedItem_t *pHead;
DoublyLinkedItem_t *pTail;
int count;
} DoublyLinkedList_t;
// init は構造体の初期化だけで十分かもしれない。
// DoublyLinkedList_t list = {0};
DoublyLinkedList_t *DoublyLinkedList_init(DoublyLinkedList_t *pThis) {
pThis->pHead = NULL;
pThis->pTail = NULL;
pThis->count = 0;
return pThis;
}
void DoublyLinkedList_pushTail(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pItem) {
if (pThis->pTail) {
pItem->pNext = NULL;
pThis->pTail->pNext = pItem;
pItem->pPrev = pThis->pTail;
pThis->pTail = pItem;
pThis->count++;
}
else {
pItem->pNext = NULL;
pItem->pPrev = NULL;
pThis->pTail = pItem;
pThis->pHead = pItem;
pThis->count = 1;
}
}
void DoublyLinkedList_pushHead(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pItem) {
if (pThis->pHead) {
pItem->pPrev = NULL;
pThis->pHead->pPrev = pItem;
pItem->pNext = pThis->pHead;
pThis->pHead = pItem;
pThis->count++;
}
else {
pItem->pPrev = NULL;
pItem->pNext = NULL;
pThis->pHead = pItem;
pThis->pTail = pItem;
pThis->count = 1;
}
}
void DoublyLinkedList_insertBefore(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pAnchor, DoublyLinkedItem_t *pItem) {
if (!pAnchor) {
// エラーにするか、DoublyLinkedList_pushHead を呼ぶか…
}
else if (pAnchor->pPrev) {
pItem->pPrev = pAnchor->pPrev;
pItem->pNext = pAnchor;
pAnchor->pPrev->pNext = pItem;
pAnchor->pPrev = pItem;
}
else {
pItem->pPrev = NULL;
pItem->pNext = pAnchor;
pThis->pHead = pItem;
pAnchor->pPrev = pItem;
}
pThis->count++;
}
void DoublyLinkedList_insertAfter(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pOf, DoublyLinkedItem_t *pItem) {
if (!pAnchor) {
// エラーにするか、DoublyLinkedList_pushTail を呼ぶか…
}
else if (pAnchor->pNext) {
pItem->pPrev = pAnchor;
pItem->pNext = pAnchor->pNext;
pAnchor->pNext->pPrev = pItem;
pAnchor->pNext = pItem;
}
else {
pItem->pPrev = pAnchor;
pItem->pNext = NULL;
pThis->pTail = pItem;
pAnchor->pNext = pItem;
}
pThis->count++;
}
void DoublyLinkedList_remove(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pItem) {
if (pItem->pPrev) {
pItem->pPrev->pNext = pItem->pNext;
}
else {
pThis->pHead = pItem->pNext;
}
if (pItem->pNext) {
pItem->pNext->pPrev = pItem->pPrev;
}
else {
pThis->pTail = pItem->pPrev;
}
pItem->pPrev = NULL;
pItem->pNext = NULL;
pThis->count--;
}
以下は、ヘッダに同じ構造を適用する場合(条件判断が不要になる)
code:c
typedef struct DoublyLinkedItem {
struct DoublyLinkedItem *pNext;
struct DoublyLinkedItem *pPrev;
char data1;
} DoublyLinkedItem_t;
typedef struct DoublyLinkedList {
DoublyLinkedItem_t head;
int count;
} DoublyLinkedList_t;
DoublyLinkedList_t *DoublyLinkedList_init(DoublyLinkedList_t *pThis) {
pThis->head.pNext = &(pThis->head);
pThis->head.pPrev = &(pThis->head);
pThis->count = 0;
return pThis;
}
void DoublyLinkedList_pushTail(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pItem) {
pItem->pNext = &(pThis->head);
pItem->pPrev = pThis->head.pPrev;
pThis->head.pPrev->pNext = pItem;
pThis->head.pPrev = pItem;
pThis->count++;
}
void DoublyLinkedList_pushHead(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pItem) {
pItem->pPrev = &(pThis->head);
pItem->pNext = pThis->head.pNext;
pThis->head.pNext->pPrev = pItem;
pThis->head.pNext = pItem;
pThis->count++;
}
void DoublyLinkedList_insertBefore(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pAnchor, DoublyLinkedItem_t *pItem) {
pItem->pPrev = pAnchor->pPrev;
pItem->pNext = pAnchor;
pAnchor->pPrev->pNext = pItem;
pAnchor->pPrev = pItem;
pThis->count++;
}
void DoublyLinkedList_insertAfter(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pAnchor, DoublyLinkedItem_t *pItem) {
pItem->pPrev = pAnchor;
pItem->pNext = pAnchor->pNext;
pAnchor->pNext->pPrev = pItem;
pAnchor->pNext = pItem;
pThis->count++;
}
void DoublyLinkedList_remove(DoublyLinkedList_t *pThis, DoublyLinkedItem_t *pItem) {
pItem->pPrev->pNext = pItem->pNext;
pItem->pNext->pPrev = pItem->pPrev;
pItem->pNext = NULL;
pItem->pPrev = NULL;
pThis->count--;
}