单链表(C语言)¶

本文介绍如何使用 C 语言实现 单链表 ( single linked list )：定义链表节点 ( node ) 以及链表结构体，实现添加、删除、查找、遍历等主要操作，附以结构清晰的源码以及详实的 文字说明 ，希望对 初学者 有所帮助。

结构定义¶

先定义链表节点 ( node )，以存储整数元素( int )为例：

typedef int Element;

typedef struct node Node;
typedef Node* NodePtr;

struct node {
    Element element;
    NodePtr next;
};

第 1 行，为 int 类型定义一个别名，为 Element ；第 3-4 行，为结构体及其指针分别定义别名；第 6-9 行，定义链表节点 结构体 ，包含两个字段：

element ，节点 存储元素 ；
next ， 后向指针 ，指向下一个节点；

接着，定义一个结构体表示链表：

typedef struct {
    NodePtr head;
    NodePtr tail;
} List, *ListPtr;

该结构体包含两个指针：

head ，指向链表 头节点 ；
tail ，指向链表 尾节点 ：

操作定义¶

初始化¶

init 函数负责初始化链表，将头、尾指针置为 NULL ，表示链表为空：

void init(ListPtr l) {
    l->head = l->tail = NULL;
}

动态创建¶

create 函数动态创建新链表，即为链表结构体分配内存并完成初始化：

ListPtr create() {
    ListPtr l = (ListPtr)malloc(sizeof(List));
    if (l != NULL) {
        init(l);
    }

    return l;
}

这样一来，创建链表的方式有两种。①声明链表结构体并初始化：

List l;
init(&l);

// do something with list
add(&l, 1);

②动态创建链表结构体：

ListPtr l = create();

// do something with list
add(l, 1);

具体采用哪种方式视情况而定。

空判断¶

isEmpty 函数判断链表是否为空，只需判断头指针是否为 NULL ：

int isEmpty(ListPtr l) {
    return l->head == NULL;
}

链表头¶

head 函数返回链表头指针：

NodePtr head(ListPtr l) {
    return l->head;
}

链表尾¶

tail 函数返回链表尾指针：

NodePtr tail(ListPtr l) {
    return l->tail;
}

查找¶

查找操作需要遍历整个链表，逐一验证。

头文件为节点指针定义一个别名，表示当前遍历到的位置：

typedef NodePtr Position;

find 函数在链表中查找元素 x 并返回其节点指针：

Position find(ListPtr l, Element x) {
    Position p;
    for (p = l->head; p != NULL; p = p->next) {
        if (p->element == x) {
            return p;
        }
    }

    return NULL;
}

第 2-7 行， for 循环遍历链表每个节点；
第 4-6 行，如节点存储元素为 x ，则返回节点指针；
第 9 行，循环结束，没有找到元素 x ，返回 NULL ；

删除¶

delete 函数从链表 l 中找到元素 x 并将其删除：

void delete(ListPtr l, Element x) {
    // find x and trace previous one at the same time
    Position prev, p;
    for (prev = NULL, p = l->head; p != NULL; prev = p, p = p->next) {
        if (p->element == x) {
            break;
        }
    }

    // find nothing
    if (p == NULL) {
        return;
    }

    // delete it
    if (p == l->head) {
        l->head = p->next;
    }
    if (p == l->tail) {
        l->tail = prev;
    }
    if (prev != NULL) {
        prev->next = p->next;
    }
    free(p);
}

删除元素前，先遍历链表每个节点，找出元素 x 所在节点。由于删除节点需要调整前一节点的后向指针，因此遍历时， 需跟踪前节点 。

第 3 行，定义两个游标 ( cursor )变量， p 表示当前节点， prev 表示其前节点；
第 4-8 行，循环遍历每个节点，如果元素为 x ，则跳出；
- 初始条件 ：当前节点 p 为头节点，前节点为空( NULL )；
- 循环条件 ：当前节点非空；
- 迭代：跳到下一节点，跳之前先更新前节点；
第 11-13 行，如元素 x 不存在，直接返回；
第 16-25 行，删除元素 x 所在节点 p ，注意 特殊情况 处理：
- 如果被删除节点为头节点，调整链表头( 16-18 )；
- 如果被删除节点为尾节点，调整链表尾( 19-21 )；
- 如果前一节点存在，调整其后向指针( 22-24 )；

添加¶

add 函数将元素 x 添加到链表 l 节点 p 之后( p 为 NULL 则添加到链表头)：

int add(ListPtr l, Position p, Element x) {
    // allocate memory for element node
    Position node = malloc(sizeof(Node));
    if (node == NULL) {
        return -1;
    }

    // fill element value
    node->element = x;

    if (p == NULL) {
        // add to head
        node->next = l->head;
        l->head = node;
    } else {
        node->next = p->next;
        p->next = node;
    }

    if (l->tail == p) {
        l->tail = node;
    }

    return 0;
}

