線形リストの基礎と実装：配列とリンクリストの比較

2.1 線形リストの定義と基本操作

2.1.1 線形リストの定義

線形リストとは、同一データ型を持つn個のデータ要素からなる有限の順序付き集合である。nを表の長さと呼び、n=0のとき空の線形リストとなる。線形リストをLとすると、一般的にL=(a1, a2, ..., an)と表される。

ここでa1は唯一の「最初」のデータ要素（先頭要素）、anは「最後」のデータ要素（末尾要素）である。最初の要素を除き、各要素はただ一つの直前要素を持ち、最後の要素を除き、各要素はただ一つの直後要素を持つ。

線形リストは線形順序を持つ論理構造である。

線形リストの特徴は以下の通り：

  • 要素数が有限である。
  • 要素は論理的な順序性を持ち、順序が決まっている。
  • 全要素は単独のデータ要素である。
  • 全要素のデータ型が同じであり、各要素が同じ記憶容量を占める。
  • 要素は抽象性を持ち、要素間の論理関係だけを扱い、具体的な内容は考慮しない。

線形リストは論理構造であり、要素間の一対一の隣接関係を表す。一方、順序表とリンクリストは記憶構造であり、混同しないよう注意が必要である。

2.1.2 線形リストの基本操作

データ構造の基本操作は、その中核となる最も基本的な操作を指す。複雑な操作は基本操作を組み合わせて実現できる。

  • InitList(&L): 線形リストを初期化し、空のリストを生成する。
  • Length(L): リストの長さを返す。
  • LocateElem(L, e): 値をキーに検索し、該当する要素の位置を返す。
  • GetElem(L, i): 位置を指定して要素の値を取得する。
  • ListInsert(&L, i, e): 指定位置iに要素eを挿入する。
  • ListDelete(&L, i, &e): 位置iの要素を削除し、その値をeに格納する。
  • PrintList(L): 全要素を順に出力する。
  • Empty(L): リストが空かどうかを判定する。
  • DestroyList(&L): リストを破棄し、占有メモリを解放する。

リスト自体を変更する操作（初期化、挿入、削除、破棄）ではパラメータに「&」を用いる点に注意する。

2.2 線形リストの順序表現

2.2.1 順序表の定義

線形リストを順序記憶したものを順序表と呼ぶ。

これはアドレスが連続した記憶領域を用いてデータ要素を格納し、論理的に隣接する要素が物理的にも隣接するようにする。

先頭要素は先頭アドレスに格納され、i番目の要素の直後にi+1番目の要素が続く。要素の位置を位順と呼ぶ。

順序表では、要素の論理的な順序と物理的な格納順序が一致する。

先頭アドレスをLOC(A)、各データ型のサイズをsizeof(ElemType)とすると、各要素のアドレスはLOC(A) + (i-1) * sizeof(ElemType)で計算できる。このため、任意の要素に直接アクセスできる（ランダムアクセス）。

配列を用いて実装されることが多い。要素の位順は1から始まり、配列の添字は0から始まることに注意する。

静的割り当てによる順序表の定義：

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int length; // 現在の長さ
} SqList;

動的割り当てによる順序表の定義：

#define InitSize 100
typedef struct {
    ElemType *data; // 動的配列へのポインタ
    int maxSize;    // 最大容量
    int length;     // 現在の長さ
} SqList;

C言語での初期化例：L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);

順序表の利点：ランダムアクセスが可能（O(1)）、記憶密度が高い。欠点：挿入・削除時に多くの要素を移動する必要がある、連続した記憶領域が必要。

2.2.2 順序表の基本操作（疑似コード）

初期化

void InitList(SqList &L) {
    L.length = 0;
}

挿入操作

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MaxSize) return false;
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}
// 時間計算量：最良O(1)、最悪O(n)、平均O(n)

削除操作

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}
// 時間計算量：最良O(1)、最悪O(n)、平均O(n)

