在介绍链表之前，我们先说一下线性表，链表其实也是线性表的一种。
线性表是具有像线一样的性质的表 ，是由零个或多个数据元素组成的有限序列。数据元素可以是单个元素也可以是一组信息组成的元素。
举个例子来说，上学时班级里的名册，给每个人都标了一个学号，如1号张三，2号李四...44号王四四等等。
我们分析一下，首先它是有顺序的，其次学生的数量是有限的，可以当做一个有限序列，也就是线性表。我们单拿出学号来，是一组从小到大排序的数字（单个元素），是线性表。拿学号，姓名，出生日期组成的学生信息（多项元素）来看，它也是线性表。 还是这群学生，我们要绘制他们的交友关系线，那这种能不能用线性表呢？肯定是不行了，一个学生能交的朋友肯定不止一个，我们也不能强制说，你是1号，你只能和2号做朋友，你2号只能和3号...这肯定是不合适的，它肯定不是简单的线性关系。 知道了线性表之后，我们再继续下去，线性表有两种存储方式，一种是顺序存储结构，一种是链式存储结构。顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据。线性表(a₁,a₂...aᵢ ,aᵢ₊₁...aₙ)的顺序结构示意图如下所示：
顺序存储结构我们就不具体介绍了（数组就是一种顺序存储结构的代表）。
直接来看链式存储结构的线性表，也就是我们说的链表了。链式存储结构指的是用一组任意的存储单元存储线性表的数据，这组存储单元可以是连续的，也可以不连续。线性表(a₁,a₂...aᵢ ,aᵢ₊₁...aₙ)的链式结构示意图可能是这样的：
按这样杂乱的排列来看，从a₁到a₂要是不连条线的话，怕是根本找不着了。也就是说，链式结构不仅要存数据元素，还得把下一个数据的地址也存起来。让我们美化一下链表的样子：
图中这样的链表一般叫做单链表，然后我们把这些概念来解释一下（背个书）：单向链表 ：由一个个结点组成，每个结点都存储了数据信息和指向下一个结点的地址信息头指针（head）：链表中第一个结点的存储位置，叫做头指针，整个链表的存取都是从头指针开始进行的尾指针（tail）：指向链表最后一个结点的存储位置的指针，这个可以设置也可以不设置，因为最后一个结点的位置也可以通过从头开始一个一个结点的去找（就是比较慢而已，嗯，啊呸）NULL：最后一个结点已经没有下一个了，那它的指针就是“空”，通常用NULL表示
查询：在单链表里，当查询第 i 个元素的时候，我们不知道第 i 个元素在哪里，只知道头指针里放的第一个元素的地址，那没办法了，从第一个开始找吧。过程大概是这样：3、以此类推，一直找到第 i - 1个结点，根据 i - 1 结点的指针地址找到第 i 个元素有可能链表找到最后一个结点了还没有找到，那就说明 i 不存在。来计算一下查询的时间复杂度，查询第n条数据时，因为需要从第一条开始一个个查找 ,查询第一个是1次，第二个是2次，第n个就是n次，时间复杂度为O(n)。
插入 ：现在来看链表的插入操作，我们需要在第 i 个元素和第 i + 1 个元素间插入一个元素 s ，应该怎么操作呢？
看上图中，要把第s个结点放进去，我们是不是只需要把结点的指针地址位置调整一下就好了，也就是ps-->aᵢ₊₁ ，pi-->aₛ 
删除 ：现在我们需要删除第 i 个结点，与插入同理，我们把第 i -1 个结点的指针指向第 i + 1 个，那么 i 就找不到了。
看一下插入和删除的时间复杂度，我们拿顺序存储结构线性表来做个对比。先看顺序结构的，有n个元素，从第 i 个位置插入元素，首先直接找到第 i 个元素的位置，然后插入在后面。完了吗？还没有。一看后面还有 n-i 个元素呢，大家都得往后挪一个位置啊，不然顺序都乱啦。因此说，顺序结构有数据在中间插入，后面n - i 个元素都要挪位，时间复杂度为O(n)。我们如果插入多个，每往里插一个，在插入数据后边的都得挪一次，得亏是元素，要换了排队老有人插队，早骂人了（和排队插队还挺像哈）。删除也是一样的，每往中间删一个，后面所有的都要往前动一动。再看单链表，如果都是单个元素的增删，之前说过找到对应数据的位置需要先从头开始查找，这时时间复杂度为O(n)，再执行插入或删除操作时为O(1)，因此时间复杂度为O(n)。但当我们插入多个元素时，只有第一次查找时需要的时间长一点，后续都是知道位置的连续插入，时间复杂度为O(1)，不过总的来说还是O(n)。相比顺序结构每次增删都是O(n)，链表的增删操作效率看起来高多了吧。
接着来看一个问题，我们知道第 i 个元素的位置，现在要找第 i - 1 个，应该怎么找呢？按单链表的方式，还是得从头指针开始吧，一个个去找，最后找到 i - 1 在哪里。那明明给了第 i 个元素了，本来就在旁边，怎么还要重头找啊，这不是太麻烦了吗？那要是我们结点里不止放下一个结点的地址，把它上一个结点的地址也放进去，那不就好找了。这种每个结点均存有上一结点和下一结点的地址的链表，就叫双向链表（PS：头结点无上一结点地址，尾结点无下一节点地址啊）。
按照双链表的方式，我们知道第 i 个元素的位置，那么第 i - 1 个只要根据指向它的指针就找到了。双链表的增删查改和单链表基本类似，需要注意的是原来需要修改下一结点地址的指针的，在双链表的时候就需要修改上一结点地址和下一结点地址两个指针了。
