前面的文章已经介绍过数据这种数据结构了，这一片篇文章开始将接触到一种新的数据结构-链表。
什么是链表？
链表是一种通过指针串联在一起的线性结构，这种串联结构的基本构成单位被称为节点。每一个节点由两部分组成，包括一个数据域和一个指针域，数据域用来存储数据元素，指针域用来存放指向下一个节点的指针，最后一个节点的指针域指向null (即空指针)。
链表最开头的节点通常被称为头节点一般用head表示。因为其头节点的存在因此在对链表进行操作的时候就存在一些常用的特殊技巧如使用虚拟头节点，这个技巧将会在后面的具体Leetcode解题中进行演示和深入讨论。
链表的结构图如下：
链表的不同类型：
单链表，这种链表就是上面图示中所展示的链表，它由一条单链组成上一节点能够通过指针找到下一节点。
双链表，每一个节点包含两个指针域，一个指向上一个节点，一个指向下一个节点，这也就意味着双链表不光包含next还包含一个prev。
如图所示：
循环列表，当链表的首尾相连时，其结构被称为循环列表，这种结构能够被用来解决约瑟夫环问题。
链表独特的存储方式
在前面的文章中，数组在内存中的存储方式是连续分布的，但是链表则是非连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
如图所示：
该链表的各个节点杂乱的分布在不同的内存地址空间上，并通过指针链接在一起。
在进行Leetcode刷题时，通常涉及到链表的题目都会事先定义好链表的结构，答题时只要知道怎么使用这个数据结构就行了，但是实际上我们也要学会自己定义出链表结构。
Java代码：
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}链表的操作：
相比于数组，链表的优点在于其增删的便利程度远大于数组。但由于其特殊的数据结构导致其查找操作十分不便利。因此当我们想要在算法中需要对数据进行大量的增删操作时我们就可以借助这种数据结构。
删除节点：当我们想要删除一个节点时，我们只需要将想要删除节点的上一个节点的指针指向删除节点的下一个节点就可以完成删除操作。值得注意的是，在一些需要手动释放内存的语言中如C++我们还需要使用释放内存的语句释放删除节点所占用的内存空间。对于一些具有内存回收机制的语言如Java，Python则不需要进行手动释放的操作。
增加节点：当想要增加一个节点时，只需要将增加节点位置的上一个节点的指针指向该节点，将想要添加的节点的指针指向下一个节点即可完成增加操作。可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除尾节点节点，需要从头节点查找到最末尾的节点通过next指针进行删除操作，查找的时间复杂度是O(n)。
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
这里我想到如果链表在进行插入和删除操作时要先遍历整个链表进行定位，那其进行插入和删除的时间复杂度不是和数组一样都是O(n)了么？那么为什么还说链表的效率更高呢？
我在另外一个博客上找到了答案。
因为这个O(n)内涵不同，分别是写O(n)和读O(n)。
数组擅长读取，链表擅长写入。
写入要先读取定位，再写入。
读取场景：任意序位读取，复杂度： 数组O(1)，链表O(n)。
写入场景：任意序位写入，定位复杂度：数组O(1)，链表O(n)；写入复杂度：数组O(n)，链表O(1)。
在写入场景中，数组链表的复杂度是定位写入复杂度之和，都是O(n),但写入比定位的O(n)慢很多，所以两个表面看起来一样的O(n)的实际时间还是差很多。
所以说链表和数组的插入删除时间复杂度都是o(n)，链表写入效率高。
看来链表的知识我们已经足够了解，接下来的几天我们开始刷题吧！