数据结构之链表 | 小尹的博客

概述

在计算机中用一组任意的，可能是连续的，也可能是不连续的存储单元存储线性表的数据元素，称为链式存储结构。和顺序表相比的优势（使用场景）：

• 当插入或删除元素较多时
• 不确定元素个数时

因为不确定链式存储结构的存储单元是否连续，所以链表的结点不可以随机存取。

链表中的数据是以结点来表示的，每个结点的构成：

• 数据域(存储数据元素的映像)
• 指针域(存储后继元素存储位置)

单链表

n个结点链成的一个链表，当每个结点中只包含一个指针域时，称为单链表

• 开始结点无直接前趋：头指针head指向开始结点
• 终端结点无后继结点：终端结点指针域为NULL

因此，一个单链表可由头指针唯一确定，并且可以用头指针的名字命名。

• 定义一个单链表

typedef char Datatype;

//定义结点类型
typedef struct node
{
    Datatype data;      //数据域
    struct node *next;  //指针域
} ListNode;

//定义指向单链表的指针类型
typedef ListNode *LinkList;

• 头插法创建单链表

将新结点插入到当前链表表头，直到读入结束标志，如图所示

代码如下，这里指定回车为结束标志

LinkList CreateListF()
{
    //声明头指针，结点类型变量, 数据变量
    LinkList head;
    ListNode *p;
    Datatype ch;
    //置空单链表
    head = NULL;
    //新增结点
    while (1)
    {
        ch = getchar();
        if (ch == '\n')
        {
            break;
        }
        //给ListNode动态分配一块空间
        p = (ListNode *)malloc(sizeof(ListNode));
        p->data = ch;
        //新增结点指针域指向下一节点
        p->next = head;
        //新增结点成为头节点
        head = p;
    }
    return head;
}

• 尾插法创建单链表

需要一个尾指针rear，始终指向链表的尾结点，如图

代码如下

LinkList CreateListR()
{
    //声明头指针和尾指针，结点类型变量，数据变量
    LinkList head, rear;
    ListNode *p;
    char ch;
    //置空单链表
    head = NULL;
    rear = NULL;
    //新增结点
    while (1)
    {
        ch = getchar();
        if (ch == '\n')
        {
            break;
        }
        //给ListNode动态分配一块空间
        p = (ListNode *)malloc(sizeof(ListNode));
        p->data = ch;
        //头指针指向第一个输入的结点
        if (head == NULL)
        {
            head = p;
        }
        //上一个新增结点的指针域指向本次新增结点
        else
        {
            rear->next = p;
        }
        //尾指针始终指向最后输入的那个结点
        rear = p;
    }
    //终端结点指针域置空
    if (rear != NULL)
    {
        rear->next = NULL;
    }
    return head;
}

• 查找单链表第i个结点，时间复杂度为O(n)

//返回head指向的单链表的第i个结点
ListNode *GetNode(LinkList head, int i)
{
    ListNode *p = head;
    int j = 0;
    //循环向后查找结点，直到第i个结点或者链表尾(NULL)
    while (++j < i && p)
    {
        p = p->next;
    }
    //返回NULL表示索引i超出了链表范围，否则返回第i个结点
    return j == i ? p : NULL;
}

• 查找某个值的结点位置，同样的，时间复杂度为O(n)

//返回head指向的单链表的第一个等于k的结点
ListNode *LocateNode(LinkList head, Datatype k)
{
    ListNode *p = head;
    //循环向后查找结点，直到找到第一个等于k的结点或者链表尾(NULL)
    //注意：while条件里需先对p判空，否则当p为NULL时，p->data会引发中断
    while (p && p->data != k)
    {
        p = p->next;
    }
    //返回NULL表示没有找到等于k的结点，否则返回该结点
    return p;
}

• 插入运算，最重要的是先找到插入位置的的前一个结点…，所以依然时间复杂度0(n)

//向head指向的单链表第i个结点的位置，插入一个数据域值为x的新节点
void InsertList(LinkList head, int i, Datatype x)
{
    //p为链表第i - 1个结点，s为插入的新节点
    ListNode *p, *s;
    p = GetNode(head, i - 1);
    if (p == NULL)
    {
        printf("error position");
        exit(0);
    }
    s = (ListNode *)malloc(sizeof(ListNode));
    s->data = x;
    //新节点指针域指向第i个结点
    s->next = p->next;
    //新节点成为第i个节点
    p->next = s;
}

• 删除运算，同理，最重要的是先找到删除结点的前一个结点…，时间复杂度O(n)

//删除head指向的单链表的第i个结点，并返回删除结点的数据域值
Datatype DeleteList(LinkList head, int i)
{
    //p为链表第i - 1个结点，s为第i个结点
    ListNode *p, *s;
    //x为删除结点的值
    Datatype x;
    p = GetNode(head, i - 1);
    if (p == NULL)
    {
        printf("error position");
        exit(0);
    }
    s = p->next;
    //i - 1结点的指针域指向i + 1结点
    p->next = s->next;
    x = s->data;
    //释放第i 个结点的空间并返回结点值
    free(s);
    return x;
}

单循环链表

单链表的最后一个结点（终端结点）的指针域不为空，而是指向链表的头节点，使整个链表构成一个环。

• 从任意一个结点开始都能访问到其他结点