【数据结构与算法】之链表
2019-05-05 16:36:52
@Auther:MrZhangxd
概述
链表（Linked list）由一些节点组成，物理存储非连续的线性表。其中每个节点都会存储下个节点的指针，由于实际存储空间不连续，对链表插入节点，删除节点可以达到O(1)的复杂度，但是对一个节点的访问需要O(n)的时间。
链表有单向链表，双向链表。
单向列表
单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。
结构体表示为：
|
//单向链表节点数据结构 typedef struct linkNode { void *val; //数据项(任意类型) struct linkNode *next; }node; |
插入节点操作：
单向链表中由四个数据节点，数据1，数据2，数据3，数据4，现在数据1和数据2节点间插入数据5，只需把数据1节点的pNext指向新的节点，把新节点的pNext指向数据2节点即可。
删除节点操作：
删除节点2，只需把第一个节点的pNext执行数据3节点，同时释放节点2的存储空间即可。
双向列表
双向链表有别于单向的，每个节点除了数据项外有两个指针分别指向前一个节点和后一个节点，占用空间会大一些，可以实现从头到尾的遍历，又可以从尾到头遍历。
结构体表示为：
|
//双向链表节点数据结构 typedef struct dLinkNode { void *val; //数据项(任意类型) struct dLinkNode *prev; struct dLinkNode *next; }node; |
插入节点操作：
节点1与节点2之间插入新节点5，需要把节点1的pNext指向节点5，节点5的pHead指向节点1，节点5的pNext指向节点2，节点2的pHead指向节点5，
如下图所示：
删除节点操作：
删除节点2，把节点1的pNext指向节点3，把节点3的pHead指向节点1，同时释放节点2的存储空间即可。
如下图所示：
链表与数组的区别
1. 数组
查询快：数组要求是一块连续的内存空间来存储，这就要求在物理上这一片空间是连续的，每个元素都有指定的索引index指向内存地址，因此查询对时候，可根据index快速找到对应地址存储的信息，此为查询快.
增删慢：但要进行增删的时候，就必须将目标位置后的所有元素都整体移动，因此就比较耗时，此为增删慢.
2. 链表
增删快：链表在物理上是动态地分配储存空间，不要求连续性，但是要求逻辑上的连续。它需要存储每个元素在内存中的地址，以及它相邻元素的地址，然后像链条一样把各元素链起来，保证了在逻辑上的连续性。