順序(Sequential)

• 存取元素複雜度為O(1)；插入、刪除複雜度為O(N)

typedef struct {
    ElemType data[MAXSIZE];
    int length;
} SqList;

int GetElem(SqList L, int i, ElemType *e) {
    *e = L.data[i - 1];
    return 0;
}

int ListInsert(SqList *L, int i, ElemType e) {
    int k = 0;
    if (i <= L->length) {
        // 往後移
        for (k = L->length - 1; k >= i - 1; k--)
            L->data[k + 1] = L->data[k];
    }

    L->data[i - 1] = e;
    L->length++;
    return 0;
}

int ListDelete(SqList *L, int i, ElemType *e) {
    int k = 0;
    *e = L->data[i - 1];
    if (i < L->length) {
        // 往前移
        for (k = i; k < L->length; k++)
            L->data[k - 1] = L->data[k];
    }

    L->length--;
    return 0;
}

鏈結串列(Linked List)

• 存取元素複雜度為O(N)；插入、刪除複雜度為O(1)

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node;

typedef struct Node* LinkList;

// Init：
// LinkList head = malloc(sizeof(struct Node));
// head->next = NULL;
// head->data = 0;

int GetElem(LinkList L, int i, ElemType *e) {
    LinkList p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }

    *e = p->data;
    return 0;
}

int ListInsert(LinkList *L, int i, ElemType e) {
    LinkList p = *L;
    int j = 1;
    while (p->next && j < i) {
        p = p->next;
        j++;
    }

    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    // 先把s指向i+1, 再把p指向s
    s->next = p->next;
    p->next = s;
    return 0;
}

int ListDelete(LinkList *L, int i, ElemType *e) {
    LinkList p = *L;
    LinkList q = NULL;
    int j = 1;
    while (p->next && j < i) {
        p = p->next;
        j++;
    }

    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return 0;
}

int ListInvert(LinkList *L) {
    LinkList p = (*L)->next;
    (*L)->next = NULL;
    LinkList q = NULL;
    while (p) {
        q = p;
        p = p->next;
        q->next = (*L)->next;
        (*L)->next = q;
    }
    return 0;
}

靜態鏈結串列(Static Linked List)

• 針對沒有指標的高階語言

// 第一個元素的cur指向可用，最後一個元素cur指向首節點
typedef struct {
    ElemType data;
    int cur;
} StaticLinkList[MAXSIZE];

int InitList(StaticLinkList space) {
    for (i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;
    return 0;
}

int ListInsert(StaticLinkList L, int i, ElemType e) {
    k = MAXSIZE - 1;
    j = L[0].cur;
    if (j) {
        L[0].cur = L[j].cur;
        L[j].data = e;
        for (l = 1; l <= i - 1; l++)
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return 0;
    }
    return -1;
}

int ListDelete(StaticLinkList L, int i) {
    k = MAXSIZE - 1;
    for (j = 1; j <= i - 1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    L[j].cur = L[0].cur;
    L[0].cur = j;
    return 0;
}

int ListLength(StaticLinkList L) {
    j = 0;
    i = L[MAXSIZE - 1].cur;
    while (i) {
        i = L[i].cur;
        j++;
    }
    return j;
}

環狀鏈結串列(Circular Linked List)

// 用指向尾端節點來表示環狀鏈結串列，合併結果即可照著原順序
// rearA, rearB 指向最後一個節點
p = rearA->next;
rearA->next = rearB->next->next;
q = rearB->next;
rearB->next = p;
free(q);

雙向鏈結串列(Double Linked List)

typedef struct DulNode {
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode, *DulLinkList;

Insert

// s插在p後 (1, 2 可顛倒)
s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;

Delete

// 刪除p (1, 2 可顛倒)
p->prior->next = p->next;
p->next->prior = p->prior;
free(p)