## 链表是线性表的链式存储结构 线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素 之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个“结点”，表示线性表中一个数据元素 。 链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。 链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向明上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。 链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。 ## 更详细解说链表 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 由于链表这种数据结构必须利用指针变量才能实现，因此先介绍指针的概念。 由前述可知，计算机的内存储器被划分为一个个的存储单元，每个存储单元存放8个二进制位（即一个字节）。存储单元按一定的规则编号，这个编号就是存储单元的地址。也就是说计算机中存储的每个字节是一个基本内存单元，有一个地址。计算机就是通过这种地址编号的方式来管理内存数据读写的准确定位的。 计算机是如何从内存单元中存取数据的呢？从程序设计的角度看，有两种办法：一是通过变量名；二是通过地址。程序中声明的变量是要占据一定的内存空间的，例如，C语言中整型变量占2字节，实型变量占4字节。程序中定义的变量在程序运行时被分配内存空间。在变量分配内存空间的同时，变量名也就成为了相应内存空间的名称，在程序中可以用这个名字访问该内存空间，表现在程序语句中就是通过变量名存取变量内容（这就是程序中定义变量的用途，即程序中通过定义变量来实现数据在内存中的存取）。但是，有时使用变量名不够方便或者根本没有变量名可用，这时就可以直接用地址来访问内存单元。例如，学生公寓中每个学生住一间房，每个学生就相当于一个变量的内容，变量名指定为学生姓名，房间是存储单元，房号就是存储单元地址。如果知道了学生姓名，可以通过这个名字来访问该学生，这相当于使用变量名访问数据。如果知道了房号，同样也可以访问该学生，这相当于通过地址访问数据。 由于通过地址能访问指定的内存存储单元，因此可以说，地址“指向”该内存存储单元（如同说，房间号“指向”某一房间一样）。故将地址形象化地称为“指针”，意思是通过它能找到以它为地址的内存单元。一个变量的地址称为该变量的“指针”。如果有一个变量专门用来存放另一个变量的地址（即指针），则它称为“指针变量”。在许多高级程序设计语言中有专门用来存放内存单元地址的变量类型，这就是指针类型。指针变量就是具有指针类型的变量，它是用于存放内存单元地址的。 通过变量名访问一个变量是直接的，而通过指针访问一个变量是间接的。就好像要在学生公寓中找一位学生，不知道他的姓名，也不知道他住哪一间房，但是知道101房间里有他的地址，走进101房间后看到一张字条：“ 找我请到302”，这时按照字条上的地址到302去，便顺利地找到了他。这个101房间，就相当于一个指针变量，字条上的字便是指针变量中存放的内容（另一个内存单元的地址），而住在302房间的学生便是指针所指向的内容。 指针作为维系结点的纽带，可以通过它实现链式存储。假设有五个学生某一门功课的成绩分别为A、B、C、D和E，这五个数据在内存中的存储单元地址分别为1248、1488、1366、1022和1520，其链表结构如下图所示。 :-:  单链表 链表有一个“头指针”变量，上图中以 head表示，它存放一个地址，该地址指向链表中第一个结点，第一个结点又指向第二个结点……直到最后一个结点。该结点不再指向其他结点，它称为“表尾”，它的地址部分存放一个“NULL”（表示“空地址”），链表到此结束。链表中每个结点都包括两个部分：用户需要用的实际数据和下一个结点的地址。 可以看到链表中各结点在内存中可以不是连续存放的。要找到某一结点C，必须先找到其上一个结点B，根据结点B提供的下一个结点地址才能找到C。链表有一个“头指针”，因此通过“头指针”可以按顺序往下找到链表中的任一结点，如果不提供“头指针”，则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。打个比方，幼儿园的老师带领孩子出来散步，老师（作为头指针）牵着第一个小孩的手，第一个小孩的另一只手牵着第二个孩子……这就是一个“链”，最后一个孩子有一只手空着，他是“链尾”。要找这个队伍，必须先找到老师，然后按顺序找到每一个孩子。 上图的链表每个结点中只有一个指向后继结点的指针，该链表称为单链表。其实结点中可以有不止一个用于链接其他结点的指针。如果每个结点中有两个用于链接其他结点的指针，一个指向前趋结点（称前趋指针），另一个指向后继结点（称后继指针），则构成双向链表。双向链表如下图所示。 :-:  双向链表 链表的一个重要特点是插入、删除操作灵活方便，不需移动结点，只需改变结点中指针域的值即可。而数组由于用存储单元的邻接性体现数组中元素的逻辑顺序关系，因此对数组进行插入和删除运算时，可能需要移动大量的元素，以保持这种物理和逻辑的一致性。如数组中有m个元素，往第i（i < m）个元素后面插入一个新元素，需要将第i+1个元素至第m个元素共m-i个元素向后移动。 ## 一点看法 C语言是学习数据结构的很好的工具。理解了C中用结构体描述数据结构，那么对于理解其C++描述，Java描述都就轻而易举了！ 链表的提出主要在于顺序存储中的插入和删除的时间复杂度是线性时间的，而链表的操作则可以是常数时间的复杂度。对于链表的插入与删除操作，个人做了一点总结，适用于各种链表如下： * 插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。按照这个顺序处理可以完成任何链表的插入操作。 * 删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。 按照此顺序可以处理任何链表的删除操作。如果不存在其中的某个节点略过即可。上面的总结，大家可以看到一个现象，就是插入的顺序和删除的顺序恰好是相反的，很有意思！ 前面已经对单链表做了一些解释。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。 单链表实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。而向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。其实应该用数据和地址代替前面的对象和引用的。 单链表的结构示意图（包括空的单链表）： :-:  那么大家可能清楚了，为什么说有了头节点就可以操作所有节点。因为有连续不断的引用嘛！那么在链表里的属性大概就只有两个了：头节点和节点数量。当然，根据需要，我们通常需要更多的属性。 下面用C语言简单写一个单链表，并完成初始化，创建链表与链表遍历。 ```C #include <stdio.h> #include <stdlib.h> #include <time.h> typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */ /* 定义单链表结点类型 */ typedef struct Node{ ElemType element; struct Node *next; }Node; /* 1.初始化线性表，即置单链表的表头指针为空 */ void initList(Node **pNode) { *pNode = NULL; printf("initList函数执行，初始化成功\n"); } /* 2.创建线性表，此函数输入负数终止读取数据*/ Node *creatList(Node *pHead) { Node *p1; Node *p2; p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点 if(p1 == NULL || p2 ==NULL) { printf("内存分配失败\n"); exit(0); } memset(p1,0,sizeof(Node)); scanf("%d",&p1->element); //输入新节点 p1->next = NULL; //新节点的指针置为空 while(p1->element > 0) //输入的值大于0则继续，直到输入的值为负 { if(pHead == NULL) //空表，接入表头 { pHead = p1; } else { p2->next = p1; //非空表，接入表尾 } p2 = p1; p1=(Node *)malloc(sizeof(Node)); //再重申请一个节点 if(p1 == NULL || p2 ==NULL) { printf("内存分配失败\n"); exit(0); } memset(p1,0,sizeof(Node)); scanf("%d",&p1->element); p1->next = NULL; } printf("creatList函数执行，链表创建成功\n"); return pHead; //返回链表的头指针 } /* 3.打印链表，链表的遍历*/ void printList(Node *pHead) { if(NULL == pHead) //链表为空 { printf("PrintList函数执行，链表为空\n"); } else { while(NULL != pHead) { printf("%d ",pHead->element); pHead = pHead->next; } printf("\n"); } } int main() { Node *pList = NULL; int length = 0; ElemType posElem; initList(&pList); //链表初始化 printList(pList); //遍历链表，打印链表 printf("请为链表输入节点值，输入负数退出 \n"); pList=creatList(pList); //创建链表 printList(pList); } ``` 链表是由不定数量的节点连接（通过相互之间的引用）起来的，由于这种关系，在链表里我们只定义了头节点和节点数量。节点是由存储的对象及对下一个“节点”的引用封装而成。 当链表的每个结点只包含一个指针域时，我们称此链表为单链表。 关于单链表的存取，有时候我们在单链表的第一个结点（有效元素）之前附设一个结点，称之为头结点；指向头结点的指针，称之为头指针；对单链表的存取必须从头指针开始进行，由于单链表的最后一个数据元素没有直接后继，则指针为NULL。 :-:  对于头结点，数据域可以不存储任何信息，也可存储如链表长度等附加信息。 下面是带头结点的单链表与空表的比较图。 :-:  头指针与头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。 以下是头指针与头结点的关系： ```C //定义结点的结构体 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; ``` 则定义LinkList L;时，L为链表的头指针。 L=(LinkList) malloc (sizeof(LNode)); //创建一个结点 此处返回给L的是一个指针，并且赋给了头指针。 L->next=null; //这里说明我创建了一个头结点，即同时运用了头指针和头结点。 小结 关于头指针： * 在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。 * 头指针具有标识作用，故常用头指针冠以链表的名字。 * 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 关于头结点： * 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。 * 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。 * 首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。 * 头结点不是链表所必需的。