線形リストの特性と比較

配列ベースリストの特徴

配列を用いたリストはメモリ空間を事前に確保する必要があるため、サイズ変更が難しいが、要素へのアクセスは定数時間で可能である。挿入や削除を行う際には、対象位置以降のすべての要素を移動させる必要があり、処理効率が低下する可能性がある。

単方向連結リストの特徴

連結リストは動的メモリ割り当てにより柔軟なサイズ管理が可能だが、メモリ使用効率は配列に劣る。要素検索には先頭から順にたどる必要があるが、挿入・削除操作はポインタの書き換えだけで完了する。

連結リストにおける重要なノード

ヘッドポインタはリストの最初のノードを指すポインタであり、ヘッドノードが存在する場合はそのノードを指す。ヘッドノードはデータを保持せず、最初のデータノードへのリンクを提供する。データノードは実際の情報を格納する各要素である。

選択問題

1. 頻繁にインデックス指定でのアクセスと末尾操作が必要な場合、最も適したデータ構造は配列ベースリストである。
2. 連結リストが持たない特徴は任意要素へのランダムアクセスである。
3. 末尾ノードの操作に最適化された構造はテールポインタ付き循環連結リストである。
4. 配列ベースリストは連続メモリ領域を必要とし、連結リストは不要であるが、配列ベースリストは挿入・削除操作に向いていない。
5. ヘッドノードを持たない単方向連結リストの空判定条件はhead == NULLである。
6. ヘッドノード付き循環連結リストの空判定条件はhead->next == headである。
7. n個の要素を持つ配列リストでi番目の要素を削除する場合、移動が必要な要素数はn - i個である。
8. ヘッドノード付き双方向循環連結リストの空判定条件はhead->next->prior == NULLである。
9. 単方向連結リストでpが指すノードの次のノードを削除する正しい処理は：s = p->next; p->next = s->next; free(s);
10. ベースアドレスBase、要素サイズmの配列でi番目の要素のアドレスはBase + (i-1) × mである。

アルゴリズム実装

ソート済み配列への要素挿入

#define MAX_SIZE 100

typedef struct {
    int elements[MAX_SIZE];
    int count;
} ArraySequence;

int insert_sorted(ArraySequence *seq, int value) {
    if (seq->count >= MAX_SIZE) return 0;
    
    int pos = seq->count - 1;
    while (pos >= 0 && seq->elements[pos] > value) {
        seq->elements[pos + 1] = seq->elements[pos];
        pos--;
    }
    seq->elements[pos + 1] = value;
    seq->count++;
    return 1;
}

配列からの範囲削除

int remove_range(ArraySequence *seq, int start_index, int delete_count) {
    if (start_index <= 0 || start_index > seq->count || delete_count <= 0) 
        return 0;
    
    int end_pos = start_index + delete_count - 1;
    if (end_pos >= seq->count) {
        seq->count = start_index - 1;
    } else {
        for (int i = start_index - 1; i <= seq->count - delete_count - 1; i++) {
            seq->elements[i] = seq->elements[i + delete_count];
        }
        seq->count -= delete_count;
    }
    return 1;
}

二つのソート済み配列のマージ

void merge_descending(ArraySequence *first, ArraySequence *second, ArraySequence *result) {
    int i = first->count - 1;
    int j = second->count - 1;
    int k = 0;
    
    while (i >= 0 && j >= 0) {
        if (first->elements[i] >= second->elements[j]) {
            result->elements[k++] = first->elements[i--];
        } else {
            result->elements[k++] = second->elements[j--];
        }
    }
    
    while (i >= 0) result->elements[k++] = first->elements[i--];
    while (j >= 0) result->elements[k++] = second->elements[j--];
}

奇数偶数の分割並び替え

void partition_odd_even(ArraySequence *seq) {
    int left = 0;
    int right = seq->count - 1;
    
    while (left < right) {
        if (seq->elements[left] % 2 == 0 && seq->elements[right] % 2 == 1) {
            int temp = seq->elements[left];
            seq->elements[left] = seq->elements[right];
            seq->elements[right] = temp;
        } else if (seq->elements[left] % 2 == 0) {
            right--;
        } else if (seq->elements[right] % 2 == 1) {
            left++;
        } else {
            left++;
            right--;
        }
    }
}

