連鎖リストの概念と構造

連鎖リストは物理的に非連続で順序が保たれていないデータ構造であり、論理的な順序は各ノード間のポインタリンクによって実現されます。

連鎖リストの分類

実際のアプリケーションでは様々な種類の連鎖リストがありますが、主に以下の3つの特性を組み合わせることで8種類の構造が考えられます：

• 単方向または双方向
• ヘッダありまたはヘッダなし
• 循環または非循環

最も一般的に使用される構造は以下の2つです：

• ヘッダなし単方向非循環連鎖リスト：構造がシンプルで、通常は他のデータ構造のサブ構造として使用されます。
• ヘッダあり双方向循環連鎖リスト：構造が複雑ですが、多くの利点があるため実装が比較的容易となります。

単方向連鎖リストの実装

以下に実装するインターフェースを示します：

// ノードの動的確保
ListNode* createNode(int value);
// 連鎖リストの表示
void printList(ListNode* head);
// 末尾への挿入
void insertAtTail(ListNode** head, int value);
// 先頭への挿入
void insertAtHead(ListNode** head, int value);
// 末尾からの削除
void removeAtTail(ListNode** head);
// 先頭からの削除
void removeAtHead(ListNode** head);
// 値の検索
ListNode* searchValue(ListNode* head, int value);
// 指定位置の後の挿入
void insertAfter(ListNode* pos, int value);
// 指定位置の後の削除
void removeAfter(ListNode* pos);
// 指定位置の前に挿入
void insertBefore(ListNode** head, ListNode* pos, int value);
// 指定位置の削除
void removePosition(ListNode** head, ListNode* pos);
// 連鎖リストの破棄
void destroyList(ListNode** head);

1. ノードの定義

typedef int NodeData;

typedef struct Node {
    NodeData data;
    struct Node* next;
}ListNode;

2. 連鎖リストの表示

void printList(ListNode* head) {
    ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

3. 末尾への挿入

void insertAtTail(ListNode** head, int value) {
    ListNode* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        ListNode* tail = *head;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newNode;
    }
}

4. 先頭への挿入

void insertAtHead(ListNode** head, int value) {
    ListNode* newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

5. 末尾からの削除

void removeAtTail(ListNode** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    ListNode* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    free(current->next);
    current->next = NULL;
}

6. 先頭からの削除

void removeAtHead(ListNode** head) {
    if (*head == NULL) return;
    ListNode* temp = *head;
    *head = (*head)->next;
    free(temp);
}

7. 値の検索

ListNode* searchValue(ListNode* head, int value) {
    ListNode* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

8. 指定位置の前の挿入

void insertBefore(ListNode** head, ListNode* pos, int value) {
    if (pos == *head) {
        insertAtHead(head, value);
    } else {
        ListNode* current = *head;
        while (current->next != pos) {
            current = current->next;
        }
        ListNode* newNode = createNode(value);
        newNode->next = pos;
        current->next = newNode;
    }
}

9. 指定位置の後の挿入

void insertAfter(ListNode* pos, int value) {
    ListNode* newNode = createNode(value);
    newNode->next = pos->next;
    pos->next = newNode;
}

10. 指定位置の削除

void removePosition(ListNode** head, ListNode* pos) {
    if (pos == *head) {
        removeAtHead(head);
    } else {
        ListNode* current = *head;
        while (current->next != pos) {
            current = current->next;
        }
        current->next = pos->next;
        free(pos);
    }
}

11. 指定位置の後の削除

void removeAfter(ListNode* pos) {
    if (pos->next == NULL) return;
    ListNode* temp = pos->next;
    pos->next = pos->next->next;
    free(temp);
}

12. 連鎖リストの破棄

void destroyList(ListNode** head) {
    ListNode* current = *head;
    while (current != NULL) {
        ListNode* temp = current->next;
        free(current);
        current = temp;
    }
    *head = NULL;
}

双方向循環連鎖リストの実装

1. ノードの定義

typedef int DNodeData;

typedef struct DNode {
    struct DNode* next;
    struct DNode* prev;
    DNodeData data;
}DListNode;

2. 双方向循環連鎖リストの初期化

void initList(DListNode** head) {
    *head = createDNode(-1);
    (*head)->next = *head;
    (*head)->prev = *head;
}

3. 双方向循環連鎖リストの表示

void printDList(DListNode* head) {
    assert(head);
    DListNode* current = head->next;
    printf("<=head=>");
    while (current != head) {
        printf("%d<=>", current->data);
        current = current->next;
    }
    printf("\n");
}

4. 末尾への挿入

void insertAtTail(DListNode* head, DNodeData value) {
    assert(head);
    DListNode* newNode = createDNode(value);
    DListNode* tail = head->prev;
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = head;
    head->prev = newNode;
}

5. リストが空かどうかのチェック

bool isEmpty(DListNode* head) {
    assert(head);
    return head->next == head;
}

6. 末尾からの削除

void removeAtTail(DListNode* head) {
    assert(head);
    assert(!isEmpty(head));
    DListNode* tail = head->prev;
    DListNode* prevTail = tail->prev;
    prevTail->next = head;
    head->prev = prevTail;
    free(tail);
}

7. 先頭への挿入

void insertAtHead(DListNode* head, DNodeData value) {
    assert(head);
    DListNode* newNode = createDNode(value);
    newNode->next = head->next;
    head->next->prev = newNode;
    head->next = newNode;
    newNode->prev = head;
}

8. 指定位置の前の挿入

void insertBefore(DListNode* pos, DNodeData value) {
    assert(pos);
    DListNode* prevPos = pos->prev;
    DListNode* newNode = createDNode(value);
    prevPos->next = newNode;
    newNode->prev = prevPos;
    newNode->next = pos;
    pos->prev = newNode;
}