数据结构与算法 - 单链表

2020-04-05 本文已影响0人 Typeco

本文首发于个人博客

对于非空的线性表和线性结构，具有以下特点：

存在唯一的一个被称作 第一个 的数据元素
存在唯一的一个被称作 最后一个 的数据元素
除了第一个元素以外，其他每个数据元素都有 一个前驱
除了最后一个元素以外，其他每个数据元素都有 一个后继

线性表是最基本也是最常用的一种线性结构，同时它也是其他数据结构的基础。尤其是 单链表 ，这篇文章主要讲述一下单链表的结构以及如何用 C语言 实现一个单链表。

单链表的实现

单链表是一种线性数据结构，我们考察的主要是它的初始化、添加、删除、遍历等方法

初始化

单向链表是由一个个节点组成的，每一个节点都包含一个数据段和指针段，数据段主要保存节点的相关信息，指针段主要保存后继节点的地址。

#define ERROR 0
#define TRUE 1
#define FAILURE 0
#define SUCCESS 1

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如 SUCCESS、FAILURE等 */
typedef int ListData;/* ListData类型根据实际情况而定，这里假设为int */

// 定义节点
typedef struct Node{
    ListData data;
    struct Node *next;
}Node;

typedef struct Node *LinkList;
// 初始化单链表
Status InitList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    return SUCCESS;
}

添加节点

既然链表的节点已经定义而且链表的数据结构已经初始化，接下来我们看看如何去添加元素，这里我们看两种情况：

不带头节点的单链表

如图所示，我们要对单链表进行插入操作的时候要进行额外判断，如果要在首元节点之前添加节点，就要挪动List指针，如果其他位置则不用。

带头节点的单链表

这里带头节点的插入就很简单了，所有的地方一视同仁，而不需要额外去操作链表的指针。PS：其中头节点中的信息我们不需要关心，因为它相当于我们默认放进去的一个节点。

所以后续我们使用的单链表默认 添加头节点。

我们要插入节点，就要对链表进行修改，那么我们需要把 链表的指针 作为参数传入。

// location from 1...
Status InsertNode(LinkList *L,int location,ListData data) {
    // 找到需要location-1位置的节点
    Node *pre = *L;
    // 因为0位置被头节点占了，所以要从1位置开始
    int currentLocation = 1;
    while (pre && currentLocation < location) {
        pre = pre->next;
        currentLocation ++;
    }
    if (!pre || currentLocation < location) return ERROR;

    // 根据data生成一个新节点
    Node *insertNode = (Node *)malloc(sizeof(Node));
    insertNode->data = data;
    // 让新节点的next 指向 pre->next
    insertNode->next = pre->next;
    // 让前一个节点的next指向新节点
    pre->next = insertNode;
    return SUCCESS;
}

此处逻辑跟图上一一对应，接下来我们要验证就要打印链表每个位置的值，我们添加一个打印的方法，我们只是打印链表，没必要把传递指针。

// 打印方法 我们不用修改链表 无需传指针
Status printList (LinkList L) {
    LinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    return SUCCESS;
}

我们验证一下：

int main(int argc, const char * argv[]) {
    LinkList L;
    Status status = InitList(&L);
    printf("s is %d\n",status);
    // 插入元素
    for (int i = 10; i >= 1; i --) {
        InsertNode(&L, 1, i);// 此处1表示，总是从头节点后面插入新节点，也就是头插法，比较简单，因为尾插法还要保留链表长度
    }
    // 打印链表
    printList(L);
    return 0;
}

打印结果如下：

删除节点

结果如我们所愿，链表创建以及插入读取都正常，接下来我们看看链表是如何删除节点的：

创建临时变量指向我们即将删除的节点，一方面为了找到下一个节点，另外一个方面为了释放内存，否则就内存泄漏了。
直接将临时变量的上一个节点直接指向临时变量的下一个节点
释放临时变量

