数据结构之链表

链表

1. 单链表

1.1 概念与结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.1.1 结点

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

1.1.2 链表的性质

• 链式机构在逻辑上是连续的，在物理结构上不一定连续。
• 结点一般是从堆上申请的。
• 从堆上申请来的空间，每次申请的空间可能连续，可能不连续。

struct SlistNode {
    int data; // 结点数据
    struct SlistNode* next; // 指针变量用保存下一个结点的地址
};

1.1.3 链表的打印

给定的链表的结构，实现链表从头到尾的打印

void SLTPrint(SLTNode* phead) {
    SLTNode* pcur = phead;
    while (pcur) {
        printf("%d", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

1.2 实现单链表

typedef int SLTDataType;
typedef struct SListNode {
    SLTDataType data; // 结点数据
    struct SListNode* next; // 指针保存下一个结点的地址
} SLTNode;

void SLTPrint(SLTNode* phead); // 头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos);
// 销毁链表
void SListDestroy(SLTNode** pphead);

1.3 链表的分类

链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

• 单向或者双向
• 带头或不带头
• 循环或不循环 （2 x 2 x 2）=8 种

2. 双向链表

2.1 概念与结构

2.2 实现双链表

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next; // 指针保存下一个结点的地址
    struct ListNode* prev; // 指针保存前一个结点的地址
    LTDataType data;
} LTNode;

void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
// 在 pos 位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

3. 顺序表与链表的分析