第 3-6 行，为新节点分配内存，失败则返回 -1 ；
第 9 行，将元素 x 拷贝到新节点；
第 11-14 行，添加到链表头，节点链接到元头节点之前并调整链表头；
第 16-17 行，添加到 p 之后，调整指针完成链接；
第 20-22 行，如添加至链表尾，调整尾指针；

遍历¶

由于遍历链表是一个很常用的操作，可以实现一个通用的遍历函数 traverse 。该函数遍历链表 l ，并为每个节点调用处理函数 h 。 h 为函数指针，原型在头文件中定义如下：

typedef void (*NodeHandler)(NodePtr);

traverse 函数实现如下：

void traverse(ListPtr l, NodeHandler h) {
    Position p = l->head;
    while (p != NULL) {
        Position tmp = p;
        p = p->next;
        h(tmp);
    }
}

第 2 行，定义游标变量 p ，从链表头开始遍历；
第 3-7 行， while 当 p 非 NULL 时不断循环；
- 暂存当前节点( 4 )；
- 跳到下一节点( 5 )；
- 调用处理函数处理当前节点( 6 )；

清空¶

clear 函数将链表 l 清空，释放所有链表节点：

void clear(ListPtr l) {
    traverse(l, (NodeHandler)free);
    l->head = l->tail = NULL;
}

第 2 行，调用 traverse 函数遍历链表，为每个节点调用 free 库函数，释放内存；
第 3 行，链表清空后，将头尾指针置为 NULL ，表示链表为空；

反转¶

reverse 函数将链表 l 所有节点反转，即前后颠倒：

void reverse(ListPtr l) {
    Position h1 = l->head;
    Position h2 = NULL;

    while (h1 != NULL) {
        Position n = h1;
        h1 = h1->next;

        n->next = h2;
        h2 = n;
    }

    l->tail = l->head;
    l->head = h2;
}

将原链表元素从头部逐一取出并插到新链表的最前面，所得链表就是原链表的倒置：

第 2-3 行，定义两个临时链表头， h1 为原链表， h2 为空的新链表；
第 5-11 行， while 遍历原链表每个节点，并将其插到 h2 最前面；
第 13-14 行，倒置后原链表头成了链表尾，原链表尾即 h2 ，成了链表头；

打印¶

print 函数输出链表 l 所有元素， hint 为一个可选的输出提示：

void print(ListPtr l, char *hint) {
    printf("%s[ ", hint);
    traverse(l, printNode);
    printf("]\n");
}

第 2 行，先打印提示以及左方括号 [ ；
第 3 行，调用 traverse 函数遍历链表，为每个节点调用 printNode 打印函数；

printNode 函数为 print 的辅助函数，负责打印一个节点：

void printNode(NodePtr n) {
    printf("%d ", n->element);
}

销毁¶

destroy 函数销毁链表 l ：

void destroy(ListPtr l) {
    clear(l);
    free(l);
}

第 2 行，先清空链表，释放所有节点；
第 3 行，释放链表结构体；

应用¶

#include <stdio.h>
#include "single-linked-list.h"

int main(int argc, char *argv[]) {
    ListPtr l = create();
    if (l == NULL) {
        return -1;
    }

    print(l, "after init: ");

    add(l, NULL, 1);
    add(l, NULL, 2);
    add(l, NULL, 3);
    print(l, "after add 1, 2, 3 to head: ");

    add(l, tail(l), 4);
    add(l, tail(l), 5);
    add(l, tail(l), 6);
    print(l, "after add 4, 5, 6 to tail: ");

    Position p = find(l, 1);
    add(l, p, 0);
    print(l, "after add 0 after 1: ");

    reverse(l);
    print(l, "after reverse: ");

    delete(l, 0);
    print(l, "after delete 0: ");

    clear(l);
    print(l, "after clear: ");

    destroy(l);

    return 0;
}

进入源码目录，执行 make run 即可运行例子程序：

$ make run
gcc -o demo single-linked-list.c demo.c
./demo
after init: [ ]
after add 1, 2, 3 to head: [ 3 2 1 ]
after add 4, 5, 6 to tail: [ 3 2 1 4 5 6 ]
after add 0 after 1: [ 3 2 1 0 4 5 6 ]
after reverse: [ 6 5 4 0 1 2 3 ]
after delete 0: [ 6 5 4 1 2 3 ]
after clear: [ ]

下一步¶

订阅更新，获取更多学习资料，请关注我们的微信公众号：

小菜学编程