Status DeleteNode (LinkList *L ,int location,ListData *deleteData) {
    Node *pre = *L;
    int currentLocation = 1;
    // 还是找到location-1位置的节点
    while (pre && currentLocation < location) {
        pre = pre->next;
        currentLocation++;
    }
    if (!pre || currentLocation < location) return ERROR;
    // 创建临时变量 保存即将被删除的节点
    Node *temp = pre->next;
    if (!temp) return ERROR;
    // 前驱节点指向后驱节点
    pre->next = temp->next;
    // 将我们删除的内容返回出去
    *deleteData = temp->data;
    // 释放内存
    free(temp);
    return SUCCESS;
}
//在main方法中添加如下代码验证
// 删除第五个节点
    ListData data;
    DeleteNode(&L, 5, &data);
    printf("删除第五个元素后的链表是 :\n");
    printList(L);
    printf("被删除的值是 %d\n",data);

清空单链表

指针指向首元节点 注意不是头节点 ，并将该节点释放
指针偏移到下一个节点 中间节点
释放下一个节点 中间节点
指针以此类推到 尾节点
释放 尾结点
头节点指向 NULL 此处如果不处理，头节点的 next就是 野指针了

Status clearList(LinkList *L) {
    // 由于第一个是头节点，我们从第二个节点开始删除，这个地方可以根据实际情况来
    Node *pre = (*L)->next;
    Node *nextNode;
    while (pre) {
        // 用一个临时变量保存当前要删除的节点指向的下一个节点，有点像递归的意思
        nextNode = pre->next;
        // 释放
        free(pre);
        // 将要删除的指针偏移到下一个指针
        pre = nextNode;
    }
    // 此处将头节点指向NULL ，否则就出现野指针了
    (*L)->next = NULL;
    return SUCCESS;
}

头插法初始化

根据名字就知道了，从表头处添加节点，之前一篇文章 @synchronized底层探索里的数据结构用的就是哈希表，内部就是通过头插法进行操作的。

Status InitFromHead(LinkList *L,int n) {
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    Node *pre = *L;
    for (int i = 1; i <= n; i ++) {
        Node *temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->next = pre->next;
        pre->next = temp;
    }
    return SUCCESS;
}

// 在main中添加如下，会倒序打印30---1 就是头插法
    clearList(&L);
    InitFromHead(&L, 30);
    printf("链表是 :\n");
    printList(L);

上述打印结果会从30倒序到1，足以证明是头插法。

尾插法初始化

尾插法就是从链表尾部依次插入数据，这样就跟我们平常的数组的逻辑差不多了，相当于addObject,这里跟头插法不同的是，头插法依赖头节点，此处依赖尾节点，所以我们要用一个临时的指针指向尾结点并依次保存。

Status InitFromTail(LinkList *L,int n) {
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    // 初始化的时候尾结点就是头节点
    Node *tail = *L;
    for (int i = 1; i <= n; i ++) {
        Node *temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->next = NULL;
        tail->next = temp;
        // 尾节点偏移
        tail = tail->next;
    }
    return SUCCESS;
}
// 在main函数中添加如下代码
    clearList(&L);
    InitFromTail(&L, 30);
    printf("链表是 :\n");
    printList(L);

但是细心的观察你会发现，这个往链表尾部添加节点的方法的关键点在于先要找到尾节点，无非是通过循环直到找到一个节点的 next 是 NULL ,对于这个方法如果要初始化一个包含100个数字的的链表就要循环1+2+3+....+100 = 5050次，而用它上面那个函数添加的话只用循环100次，这个函数的时间复杂度是n*(n+1)/2 即是 O(n^2) 而上面那个是 O(n),所以这个方法只能针对初始化之后需要从尾部额外添加一个节点使用。

单向循环链表

看到 循环 两个字我们就大概知道了，就是所有的节点组成一个 闭合的环，看起来应该是这样：

因为上面的单链表我们选用了使用头节点的方式，下面我没使用不带头节点的方式实现单向循环链表。具体以代码体现，其原理跟单向链表差不多，有不清楚的结合单向链表的图连接首位即可。

初始化

这里我们采用符合我们正常逻辑的尾插法来实现单向循环链表的初始化，因为我们使用不带头节点的方式，这里我们就要对链表的首元节点进行判断：

首元节点不存在，初始化并创建赋值给链表地址
存在即找到当前链表的尾节点，依次插入后续节点

