这学期的数据结构课有讲到链表，所以再来温故一下，毕竟温故知新嘛。
链表与数组的区别
链表和数组都是线性表，两者区别如下：
数组静态分配内存，链表动态分配内存；更进一步说就是数组不易拓展，但链表易拓展。数组在内存中连续，链表不连续；更进一步说就是数组可能会造成内存浪费，但链表的内存利用率高；数组利用下标定位元素，时间复杂度为O(1)，链表在最坏情况下是O(n)；即在随机性查找上数组比链表更快。在数组中进行插入和删除操作的时间是O(n)，链表是O(1)。 单链表单链表接触的太多了，单链表中每一个结点由数据域和指针域构成，因为C语言有指针的概念，可以很方便的控制内存，因此大多数关于链表的实现代码都是C/C++版本的，其它语言则大多都是模拟链表，但其实Python也可以实现真实链表，尽管Python不能直接操作内存，但因为Python是动态语言，因此可以直接把对象赋值给新的变量而不需要预先定义。
这篇博客仍以C语言来实现链表，Python版本感兴趣的可以自己尝试。
链表其实就是一个又一个的结点连接而成，这很好理解，如果你的指针学的还不错的话，那么创建一个链表并不是一件难事。
创建结点：
typedef struct Node{ int data; struct Node *next;}*Linklist;创建链表：
Linklist createList(int n){ Linklist p,q,head; head = (Linklist)malloc(sizeof(Linklist)); q = head; for(int i = 0; i < n; i++) { p = (Linklist)malloc(sizeof(Linklist)); scanf("%d",&p->data); p->next = NULL; q->next = p; q = p; } return head;}输出链表：
void print(Linklist head){ Linklist p = head->next; while(p) { printf("%d ",p->data); p = p->next;}}修改结点：
void changeList(Linklist head,int pos,int x)//修改第pos位的结点，修改值为x{ Linklist p = head; int i = 0; while(i < pos && p != NULL) { p = p->next; i++; } if(p) p->data = x; else printf("结点不存在！n");}插入结点：
void insertList(Linklist head,int pos,int x){ Linklist p = head; int i = 0; while(i < pos - 1 && p != NULL) //遍历到pos位置的前驱结点 { p = p->next; i++; } Linklist newnode = (Linklist)malloc(sizeof(Linklist)); newnode->data = x; newnode->next = p->next; //先后插 p->next = newnode; //再前插}删除结点（按位置删）：
void deleteList(Linklist head,int pos){ Linklist p = head; //记录前驱 Linklist q = head->next; //记录当前结点 int i = 0; while(i < pos - 1 && p != NULL) //遍历到pos位置 { p = p->next; q = q->next; i++; } p->next = q->next; //前驱结点指向待删结点的后继结点，即把待删结点隔离出来 free(q); //删除 q->next = NULL; //结点指向空}关于单链表的基本操作基本上也就上面那些，其中一些简单的细节被我省略了，比如在插入或者删除之前判断pos是否是不合理的值等，这些都比较好写，也就不再说，另外，因为如果每一个操作都详细辅以文字说明的话篇幅太长，所以大部分情况下我都直接给出了代码并附上少量的关键性注释，目的只是起到一个快速浏览和记忆的作用，因此这篇博客不太适合刚入门的新手，适合学过但记忆的不太牢固的人拿来复习。
单链表因为每一个结点只保存next的缘故，在它中只能通过一个结点访问它的后继结点而无法访问前驱，如果你想要通过一个结点既能访问前驱又能访问后继，那么可以使用双链表。
双链表与单链表在结构上唯一的不同在于，构成双链表的每一个结点，除了数据域和指向后继的next域之外，新添了一个指向前驱的pre域。在双链表中，查找或者插入等操作不仅可以从链表的头部开始，也可以从尾部开始。仿照创建单链表的思路，在创建双链表时，我们将创建两个哑元结点，分别代表双链表的head和tail。head以及tail结点都不保存数据，head结点的pre域为空，tail结点的next域为空。
双链表看起来是高大上了不少，但对于插入、查找等大部分操作，单链表和双链表在最坏情况下的时间损耗其实是相同的，均为O(n)。双链表更重要的作用是用在散列表中，在采用了双链表的散列表中，删除操作具有O(1)的时间复杂度，因为删除操作不仅需要找到待删结点的前驱还需要找到它的后继，在单链表中只能找到后继，但在双链表中，前驱和后继都可以同时找到。
创建结点：
typedef struct Node{ int data; struct Node *pre,*next;}*Linklist;创建链表：
Linklist head = (Linklist)malloc(sizeof(Linklist));Linklist tail = (Linklist)malloc(sizeof(Linklist));void createList(int n){ Linklist p,q; head->pre = head->next = NULL; tail->pre = tail->next = NULL; q = head; for(int i = 0; i < n; i++) { p = (Linklist)malloc(sizeof(Linklist)); scanf("%d",&p->data); p->next = NULL; p->pre = q; q->next = p; q = p; } p->next = tail; tail->pre = p;}输出链表：
void next_print(Linklist head) //正向输出{ Linklist p = head->next; while(p && p != tail) { printf("%d ",p->data); p = p->next; } printf("n"); }void pre_print(Linklist tail) //反向输出{ Linklist p = tail->pre; while(p && p != head) { printf("%d ",p->data); p = p->pre; } printf("n");}对于查找结点、修改结点、插入结点等等之类，与单链表基本一致，唯一不同的就是双链表可以选择正向遍历或者反向遍历两种方式。
接下来给出与单链表稍微有些许不同的删除操作：
删除结点：
循环链表
将一条链表的首尾相连我们就会得到一条循环链表。在单链表中，将尾结点的next域指向head结点，由此构造出一条单循环链表。在双链表中，将head结点的pre域指向尾结点，尾结点的next域指向head结点，由此构造出一条双循环链表。
循环链表有什么好处呢？首先，因为是循环结构，因此无须增加存储量，仅对表的连接方式稍作改变，即可使表的处理更加方便灵活。
① 循环链表没有NULL指针，因此在值判断操作中就不再是判别p == NULL 或者 p->next == NULL等方式，而是判别它们是否等于某一指针；
② 在单链表中实现全遍历只能从head节点开始，在双链表中只能从head或者tail结点开始，而在循环链表中可以从链表的任意位置开始；
单循环链表
单循环链表是在单链表的基础上实现的，在这里有两种实现方式，一种是带头结点的单循环链表，一种是带尾结点的单循环链表，两种方式均可实现，但有时候带尾结点的单循环链表可能更为方便。比方说：我们如果要查找链表的首元素和尾元素，那么用带头结点的单循环链表的话分别需要O(1)和O(n)的复杂的，因为虽然首元素可以直接得到，但尾元素却只能遍历得到，而如果采用带尾结点的单循环链表，则时间复杂度均是O(1)。
本来我是打算附上关于单循环链表一些基本操作的代码实现的，但敲了几个感觉实在是没什么用处，因为这些代码几乎和单链表的完全一样，所以这里我就略去了。
双循环链表
嗯。。。没啥需要说的，会写双链表就肯定会写双循环，双循环继承了双链表的许多优势同时又具有循环链表的优势，我就不再重复赘述了。
令附一表，在各种链表中实现相关基础操作的时间复杂度对比，包括单链表，已排序的单链表，双链表，以及已排序的双链表。
关于链表还有很多值得说的地方，但碍于篇幅这篇就不再介绍了，下一篇再补充吧。