[数据结构与算法]数据结构之线性表----一文看懂顺序表、单链表、双链表、循环链表

? 线性表是数据结构中比较基础的内容，不过也是入门的所需要客服的第一个难关。因为从这里开始，就需要我们动手编程，这就对很多同学的动手能力提出了挑战。不过这些都是我们需要克服的阵痛，学习新的知识总是痛苦的，不过能坚持下来的话，最后这些痛苦都会转化为丰收的喜悦。精神的富足是我们都向往的，正如苏轼的那句诗----”腹有诗书气自华，粗缯大布裹生涯“，希望我们都能成为有技术、有"气质"、有自信的技术人员。大家共勉！

1.线性表的基本概念与实现(存储结构)

1.1线性表的定义

? 线性表(linear_list)是最常用且最简单的一种数据结构。线性表是具有相同特性数据元素(数据类型相同)的一个有限序列，相邻的数据元素之间存在着序偶关系(前驱、后继关系)。该序列中所含元素的个数叫做线性表的长度。

? 若将线性表记为
$$(a_1,...,a_{i?1},a_i,a_{i+1},...,a_n)$$
则表中a_i-1领先于a_i，a_i领先于a_i+1，称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。列表中的除了最后一个节点，每个节点都有且仅有一个直接后继，除第一个元素外，每个节点有且仅有一个直接前驱。

? 举例：可以把线性表想象成一队学生。学生的人数对应线性表的长度，学生人数是有限的，这里体现了线性是一个有限序列；队中所有人都是学生，这里体现了的线性表中的数据元素具有相同的特性；线性表中的数据可以是有序的，也可以是无序的，如果学生按照学号来进行排队，学号靠前的排在前面，则提现了线性表的有序性。

? 下面，我们总结下线性表的逻辑特性：

1. 存在唯一的一个被称作”第一个“的数据元素；
2. 存在唯一的一个被称作”最后一个“的数据元素；
3. 除第一个元素外，表中的每个数据元素有且仅有一个前驱；
4. 除了最后一个节点，表中的每个数据元素有且仅有一个后继。

? 线性表的抽象数据类型定义如下（其中仅涉及部分基础的操作，还可以定义一些复杂的操作，可以按需自行添加），后续我们的代码实现，就按照此ADT来进行实现。

ADT List {
  数据对象：D={ai|ai ∈ Elemset,i=1,2,…,n,n≥0}
	数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
	基本操作：
    InitList(&L)
    	初始化操作，建立一个空的线性表L。
    DistroyList(&L)
    	初始条件：线性表L已存在
    	操作结果：销毁线性表，释放其空间。
    ClearList(&L)
    	初始条件：线性表L已存在
    	操作结果：将线性表清空。
    ListEmpty(L)
    	初始条件：线性表L已存在
    	操作结果：若线性表为空，返回true，否则返回false。	
    ListLength(L)
    	初始条件：线性表L已存在
    	操作结果：返回L中数据元素的个数。	
    GetElem、(L, i, &e)
    	初始条件：线性表L已存在
    	操作结果：用e返回线性表L中的第i个位置元素的值。
    LocateElem(L, e)	    
    	初始条件：线性表L已存在
    	操作结果：返回线性表L中第一个与给定值e相等的数据元素的位置。若不存在这样的元素，则返回-1。
    ListInsert(&L, i, e)
    	初始条件：线性表L已存在
    	操作结果：在线性表L中的第i个位置插入新元素e，L的长度加1。
    ListDelete(&L, i, &e)
    	初始条件：线性表L已存在
    	操作结果：删除线性表L中第i个位置元素，并用e返回其值，L的长度减1。
    DisplayList(L)
    	初始条件：线性表L已存在
    	操作结果：输出L中的所有数据元素。
}

? 其中的基本操作的实现取决于采取哪一种存储结构（顺序结构、链式结构），存储结构不同，算法的实现也不同。

1.2线性表的存储结构

? 线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称之为链表。下面我们分别来介绍这两种存储结构。

1.2.1顺序表

? 顺序表就是把线性表中的所有元素，按照其逻辑顺序，依次存储到指定存储位置开始的一块连续的存储空间中。这样，线性表中的第一个元素的存储位置就是指定的存储位置，第i+1个元素的存储位置紧接在第i个元素的存储位置之后。（其特性和数组是相同的）

? 上图是顺序表在内存中的存储结构示意图，可以看到，每一个数据元素的存储位置都和线性表起始位置相差一个和数据元素在线性表中位序成正比的常数。由此，只要确定了存储线性表的起始位置，线性表中的任意数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