// 输入的方式尾插法创建单向循环链表
Status InitList(LinkList *L) {
    int number;
    Node *tail = NULL;
    while (1) {
        scanf("%d",&number);
        // 输入0结束创建
        if (number == 0) break;
        if (*L == NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if (*L == NULL)return ERROR;
            (*L)->data = number;
            (*L)->next = *L;
            tail = *L;
        } else {
            //找尾结点  方法1
            for (tail = *L; tail->next != *L; tail = tail->next);
            Node *temp = (Node *)malloc(sizeof(Node));
            if (!temp) return ERROR;
            temp->data = number;
            temp->next = *L;
            tail->next = temp;
            if (tail == NULL) return ERROR;
            //方法2
            Node *node = (Node *)malloc(sizeof(Node));
            if (!node) return ERROR;
            node->data = number;
            node->next = *L;
            tail->next = node;
            tail = tail->next;
        }
    }
    return SUCCESS;
}

上述我们找尾节点展示了两种方法：

方法①：每次从首元节点依次循环直至找到 节点的next = 首元节点 即是当前的尾结点。
方法②：用一个临时变量指向尾节点（初始化的时候尾结点指向首元节点），每次插入新节点，临时变量进行偏移继续指向尾结点。

显然方法②的时间复杂度更小一点 O(n)，方法①每插入一个新数据都要循环遍历整个链表其时间复杂度是O(n^2) 。

插入节点

插入节点的逻辑其实跟单向链表差不多，无非就是指针的一些指向，但是这里要注意一些细节点：

插入新的首元节点，就要找到尾节点，然后尾节点指向新首元节点，新首元节点指向原首元节点，链表地址指向新首元节点。
其他地方同单向链表逻辑

void InsertNode(LinkList *List,int location, ListData data) {
    // 创建待插入节点
    Node *insertNode = (Node *)malloc(sizeof(Node));
    if (insertNode == NULL) return;
    insertNode->data = data;
    insertNode->next = NULL;
    if (location == 1) {
        // 找到最后一个节点即尾结点
        Node *tail = NULL;
        for (tail = *List; tail->next != *List; tail = tail->next);
        insertNode->next = tail->next;
        tail->next = insertNode;
        *List = insertNode;
    } else {
        Node *preNode = *List;
        // 找到插入位置的的前一个节点
        for (int i = 1; preNode->next != *List && i != location-1; preNode = preNode->next,i++);
        insertNode->next = preNode->next;
        preNode->next = insertNode;
    }
}

删除节点

删除节点同样我们也要对首元节点的处理单独拎出来：

Status DeleteNode(LinkList *List,int location,ListData *deleteData) {
    Node *temp = *List;
    if (temp == NULL) return ERROR;
    Node *target;
    if (location == 1) {// 删除首元节点
        // 找到尾节点
        for (target = *List; target->next != *List; target = target->next);
        if (target == *List) {
            target->next = NULL;
            *List = NULL;
            *deleteData = temp->data;
            free(target);
            return SUCCESS;
        }
        target->next = temp->next;
        *List = target->next;
        *deleteData = temp->data;
        free(temp);
    } else {
        // 找到待删除节点的前一个节点
        target = *List;
        int i;
        for (i = 1,target = *List; i < location-1; i ++) {
            target = target->next;
        }
        Node *deleteNode = target->next;
        target->next = deleteNode->next;
        *deleteData = deleteNode->data;
        free(deleteNode);
    }
    return SUCCESS;
}

总结

至此我们 单链表 、单向循环链表 的一系列方法都已实现，使用头节点、不使用头节点 的方式都有，最后对比我们发现使用头节点让我们对于处理链表的插入数据以及删除数据的处理会更简单，因为没有针对首节点的单独处理，针对此大家可以根据具体情况自行斟酌。其实还有很多方法和实现等着你去发掘，希望这篇文章能将单链表的概念和实现讲清楚。

数据结构与算法 - 单链表

单链表的实现

初始化

添加节点

删除节点

清空单链表

头插法初始化

尾插法初始化

单向循环链表

初始化

插入节点

删除节点

总结

猜你喜欢

热点阅读