链表（线性表的链式表示）

顺序表虽然具有可以随机存取的特点，但是在顺序表中插入和删除操作需要移动大量元素，在链式存储线性表中，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理上也相邻，因此插入和删除操作不需要移动元素，只需要移动指针，但也失去了随机存取的优点。

单链表

单链表的定义

单链表：线性表的链式存储又称单链表，通过一组任意的存储单元来存储线性表中的数据元素。单链表的结点结构中，不仅包含数据元素，还需要存放指向其后继的指针。

• 优点：
  • 插入删除操作不需要移动大量元素
  • 不需要大片连续空间，改变容量方便
• 缺点：
  • 不可随机存取，查找某个特定结点，需要从表头开始遍历
  • 需要耗费额外的存储空间存放指针

单链表的结点结构如下所示，其中data为数据域，存放数据元素；next为指针域，存放后继结点的地址。

单链表的结点类型描述

typedef struct Node {
    // 数据域
    DataType data;
    // 指针域
    struct Node * next;
} LinkList;

头指针

头指针：通常用头指针来标识一个单链表，头指针为NULL时表示为一个空表。

头结点

头结点：为了操作上的方便，在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不存放任何信息。头结点的指针域指向线性表第一个元素结点。
引入头结点后，头结点指针域为NULL表示空表。
引入头结点的优点：

• 第一个数据结点的位置被存放在头结点的指针域中，因此链表的第一个位置上的操作和在其他位置的操作一致（其他数据结点的位置存放在上一个结点的指针域，若无头结点，则头数据结点和其他数据结点的位置存放关系不一致，需要进行额外处理），无需额外处理
• 无论链表是否为空，头指针都是指向头结点的非空指针。因此空表和非空表的处理就统一了

  单链表的基本操作

  这里仅讨论带头结点的单链表的具体实现。

  头插法建立单链表

  为更好的表示头插法的建立过程，采用getche()读取控制台输入字符，为#时停止读取。
  头插法：读取数据存放在数据域中，将新结点插入到当前链表的表头位置即头结点之后。

因为头插法的插入原理，所以采用头插法具有以下特点：

• 读入数据的顺序与生成的链表元素顺序相反
• 每个结点插入的时间为$O(1)$，设需要插入的数据长度为$n$，则总时间复杂度为$O(n)$

• 将新插入结点插在最前端
• 将头结点指向新插入结点

  /**
  * 头插法建立单链表：头插法读入数据的顺序和生成链表中元素的顺序相反
  * @param head 头指针，传入传出参数
  * @return
  */
  int LinkListHeadInsert(Linklist *head) {
    Linklist *nextNode;
    // 初始化链表为空链表
    head->next = NULL;
    char ch;
    // 读取数据，数据为'#'时，结束读取操作
    while ((ch = (char) getche()) != '#') {
        // 创建新结点
        nextNode = (Linklist *) malloc(sizeof(Linklist));
        // 新结点数据域存放数据
        nextNode->data = ch;
        // 新结点的Next指针域指向头结点后的结点，若无此语句，将会造成没有指针指向其后的结点，数据丢失
        nextNode->next = head->next;
        // 将新节点插入表头，放在头结点之后
        head->next = nextNode;
    }
    return 1;
  }
  

  头插：
  nextNode->next = head->next;
  head->next = nextNode;

  尾插法建立单链表

  尾插法：读取数据存放在数据域中，将新结点插入到当前链表的表尾位置之后。
  因为尾插法的插入原理，所以采用尾插法具有以下特点：

• 读入数据的顺序与生成的链表元素顺序相同
• 因为在插入过程中，附设了一个指向表尾结点的指针，所以每个结点插入的时间为$O(1)$，设需要插入的数据长度为$n$，则总时间复杂度为$O(n)$
  
• 初始化尾指针，令尾指针等于头指针
• 尾插法插入元素：
  • 在尾指针后插入新结点
  • 令尾指针指向新插入的结点