? 由于高级程序语言中的数组类型也有随机存取的特性，因此，一般都用数组来描述数据结构中的顺序存储结构。

? 顺序表的结构体定义如下，一般有静态数组、动态数组两种方式，一般而言，静态数组用于考试足够了，甚至在考试中可以直接使用int A[MAX_LENGTH]; int n;来简单定义一个顺序表。动态数组的实现，大家可以自行练习，鼓励大家多动手实现。

//静态数组的定义
#define MAX_LENGTH 100

typedef struct{
  int data[MAX_LENGTH];
  int length;
}SqList;

//动态数组的定义
#define LIST_INIT_LENGTH 100
#define LIST_INCREAMENT  10

typedef struct{
  //存储空间基址
  int *elem;
  //当前长度
  int length;
  //当前分配的存储空间容量（能存储多少个数据元素）
  int listSize;
}SqList;

1.2.2链表

? 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

? 在链表存储中，每个结点不仅包含所存元素的信息，还包含元素之间的逻辑关系信息，如单链表中前驱节点包含后继节点的地址信息，这样就可以通过前驱结点找到后继结点的位置。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成数据元素a_i的存储映像。称为结点(Node)。

? n个结点（a_i, 1<=i<=n)）链接成一个链表，即为线性表$$(a_1,...,a_{i?1},a_i,a_{i+1},...,a_n)$$的链式存储结构。

? 链表根据其节点中包含的指针域的特点，有分为单链表、双链表、循环单链表、循环双链表、静态链表五种。每种链表的详细介绍和操作在后面进行详细介绍。

? 在每个结点中除了包含数据域外，还包含一个指针域，用与指向后继结点。其中单链表的结构示意图如下所示：

? 注意：这里需要区分下带头结点和不带头结点的单链表。以上图为参考，是一个带头结点的单链表。

1. 带头结点的单链表中，头指针L（一般也用head，只是一个名词）指向头结点，头结点的数据域中不包含任何信息，从头结点的后继结点开始存储信息，我们一般称存储第一个元素的结点为首元结点。头指针始终不为NULL，head->next等于NULL时，链表为空。
2. 不带头结点的单链表中，头指针head直接指向开始结点（首元结点），当head等于NULL时，链表为空。

? 引入头结点，主要是为了操作方便，一个链表是否包含头结点，要根据具体题目来看。引入头结点后，有两个优点。①由于首元结点的位置被存储在头指针的指针域中，所以对于链表的首元结点的操作和表中其他位置的结点操作一致，无须特殊处理；②无论链表是否为空，其头指针是指向的头结点非空指针，因此空表和非空表的处理也就统一了。

链表结点的结构体定义如下：

//单链表结点的定义
typedef struct LNode{
  //数据域
  int data;
  //指向后继结点的指针
  struct LNode *next;
}LNode;

//双链表结点的定义
typedef struct DLNode{
  //数据域
  int data;
  //指向前驱结点的指针
  struct DLNode *prior;
  //指向后继结点的指针
  struct DLNode *next;
}DLNode;

? 说明：结点是内存中一片由用户分配的存储空间，只有一个地址来表示它的存在，没有显示的名称，因此我们在分配链表结点空间时，同时定义一个指针，来存储这片空间的地址（使用指针指向结点），并且使用这个指针的名称来作为结点的名称。例如，我们会使用下面代码来创建一个结点：

LNode *A = (LNode *)malloc(sizeof(LNode));	

1.2.3两种存储结构的比较

1. 存取方式:

   顺序表可以随机存取，也可以顺序存取；链表只能顺序存取（所谓顺序存取，以读取为例，要读取某个元素必须遍历其之前的所有元素才能找到它并读取之）。

2. 逻辑结构和物理结构

   采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻，其对应的逻辑关系是通过指针来链接的。这里请读者注意区别存取方式和存储方式。

3. 查找、插入和删除操作

   对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O(n)；而当顺序表有序时，可采用折半查找，此时时间复杂度为O(log2n)。
   对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素，时间复杂度为O(n)。链表的插入、删除操作时，只需要修改相关结点的指针域即可。

4. 存储分配的方式（空间分配）：
   顺序表的存储空间是一次性分配的（静态），链表的存储空间是多次分配的（动态）。

