## 链表 由于数组在插入和删除操作，都需要后面的结点。内存需要预先分配，扩容不易。 所以有了链表。链表包含一个指向下一个节点的指针和一个自己data域 > 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下一个节点，这样当添加或者删除时，只需要改变相关节点的Next的指向，效率很高。 ```c_cpp struct Node { void * data; Node *next; } Node ``` 头指针：指向链表链表第一个元素的指针 头结点：就是一个含有空的数据域的结点。作为标识。 链表的结构  单链表的操作 - 查找 查找元素的时间复杂度依然是O（n）。需要从头节点遍历。 - 插入 插入一个新的元素到指定的位置，只需要改变前面元素的next指针指向该元素。不需要移动后面的元素。时间复杂度为0（n） - 删除 删除一个元素的，只需要记住这个元素的前一个元素和后面一个元素。删掉这个元素后，采用覆盖的方法，实现删除。时间复杂度为O（1） ### 双链表 双链表是包含两个两个指针域和一个data域的链表结构。这样我们可以从两个方向遍历。 ```c_cpp struct doubleLink { void *data; struct doubleLink next; struct doubleLink prev; } ``` ### 链表相关的面试题 链表是一种基础的数据结构，也是面试中常考的， - 判断单链表是否有环 可以使用快慢指针来。如果有环，则两个指针会相遇。 - 已知两个单链表相交，求他们的第一个交点 思路：由于两个单链表相交，那么他们的尾节点一定是相同的。遍历两个链表，求出各个长度。然后求出两个链表的差N，然后让长的链表，先走N,慢的链表再同步走。当两个节点相同时。就是一个第一个交点 - 快速找到未知长度单链表的中间节点 思路1：最简单的方法，遍历一次单链表，然后求出长度。然后除以2。找到位置，然后再遍历一次。时间复杂度是O（(3N/2)） 思路2：快慢指针，快的指针比慢指针多走一倍，然后快的指针走到尾，慢指针恰好在中间。 - 约瑟夫环 > 在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 思路：可以使用循环链表的方法。