連結リストの範囲削除

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

void remove_in_range(ListNode* head, int lower_bound, int upper_bound) {
    ListNode* current = head;
    while (current->next != NULL) {
        if (current->next->data > lower_bound && current->next->data < upper_bound) {
            ListNode* target = current->next;
            current->next = target->next;
            free(target);
        } else {
            current = current->next;
        }
    }
}

昇順連結リストの降順マージ

ListNode* merge_decreasing(ListNode* list_a, ListNode* list_b) {
    ListNode dummy;
    ListNode* tail = &dummy;
    
    ListNode* ptr_a = list_a->next;
    ListNode* ptr_b = list_b->next;
    
    while (ptr_a && ptr_b) {
        if (ptr_a->data >= ptr_b->data) {
            tail->next = ptr_a;
            ptr_a = ptr_a->next;
        } else {
            tail->next = ptr_b;
            ptr_b = ptr_b->next;
        }
        tail = tail->next;
    }
    
    tail->next = ptr_a ? ptr_a : ptr_b;
    return dummy.next;
}

文字種別によるリスト分割

void categorize_nodes(ListNode* source, ListNode* digits_head, 
                     ListNode* letters_head, ListNode* others_head) {
    ListNode* src_ptr = source->next;
    ListNode* digit_tail = digits_head;
    ListNode* letter_tail = letters_head;
    ListNode* other_tail = others_head;
    
    while (src_ptr) {
        if (isdigit(src_ptr->data)) {
            digit_tail->next = src_ptr;
            digit_tail = src_ptr;
        } else if (isalpha(src_ptr->data)) {
            letter_tail->next = src_ptr;
            letter_tail = src_ptr;
        } else {
            other_tail->next = src_ptr;
            other_tail = src_ptr;
        }
        src_ptr = src_ptr->next;
    }
    
    digit_tail->next = NULL;
    letter_tail->next = NULL;
    other_tail->next = NULL;
}

多項式の次数別分割

typedef struct PolyNode {
    int coefficient;
    int degree;
    struct PolyNode* next;
} PolynomialNode;

void separate_by_degree(PolynomialNode* poly, PolynomialNode* odd_head, 
                       PolynomialNode* even_head) {
    PolynomialNode* current = poly->next;
    PolynomialNode* odd_tail = odd_head;
    PolynomialNode* even_tail = even_head;
    
    while (current) {
        if (current->degree % 2 == 0) {
            even_tail->next = current;
            even_tail = current;
        } else {
            odd_tail->next = current;
            odd_tail = current;
        }
        current = current->next;
    }
    
    odd_tail->next = NULL;
    even_tail->next = NULL;
}

配列の巡回シフト

void rotate_left(ArraySequence* seq, int positions) {
    positions %= seq->count;
    if (positions == 0) return;
    
    // 前半部分反転
    for (int i = 0; i < positions / 2; i++) {
        int temp = seq->elements[i];
        seq->elements[i] = seq->elements[positions - 1 - i];
        seq->elements[positions - 1 - i] = temp;
    }
    
    // 後半部分反転
    for (int i = 0; i < (seq->count - positions) / 2; i++) {
        int temp = seq->elements[positions + i];
        seq->elements[positions + i] = seq->elements[seq->count - 1 - i];
        seq->elements[seq->count - 1 - i] = temp;
    }
    
    // 全体反転
    for (int i = 0; i < seq->count / 2; i++) {
        int temp = seq->elements[i];
        seq->elements[i] = seq->elements[seq->count - 1 - i];
        seq->elements[seq->count - 1 - i] = temp;
    }
}

後ろからk番目ノードの検索

int find_kth_from_end(ListNode* head, int k) {
    ListNode* fast = head->next;
    ListNode* slow = head->next;
    
    // fastポインタをkステップ進める
    for (int i = 0; i < k; i++) {
        if (!fast) return -1;  // リスト長がk未満
        fast = fast->next;
    }
    
    // 両ポインタを同時に移動
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    return slow->data;
}