値による検索

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) return i + 1;
    }
    return 0;
}
// 時間計算量：最良O(1)、最悪O(n)、平均O(n)

2.3 線形リストのチェーン表現

2.3.1 単一リンクリストの定義

線形リストをチェーン記憶したものを単一リンクリストと呼ぶ。これは任意の記憶領域を用い、各ノードにデータと後続ノードへのポインタを格納する。

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

リンクリストは順序表と異なり、ランダムアクセスはできない。先頭から順にたどる必要がある。

先頭ポインタ（Lまたはhead）がリストの先頭を指す。空リストではNULLとなる。操作の便宜上、先頭にダミーノード（ヘッダノード）を追加することが多い。ヘッダノードのデータ領域は通常使わない。

ヘッダノードの利点：先頭での操作が他の位置と統一できる、空リストと非空リストの扱いが統一できる。

2.3.2 単一リンクリストの基本操作
// 初期化（ヘッダノードあり）
bool InitList(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (!L) return false;
    L->next = NULL;
    return true;
}

// 位置による検索（ヘッダノードあり）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    int j = 0;
    LNode *p = L;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
} // O(n)

// 値による検索
LNode* LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
} // O(n)

// 長さの取得
int Length(LinkList L) {
    int len = 0;
    LNode *p = L->next;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
} // O(n)

// 指定ノードの後に挿入（後続挿入）
bool InsertNextNode(LNode *p, int e) {
    if (!p) return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 挿入操作（ヘッダノードあり）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) return false;
    LNode *p = GetElem(L, i - 1);
    if (!p) return false;
    return InsertNextNode(p, e);
} // O(n)

// 指定ノードの前に挿入（前方挿入）
bool InsertPriorNode(LNode *p, int e) {
    if (!p) return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

// 削除操作（ヘッダノードあり）
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) return false;
    LNode *p = GetElem(L, i - 1);
    if (!p || !(p->next)) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
} // O(n)

// 末尾挿入法によるリスト生成
LinkList List_TailInsert(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r = L;
    int x;
    while (scanf("%d", &x) == 1) {
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return L;
}

// 先頭挿入法によるリスト生成
LinkList List_HeadInsert(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    int x;
    while (scanf("%d", &x) == 1) {
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
    }
    return L;
}
2.3.3 双方向リンクリスト

各ノードが直前要素と直後要素へのポインタ（prior, next）を持つ。先頭ノードのpriorと末尾ノードのnextはNULLとなる。

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

挿入操作（pの後にsを挿入）：

s->next = p->next;
if (p->next) p->next->prior = s;
s->prior = p;
p->next = s;

削除操作（pの直後qを削除）：

p->next = q->next;
if (q->next) q->next->prior = p;
free(q);
2.3.4 循環リンクリスト

循環単一リンクリスト：末尾ノードのnextが先頭ノード（またはヘッダノード）を指す。空リストの判定条件は、L->next == L となる。

循環双方向リンクリスト：末尾のnextが先頭を、先頭のpriorが末尾を指す。空リストの判定条件は、L->next == L && L->prior == L となる。

2.3.5 静的リンクリスト

配列を用いてリンクリストを実現する。各要素はデータと次の要素の配列添字（カーソル）を持つ。終端は next = -1 で示す。

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];
2.3.6 順序表とリンクリストの比較
  • アクセス方式：順序表はランダムアクセス可能（O(1)）、リンクリストは順次アクセスのみ（O(n)）。
  • 物理構造：順序表は連続、リンクリストは不連続。
  • 挿入・削除：順序表はO(n)で要素移動が必要、リンクリストはO(1)でポインタ変更のみ（ただし検索にO(n)）。
  • 記憶領域：順序表は事前割り当てが必要で拡張時に全移動、リンクリストは動的確保可能だがポインタ分のオーバーヘッドがある。

タグ: データ構造 線形リスト 順序表 リンクリスト 単一リンクリスト

7月31日 02:50 投稿

ホットタグ

©2026 異端開発室