• 尾指针指针域置为NULL

  /**
  * 尾插法建立单链表：尾插法读入数据的顺序和生成链表中元素的顺序相同
  * @param head 头指针，传入传出参数
  * @return
  */
  int LinkListTailInsert(Linklist *head) {
    Linklist *nextNode;
    // 初始化尾指针，令尾指针等于头指针
    Linklist *rearNode = head;
    // 初始化链表为空链表
    head->next = NULL;
    char ch;
    // 读取数据，数据为'#'时，结束读取操作
    while ((ch = (char) getche()) != '#') {
        // 创建新结点
        nextNode = (Linklist *) malloc(sizeof(Linklist));
        // 新结点数据域存放数据
        nextNode->data = ch;
        // 在尾指针后插入新结点
        rearNode->next = nextNode;
        //  令尾指针指向新插入的结点
        rearNode = nextNode;
    }
    // 尾指针指针域置空
    rearNode->next = NULL;
    return 1;
  }
  

  尾插：
  rearNode->next = nextNode;
  rearNode = nextNode;

  按位序查找结点

  从链表的第一个结点出发，沿着指针的next域逐个往下搜索，直到找到位序为$i$的结点，若找不到则返回NULL。

  /**
  * 按位序查找结点值
  * @param head 头指针
  * @param i 位序
  * @return
  */
  int LinkListGet(Linklist *head, int i, Linklist *getNode) {
    int j = 0;
    Linklist *p = head;
    if (i == 0) {
        return head;
    }
    // 保证位序合法，1 <= i <= length（单链表若求length，需要遍历一遍链表，时间复杂度较大）
    if (i < 1) {
        return 0;
    }
    // p：判断下一节点是否为NULL
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
  }
  

  按序号查找的时间复杂度为：$O(n)$。

  按值查找结点

• 从头到尾依次遍历元素，比较是否和需要查找的元素相等，相等则返回位序，反之返回0

  /**
  * 按值查找结点值
  * @param head 头指针
  * @param data 需要查找的元素
  * @return
  */
  int LinkListLocate(Linklist *head, DataType data, Linklist *getNode) {
    Linklist *p = head;
    while (p != NULL && p->data != data) {
        p = p->next;
    }
    return p;
  }
  

  按值查找的时间复杂度为：$O(n)$。

  插入结点操作

• 获取插入位置的前驱结点
• 令待插入结点的next指针指向下一个结点，防止下一个结点悬空

• 令前驱结点指向待插入结点

  /**
  * 插入结点操作
  * @param head 头指针
  * @param i 插入位序
  * @param data 插入数据
  * @return
  */
  int LinkListInsert(Linklist *head, int i, DataType data) {
    // 初始化
    Linklist *p;
    Linklist *s = (Linklist *) malloc(sizeof(Linklist));
    s->data = data;
  
    // 获取插入位置的前驱结点
    p = LinkListGet(head, i - 1);
    if (p != NULL) {
        // 令待插入结点的next指针指向下一个结点，防止下一个结点悬空
        s->next = p->next;
        // 令前驱结点指向待插入结点
        p->next = s;
        return 1;
    } else {
        return 0;
    }
  }
  

  插入结点：
  priorNode = LinkListGet(*head, i - 1);
  insertNode->next = priorNode ->next;
  priorNode ->next = insertNode;

• 查找前驱结点的时间复杂度为$O(n)$
• 执行插入结点的时间复杂度为$O(1)$

  删除结点操作

• 获取删除位置的前驱结点
• 令q指向被删除结点
• 令删除结点的前驱结点指向删除结点的后继结点

• 释放删除结点的存储空间

  /**
  * 删除结点操作
  * @param head 头指针
  * @param i 删除位序
  * @return
  */
  int LinkListDelete(Linklist *head, int i) {
    // 初始化
    Linklist *p;
    Linklist *q;
  
    // 获取插入位置的前驱结点
    p = LinkListGet(head, i - 1);
    if (p != NULL) {
        // 令q指向被删除结点
        q = p->next;
        // 令删除结点的前驱结点指向删除结点的后继结点
        p->next = q->next;
        // 释放删除结点的存储空间
        free(q);
        return 1;
    } else {
        return 0;
    }
  }
  

  删除结点：
  priorNode = LinkListGet(*head, i - 1);
  deleteNode = priorNode ->next;
  priorNode ->next = deleteNode ->next;
  free(q);

• 查找前驱结点的时间复杂度为$O(n)$
• 执行删除结点的时间复杂度为$O(1)$

  双链表

  双链表的定义

  双链表：双链表的指针域中包含两个指针prior和next，分别指向其前驱结点和后驱结点。
