【数据结构】单链表

• 链式存储定义

为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息（地址）

• 单链表

1. 线性表的链式存储结构中，每个结点中只包含一个指针域，这样的链表叫单链表
2. 通过每个结点的指针域将线性表的数据元素按照其逻辑次序链接在一起

• 单链表的插入操作

 操作步骤：

1. 找到插入位置的前一个结点（pCurrent）
2. 将新结点指针域（NewNode->next）指向 pCurrent->next 
3. 将 pCurrent 的指针域（pCurrent->next）指向新结点（NewNode）

• 为什么不先链接 pCurrent 和 NewNode ？

因为链表是通过指针去访问下一个数据元素的，pCurrent->next = NewNode 导致本来能找到下一个元素的指针被覆盖

如果先链接 pCurrent 和 NewNode ，则新结点的指针域指向就会出现问题，无法链接链表后面的内容。

• 单链表删除操作

操作步骤：

1. 找到要被删除结点的前一个结点（pCurrent）
2. 创建新结点 DelNode 存储 pCurrent 结点的下一个位置（pCurrent->next），也就是需要删除的结点
3. 将 pCurrent 的指针域（pCurrent->next）指向 需要删除结点的下一个位置（DelNode->next）
4. 释放需要删除的结点空间 

---

C 语 言 实 现 单 链 表

• 链表框架

// 链表结点
typedef struct LINKNODE{
    void* data;               // 无类型指针，可以指向任何数据类型
    struct LINKNODE* next;    // 结点指针域
}LinkNode;                    
 
 
// 链表结构体
typedef struct LINKLIST {
    LinkNode* head;           // 头结点
    int size;                 // 链表长
}LinkList;
 
// 打印函数指针
typedef void(*PRINTLINKNODE)(void*);
 
// 初始化链表
LinkList* Init_LinkList();
 
// 指定位置插入数据
void Insert_LinkList(LinkList* list, int pos, void* data);
 
// 删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
 
// 获取链表的长度
int Size_LinkList(LinkList* list);
 
// 按照 数据 查找
int Find_LinkList(LinkList* list, void* data);
 
// 返回第一个结点
void* Front_LintList(LinkList* list);
 
// 打印
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
 
// 释放链表内存
void FreeSpace_LinkList(LinkList* list);

• 链表实现

// 初始化链表
LinkList* Init_LinkList(){ 
    LinkList* list = (LinkList*)malloc(sizeof(LinkList));
    list->size = 0;
 
    // 头结点 (不保存数据) (为了方便插入)
    list->head = (LinkNode*)malloc(sizeof(LinkNode));
    list->head->data = NULL;
    list->head->next = NULL;
 
    return list;
}
 
// 指定位置插入数据
void Insert_LinkList(LinkList* list, int pos, void* data){ 
 
    if (list == NULL) return;
 
    if (data == NULL) return;
 
    // 友好处理，pos 越界
    if (pos < 0 || pos > list->size) {
        pos = list->size;
    }
 
    // 创建新的结点
    LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
 
    NewNode->next = NULL;
    NewNode->data = data;
 
    // 插入结点 pos = 2，就要找 1 这个位置
    // 找结点
    // 辅助指针变量
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos; i++) {
        pCurrent = pCurrent->next;
    } // 找到 
 
    // 新结点插入链表
    NewNode->next = pCurrent->next;
    
    pCurrent->next = NewNode;
 
    // 更新长度
    list->size++;
}
 
// 删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos){ 
 
    if (list == NULL) return;
    
    if (pos < 0 || pos > list->size) return;
 
    // pos 2 , 找到前一个结点
 
    LinkNode* pCurrent = list->head;
 
    // 查找删除结点的前一个结点
    for (int i = 0; i < pos; i++) {
        pCurrent = pCurrent->next;
    }
 
    LinkNode* DelNode = pCurrent->next;
 
    pCurrent->next = DelNode->next;
 
    // 释放删除节点
    free(DelNode);
    DelNode = NULL;
 
    // 更新长度
    list->size--;
}
 
// 获取链表的长度
int Size_LinkList(LinkList* list){ 
    return list->size;
}
 
// 查找
int Find_LinkList(LinkList* list, void* data){ 
    
    int pos = -1;
 
    if (list == NULL) return pos;
    if (data == NULL) return pos;
 
    LinkNode* pCurrent = list->head->next;
 
    while (pCurrent != NULL) {
        if (pCurrent->data == data) {
            break;
        }
        pos++;
        pCurrent = pCurrent->next;
    }
    return pos;
}
 
// 返回第一个结点
void* Front_LintList(LinkList* list){ 
    return list->head->next->data; // 返回数据域
}
 
// 打印
void Print_LinkList(LinkList* list, PRINTLINKNODE print){ 
    
    if (list == NULL) return;
 
    LinkNode* pCurrent = list->head->next;
 
    while (pCurrent != NULL) {
        print(pCurrent->data);
        pCurrent = pCurrent->next;
    }
}
 
// 释放链表内存
void FreeSpace_LinkList(LinkList* list){ 
 
    if (list == NULL) return;
 
    // 辅助结点
    LinkNode* pCurrent = list->head;
 
    while (pCurrent != NULL) {
        // 缓存下一个结点
        LinkNode* pNext = pCurrent->next;
        free(pCurrent);
        pCurrent = pNext;
    }
 
    // 释放链表内存
    free(list);
}

测试代码：

void test() {
 
    LinkList* list;
    list = Init_LinkList();
 
    Person p1 = { "aaa", 19, 99 };
    Person p2 = { "bbb", 20, 98 };
    Person p3 = { "ccc", 21, 97 };
    Person p4 = { "ddd", 22, 96 };
    Person p5 = { "eee", 23, 95 };
 
    // 插入链表
    Insert_LinkList(list, 0, &p1);
    Insert_LinkList(list, 0, &p2);
    Insert_LinkList(list, 0, &p3);
    Insert_LinkList(list, 0, &p4);
    Insert_LinkList(list, 0, &p5); // pos = 0 头插效果
 
    // 打印
    Print_LinkList(list, MyPrint);
 
    // 获取长度
    printf("单链表当前长度为: %d\n", Size_LinkList(list)); // 5
 
    printf("-----------------------\n");
 
    // 删除 
    RemoveByPos_LinkList(list, 1);
 
    // 打印
    Print_LinkList(list, MyPrint); // ddd 被删
 
    // 获取长度
    printf("单链表当前长度为: %d\n", Size_LinkList(list)); // 4
 
    // 查找
    Person find_p = { "aaa", 19, 99 };
 
    int pos = Find_LinkList(list, &find_p);
    printf("find_p位置: %d\n", pos); // 3
 
    // 返回第一个结点数据，强制转换成 Person*，结点类型 Person
    printf("返回第一个结点数据\n");
    Person* FirstNode = (Person*)Front_LintList(list);
    
    printf("name: %s age: %d score: %d\n", FirstNode->name, FirstNode->age, FirstNode->score);
 
    // 销毁
    FreeSpace_LinkList(list);
}

运行结果：