链表学习-1

链表

链表通过指针将一组零散的内存块串联在一起，其中我们把内存块称为链表的结点，为了将所有的结点串联起来，每个链表的结点除了存储数据外，还需要记录链上的下一个结点地址：我们把这个记录下一个结点地址的指针作为后续指针的Next
同数组一样，链表也支持数据的查找，插入，删除的操作。由于不需要数据移动，所有在数据插入和删除上，链表是非常快速的。
但是链表在数据访问的时候就不那么高效了，因为链表中的数据是非连续的，所有无法像数据那样，根据首地址和下标，通过寻地址公司就能计算出对应你的内存地址，而需要依次遍历，直到指定结点的数据

循环链表

实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。
和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。

双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
从结构上看，双向链表可以支持O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。