• 优点：相比于单链表，即可向前访问元素，也可向后访问元素，避免每一次访问元素都需要从表头开始遍历。
• 缺点：需要额外的存储空间存储前驱结点指针。

  双链表的结点类型描述

  typedef struct DNode {
    // 数据域
    DataType data;
    // 指针域
    struct DNode *prior;
    struct DNode * next;
  } DLinkList;
  

  双链表的基本操作

  相比于单链表，双链表指针域多了个前驱结点，所以在双链表上的插入和删除操作的实现上和单链表略有不同，在改变指针对象时，不仅要考虑后驱结点还需要考虑前驱结点。

  插入结点操作

  插入结点：
  insertNode->next = priorNode->Node;
  priorNode->next->prior = insertNode;
  insertNode->prior = priorNode;
  priorNode->next = insertNode;

  删除结点操作

  删除结点：
  priorNode->next = deleteNode->next;
  deleteNode->next->prior = pirorNode;
  free(deleteNode);

  循环链表

  循环链表与链表的区别是链表是线性的，表中的最后一个结点指针指向NULL，而循环链表的最后一结点的指针指向其头结点，从而使链表形成一个环。
  循环链表根据链表的指针域可以分为循环单链表和循环双链表。

  循环单链表

  循环单链表表尾结点指针域指向头结点，所以表中没有指针域为NULL的结点。
  循环单链表的判空条件：表尾结点指针等于头指针。

  循环双链表

  相比于循环单链表，循环双链表不仅表尾结点的next指针指向头结点，头结点的prior指针也指向表尾结点。
  循环双链表的判空条件：其头结点的prior域和next域都等于头结点。

  静态链表（通过数组表示）

  在一些不支持指针的高级语言中，可以使用静态链表来巧妙的表示链表的方法。

  静态链表的定义

  静态链表：静态链表借助数组来描述线性表的链式存储结构，结点中也有数据域data和指针域，与链表不同的是，这里的指针域存储的是结点的相对地址（数组下标），又称游标。静态链表需要预先分配一块连续的内存空间。

  
  
  

静态链接的结构类型描述

#define MaxSize 50

typedef struct DNode {
    // 数据域
    DataType data;
    // 指针域
    int next;
} SLinkList[MaxSize];

一般而言，静态链表以下标为0的结点表示头结点，next==1作为其结束标志，静态链表的插入和删除操作只需要修改其指针，不需要移动元素。

顺序表和链表的比较

读取方式

• 顺序表：顺序存取，可以随机访问。访问第$i$个位置的元素，仅需访问1次。
• 链表：智能从表头顺序存取元素。访问第$i$个位置的元素，需要从表头开始依次访问$i$次。

  逻辑结构与物理结构

• 顺序表：逻辑上相邻的元素，物理存储位置上也相邻。
• 链表：逻辑上相邻的元素，物理存储位置上不一定相邻。

  查找、插入和删除操作

• 顺序表：
  • 按值查找：
    • 有序：采用折半查找，时间复杂度为$O(long_2n)$
    • 无序：时间复杂度为$O(n)$
  • 按序号查找：顺序表支持随机访问，时间复杂度为$O(1)$
  • 插入与删除：顺序表插入与删除操作的耗时主要集中在移动表中元素上，执行插入与删除操作时平均需要移动半个表长的元素，时间复杂度为$O(n)$
• 链表
  • 按值查找：时间复杂度为$O(n)$
  • 按序号查找：顺序表支持随机访问，时间复杂度为$O(n)$
  • 插入与删除：链表插入与删除操作的耗时主要集中在寻找前驱结点上，在给定结点上执行插入与删除操作的时间复杂度为$O(1)$，从表头开始遍历寻找待操作结点指向插入和删除操作的时间复杂度为$O(n)$

    空间分配

• 顺序表：
  • 静态存储：一旦存储空间装满后就不能扩充，若加入新元素，则会内存溢出。
    • 预先分配空间过大：顺序表后部大量闲置。
    • 预先分配空间过小：容易造成内存溢出。
  • 动态存储：存储空间可以扩充，但需要移动大量元素，导致操作效率低，若内存中没有更大快的连续存储空间，则会导致内存分配失败。
• 链表：在需要时事情分配，只要内存有空间就可以分配。