5. 存储密度（存储密度＝结点值域所占的存储量／结点结构所占的存储总量）：
   顺序表的存储密度＝1；链表的存储密度＜1(因为结点中有指针域）。

2.顺序表的基本操作

? 顺序表是线性表的顺序表示，不仅其逻辑结构上各元素之间是连续的，在存储结构上，元素结点之间也是相邻的，其结构和数组相似，故一般使用数组对其进行描述。具体概念可以参考1.2.1。

? 对于顺序表的基本操作，本文值讲解插入操作、删除操作和按值查找的算法，其他算法都相对简单，后续会给出C语言的代码，读者可以自行对照理解。

2.1插入操作

? 在顺序表L的第i(0=<i<=L.length)个位置插入新的元素e。如果i输入不合法（静态数组的形式要考虑表满的情况），则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空的位置插入新元素e，顺序表的长度增加1，插入成功，返回true。

? 注意：位置i是否可以为0，与存储位置是否从0开始，这与你的定义有关，只要前后统一即可。

/**
 在指定位置上插入节点
 */
bool ListInsert(SqList *L, int i, int e){
    int j;
    if(i<0 || i > L->length || L->length == MAX_LENGTH){
        printf("插入元素%d位置异常或者队列已满！\n", e);
        return false;
    }
    //从后往前，逐个将元素往后移动一位
    for (j = L->length-1; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i] = e;
    //表的长度自增1
    ++(L->length);
    return true;
}

2.2删除操作

? 删除顺序表L的第i(0=<i<L.length)个位置的元素。成功则返回true，否则返回false，并将删除的元素用引用变量e返回。

? 注意：这里i的取值范围和插入时不同，因为插入时可以插入在最后一个元素之后，而删除只能删除长度以内的位置，本文中，顺序表中的元素是从0开始存储的。

/**
删除指定位置上的节点
*/
bool ListDelete(SqList *L, int i, int *e){
    int j;
    if(i<0 || i >= L->length){
        printf("删除节点索引异常，超出范围！\n");
        return false;
    }
    //将指定位置的元素存入e中
    *e = L->data[i];
    //从前往后，逐个将元素往前移动一位
    for (j = i; j < L->length; j++) {
        L->data[j] = L->data[j+1];
    }
    //表的长度自增1
    --(L->length);
    return true;
}

? 下面我们对顺序表的插入和删除操作的时间复杂度进行分析。两个操作对元素的移动基本相同，因此这里对删除操作进行分析，插入也是类似的，读者可自己演算下。

? 最好情况：删除表尾元素（i = length-1），无须移动元素，时间复杂度为O(1)。

? 最坏情况：删除表头元素（i=0），需要移动除第一个结点外的所有元素，时间复杂度为O(n)。

? 平均情况：假设删除元素的位置是等概率的，则平均结点移动次数为(0 + 1 +2 … + n-1)/n = (n-1)/2，因此时间复杂度为O(n)。

? 如下图所示为一个顺序表在进行插入和删除操作的前、后状态，其数据元素在存储空间中的位置变化以及表长变化。在插入操作中，元素从后往前依次后移一个位置，在删除操作，元素从前往后依次向前移一个位置。

2.3按值查找

? 在顺序表中查找第一个值为e的元素，并返回其位序。

/**
 查找第一个值为e的元素，并返回其位序
 */
int GetElem(SqList L, int e){
    int i;
    for (i=0; i<L.length; i++) {
        if(L.data[i] == e){
            return i;
        }
    }
    return 0;
}

? 其时间复杂度和上面的分析方式相同，其平均时间复杂度为O(n)。

3.单链表的基本操作

? 由于顺序表的插入和删除操作需要移动大量的元素，影响了运行效率，由此引入了线性表的链式存储。链式存储线性表时，不需要使用地址连续的存储单元，即不需要逻辑上相邻的两个元素在物理位置（内存中的存储位置，绝对位置）上也相邻。链表是通过"链"建立其数据元素之间的逻辑关系，对链表的操作，最主要的是对指针的操作，因此对指针心怀恐惧的同学，一定要打起精神来，胜之、克之。

3.1链表的建立

? 链表的建立主要分为两种方式，分别是头插法和尾插法。下面我们来分别看下。

? 1.采用头插法建立单链表

? 该方法从一个空表开始（包含头结点），生成新的结点，并将读取到的元素存放到新结点的数据域中，然后将新结点插入到当前链表的表头（头结点后），即新插入的结点为首元结点。插入动作如下图所示：

? 2.采用尾插法建立单链表

? 头插法创建链表虽然简单，但是生成的链表中的结点的次序和输入的数据的元素顺序是完全相反的。若想两者的顺序一致，可采用尾插法创建链表。该方法是将新结点插入到当前结点的表尾上，为此需要增加一个尾指针，使其始终指向当前链表的尾结点。插入动作如下图所示：

3.2按照序号查找结点的值

? 在单链表中从第一个结点出发，顺指针域next逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL.

/**
 i的取值范围为[0-length-1]
 因事先不知道链表的长度，故需要边遍历边计数
 */
LNode * GetElem(LNode L, int i){
    //用于计数
    int j = 0;
    LNode *p = L.next;
    //如果是i=0,返回首元结点
    if(i == 0) {
        return p;
    }
    if(i < 0) {
        return NULL;
    }
    //遍历链表
    while (p && j < i) {
        j++;
        p = p->next;
    }
    return p;
}

3.3按值查找表结点

? 从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL.

/**
 查找第一个值为e的元素，并返回该结点的指针
 */
LNode * LocateElem(LNode L, int e){
    LNode *p = L.next;
    //遍历链表
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

3.4插入节点操作

? 插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
? 算法首先调用3.2中的按序号查找算法GetElemByIndex(L, i-1)，查找第i-1个结点。其操作过程如下图所示。

? 假设返回的第i-1个结点为*p，然后令新结点*s的指针域指向＊p的后继结点，再令结点*p的指针域指向新插入的结点*s。核心插入代码段如下图所示：

①   p = GetElem(L, i-1);     //查找插入位置的前驱结点
②   s->next = p->next;              //上图中操作步骤1
③   p->next = s;                    //上图中操作步骤2

? 注：其中步骤2和步骤3顺序不能颠倒，否则指针信息就会丢失。本方法的具体代码实现暂不给出。

? 本算法的时间开销在于寻找第i-1个结点，时间复杂度为O(n)。

3.5删除节点操作

? 删除操作是将单链表的第i个结点删除，先检查删除位置的合法性，然后查找表中第i-1个结点，即被删除结点的前驱结点，再将其删除。其操作过程如下所示：

? 假设结点*p为待删除结点的前驱结点，实现删除逻辑，仅需修改*p的指针域， 将*p的指针域指向*q的下一结点。核心插入代码段如下图所示：

①   p = GetElem(L, i-1);     //查找插入位置的前驱结点
②   q = p->next;                    
③   p->next = q->next;              //将结点q从链表中断开
④   free(q);                        //释放结点q的存储空间

? 上述第三步的操作，可以写成p->next = p->next->next，指针的操作，核心在于找到对应的结点。

? 和插入操作一样，该算法的时间开销在于寻找第i-1个结点，时间复杂度为O(n)。

3.6求表长的操作

? 求表长操作就是计算单链表中数据结点（不含头结点）的个数，需要从第一个结点开始顺序依次访问表中的每一个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加1，直到访问到空结点为止。算法的时间复杂度为O(n).

? 需要注意的是，因为单链表的长度是不包括头结点的，因此，不带头结点和带头结点的单链表在求表长操作上会略有不同。对不带头结点的单链表，当表为空时，要单独处理。

? 实现代码如下所示：

/**
 获取顺序表的长度
 */
int ListLength(LNode L){
    int length = 0;
    LNode *p = L.next;
    while (p!=NULL) {
        length++;
        p = p->next;
    }
    return length;
}

? 单链表是整个链表的基础，我们一定要熟练掌握单链表的基本操作算法，在设计算法时，建议先通过图示的方法理清算法的思路，然后再进行算法的编写。

4.双链表

? 单链表结点中只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序地向后遍历。若要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。
? 为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点，其结构如下图所示：

? 双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上，和单链表有较大的不同。这是因为“链”变化时也需要对 prior指针做出修改，其关键在于保证在修改的过程中不断链，也就是指针的操作不能错。

? 此外，双链表可以很方便的找到其前驱结点，因此插入、删除节点算法的时间复杂度仅为O(1)。需注意一点，单链表也是链表，无随机存取特性，如果在指定位置上插入、删除节点（仅给出位序，没有提供结点的地址），时间复杂度仍为O(n)。

? 对于双链表，其遍历方式仍然不变，因为本文只讲解其插入和删除操作，其余操作和单链表类似。

4.1双链表的插入操作

? 在双链表中p所指的结点之后插入结点*s，其指针的变化过程如下所示。

? 插入操作的核心代码片段如下：

①   s->next = p->next;     //将结点*s插入到结点*p之后
②   p->next->prior = s;                    
③   s->prior = p;              
④   p->next = s;                       

? 上述代码的语句顺序不是唯一的，但也不是任意的，①②两步必须在④步之前，否则*p的后继结点的指针就丢掉了，导致插入失败。读者可以在纸上画出示意图，以加深理解，。

4.2双链表的删除操作

? 删除双链表中结点*p的后继结点*q，其指针变化过程如下图所示：

? 删除操作的核心代码片段如下：

①   p->next = q->next;     //删除双链表中结点*p的后继结点*q
②   q->next->prior = p;                    
③   free(q);               

? 创建双链表的操作中，也可以采用如同单链表的头插法和尾插法，但是在操作上需要注意指针的变化，和单链表略微有所不同，毕竟多了个指针域，需要多一步指针操作。

5.循环链表

? 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链形成一个环。由此，从表中任一结点出发均可找到表中的所有结点。循环链表主要分为两种：单循环链表和双循环链表。

5.1循环单链表

? 循环单链表和单链表的区别在于，表中的最后一个结点的指针next不是NULL，而改指向链表的头结点，从而形成一个环。如下图所示：

? 循环单链表的空表，其head的next指向其本身。空表的示意图如下所示：

? 在循环单链表中，表尾结点＊r的next域指向L,故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

? 遍历结点的核心操作如下：

p = L->next;     //使用临时变量指向头结点
while(p != L){   //注意，循环结束条件不同，单链表的结束条件为p!=NULL
  //...
  p = p->next;
}

? 循环单链表的插入、删除算法与单链表的几乎一样，所不同的是如果操作是在表尾进行，则执行的操作不相同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个“环”，因此，在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。

? 在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任一结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。其原因是因为若设的是头指针，对表尾进行操作需要O(n)的时间复杂度，而如果设的是尾指针rear，rear->next即为头结点，对于表头与表尾进行操作都只需要O(1)的时间复杂度。

5.2循环双链表

? 由双链表和循环单链表的定义，不难推出循环双链表，需要注意的是头结点的prior指针还要指向表尾结点，其结构如下图所示：

? 在循环双链表L中，若*rear指向尾结点，rear->next == L；当然，L->prior == rear同样成立。当循环双链表为空表时，其头结点的prior、next都指向自身。

? 双向链表有以下特性，假设*p指向链表中的任一结点，显然有如下等式成立。

p->next->prior == p->prior->next == p

6.静态链表

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

? 静态链表和单链表的对应关系如下图所示：

? 因为静态链表一样有数据域和指针域，所以需要借助结构体，其描述如下：

//静态链表结点的定义
#define MaxSize 1000
typedef struct {
  //数据域
  int data;
  //指向后继结点的指针
  int next;
} SLinkList[MaxSize];

? 静态链表以next==-1作为其结束标志（数组的下标是从0开始）。静态链表的插入、删除操作与动态链表相同，只需要修改指针，不需要移动元素。总体来说，静态链表使用起来没有动态链表方便，需要依次寻找空闲的存储位置，但是在一些不支持指针的编程语言中，这又是一种非常巧妙的设计方法。

7.总结

? 有关线性表的基本知识已经讲完了，对于双链表、循环链表来说，许多操作都是类似的，因此没有用过多的篇幅去介绍，大家可以关联起来去理解。

? 学完线性表后，在以后的实际应用中，有应当如何选取线性表的存储结构呢？一般要参考顺序表和链表的特性，基于存储、运算等方面进行考虑。两种存储结构各有长短，没有任何一种数据结构是绝对完美的，有的是适用于某一实际问题。

? 通常较稳定的线性表选择顺序存储，而频繁插入、删除操作的线性表（即动态性较强），选择链式存储。也只有熟练掌握顺序存储和链式存储，才能深刻理解他们各自的优缺点。

参考：

1.顺序表的C语言实现

2.单链表的C语言实现（敬请期待）

3.数据结构中的C语言编程基础

4.数据结构考研大纲

5.数据结构高分笔记

6.王道数据结构

7.数据结构–C语言版，严蔚敏

? 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主根据自身理解与对考研资料进行的整理，仅作为参考，大佬有什么问题，可以评论区留言，如果有什么错误，还请批评指正。

? 本专栏为数据结构知识，喜欢的话可以持续关注，如果本文对你有所帮助，还请还请点赞、评论加关注。

? 有任何疑问，可以评论区留言。

关注博主即可阅读全文