引言
程序 = 数据结构 + 算法，在编写代码时，选择一个合适的数据结构是成功的一半。不过，问题是：解决同一个问题有很多种方法。对应到组织数据时，有很多数据结构都可以完成指定的工作。关键在于知道使用哪种数据结构是正确且最高效的。
很长一段时间对我来说，链表一直是其中一个比较复杂难理解的数据结构，但是它又特别重要。尽管我已经接触到链表有好几年了，但我总是无法在脑海中清楚地记住它们。我只有在准备技术面试时当有人问我关于链表的问题时，我才会想到它们。然后在做完一些练习之后，我认为我明白了它们的原理，但几周后，我又忘记了。
这整个学习过程非常低效，这一切都因为：虽然我知道它们的存在，但我并没有从根本上理解它们！所以，是时候改变这种状况了！
线性数据结构
链表是一种线性数据结构，这意味着它们是按顺序构建和遍历的。
我们可以将线性数据结构想象成跳房子游戏：为了到达链表的末尾，我们必须按顺序遍历链表中的所有数据。相比之下，在非线性数据结构中，元素不必按顺序排列，这意味着我们可以非顺序地遍历数据结构。
无论我们是否承认，我们每天都在使用线性和非线性数据结构！比如当我们将数据组织成哈希（有时称为字典）时，我们就是在使用非线性数据结构，类似地，当我们在代码中使用数组时，我们就是在使用线性数据结构！
数组和链表都是属于线性数据结构，但是它们之间有什么不同呢？这要从它们的内存使用方式说起。
数组和链表的内存管理
数组和链表之间最大的区别在于它们在机器中使用内存的方式。
当创建一个数组时，它需要足够连续的内存。如果我们有7个字母需要存储在数组中，我们需要连续7个字节的内存来存放这个数组中的字母。再次强调，我们需要所有这些内存在一个连续的块中。也就是说，我们的计算机会需要找到7个空闲的字节，这些字节彼此相邻，全都在一个地方。
但如果用链表存储这7个字母，它不需要将 7 个字节的内存都位于一段连续的地方，一个字节可以存在某处，而下一个字节可以存储在完全不同的内存位置！只要内存中空闲的字节总数大于7个字节就可以了。
数组和链表之间还有一个区别在于数组是静态数据结构，而链表是动态数据结构。静态数据结构意味着数组在创建时需要预估数据规模的大小，初始化时就分配好所用的内存；这意味着如果元素被删除，它仍然需要占用初始指定大小的内存。
同时如果需要向数组中添加更多元素而它没有足够的内存，你需要重新创建一个具有更多内存的数组，并复制该数组的数据到新数组，这种方式性能无疑是低效的。
反之，动态数据结构可以在内存中自由增长和缩小，其大小可以随着元素的增删而改变，具有很高的灵活性。
现在，我们已经开始看到数组和链表之间的一些主要区别。但这引出了一个问题：是什么允许链表的内存分散在各处？要回答这个问题，我们需要看看链表的结构。
链表的组成
链表可以很小也可以很大，但无论大小，链表都是由一系列节点（NODE）组成，每个节点包含数据和指向下一个节点的指针（引用）。
列表的起点是对第一个真正节点（真正存放数据的节点）的引用，该节点称为 head，几乎所有的链表都必须有一个 head ，通常情况下，我们通过"head"节点来访问整个链表的内容，因为它存储了链表的起始位置信息，没有它，我们就会像个无头苍蝇不知道从哪里开始！
节点的结构也非常简单，它只有两部分：数据（即节点包含的信息）和对下一个节点的引用，也就是说一个节点只知道它包含什么数据，以及它的邻居是谁。这也是为什么链表不需要连续的内存的原因，因为链表中的每个节点都有对下一个节点的引用，通过引用就可以访问到下一个节点，所以它们不需要像数组中的元素那样紧挨着彼此。
这也是为什么链表在程序执行过程中可以动态增长和缩小的解释。
各种形状的链表
链表可以根据节点之间的连接方式和特性分为多种类型，每种形状的链表都有其特定的应用场景和优劣势，以下是一些常见的链表。
单链表（Singly linked list）
单链表是最简单的链表类型，在单链表中，每个节点包含一个指向下一个节点的指针。单链表的最后一个节点指向空值（null），表示链表的末尾。
双向链表（Doubly linked list）
双向链表中，每个节点包含两个指针，一个指向下一个节点的指针（前向指针）以及一个指向上一个节点的指针（后向指针）。双向链表头节点的前向指针指向空值（null），尾节点的后向指针指向空值。
如果我们想在一个节点和前一个节点之间跳转，而不必回到列表的最开始，那么双向链表将是一种比单链表更好的选择。
循环链表（Circular linked list）
循环链表中的最后一个节点的指针指向第一个节点，这是和单链表的不同之处：单链表的最后一个节点指向空值（null）。
循环链表使得在链表末尾添加或删除节点变得非常容易，因为您可以从尾节点开始遍历它。
前面说的是单向循环链表，实际上，如果需要我们也可以将双向链表也变成循环链表！但是无论链表有多复杂，只要我们能够理解节点的组成，我们都可以搞定它。
链表操作
我们已经知道链表由什么组成，以及它们的非连续内存分配的特性。
那么，它们究竟是如何工作的呢？就像数组一样，我们可以向链表添加元素和移除元素，添加或删除节点对于链表来说变得异常简单，只需让节点的next指针改变即可：我们知道链表由单个节点组成，并且一个节点总是包含一些数据以及指向下一个节点或null的指针。因此，要向链表添加元素，我们只需要弄清楚哪个指针需要指向哪里。
插入新节点
为了简单起见，我们将在后面的示例中使用单链表。我们将从最简单操作开始：插入元素到链表中最开始的位置。这相当容易，因为我们只需要从头开始，不需要遍历整个列表。
- 首先，我们找到链表的头节点；
- 接下来将新节点的指针设置为当前链表的第一个节点。
- 最后，我们重新安排头节点的指针，使其指向新节点。
就是这样，我们完成了！好吧，看起来很简单，确实是这样——只要我们按正确的顺序执行这三个步骤。这里强调正确的顺序，如果我们不小心在步骤2之前执行步骤3，我们会陷入麻烦，原因是：如果先将头节点指针指向新节点，那么就丢失了与原链表的联系，新节点也找不到原链表的第一个节点，整个流程执行不下去了。
一旦您能记住这三个步骤，这个过程用代码实现就不会太难。
在链表的开头插入一个元素特别高效，因为无论链表有多长，它所需的时间都是相同的，即它的时间复杂度是常数，即O(1)。
但在链表末尾插入元素则会麻烦一些，这个麻烦之处是在于找到链表的尾节点，这需要遍历整个链表，但是一旦找到了尾节点，实际执行插入的步骤则和前面插入头结点的步骤完全相同：
- 找到我们想要更改指针的节点（在本例中是最后一个节点）
- 创建我们要插入的新节点并设置其指针（在本例中为null）
- 将前一个节点的指针指向我们的新节点
然而，这里增加了一些复杂性：我们需要找到最后一个节点。这意味着我们需要遍历整个链表才能找到它。而且我们知道链表的节点在内存中是非连续存储的，因此，随着我们拥有的节点数量的增加，遍历花费的时间也会线性增加，其时间复杂度是O(n)。
如果我们有一个包含100个节点的链表，这可能不会花费太长时间。即使是1000个可能也很快。但想象一下，如果我们想向一个包含千亿个节点的链表末尾添加一个元素！这可能对我们来说是非常糟糕的一天。
删除链表节点
删除操作也很简单：
- 找到要删除链表的前一个节点记为temp，让temp节点的指针指向它下下一个节点，对应代码就是temp.next = temp.next.next;，这样就将节点从链表中删除了。
- 手动释放掉节点，回收被节点占用的存储空间，这一步在C/C++这类编程语言中不要忘了，因为在这些语言中，程序员自己申请的内存需要自己手动释放！
使用链表还是不使用链表？
没有什么是完美的，链表也不例外。有时，链表非常棒——例如，当你想在链表开头插入或移除节点时。但正如我们所学，它们有时可能不太理想（想象一下拥有一百亿个节点却只想删除最后一个！）
即使你不需要每天都与它们打交道，但了解像链表这样的数据结构的一些基本知识也是有用的，这样你在看到它们时就能认出它们，并且也知道该在什么时候使用它们。
记住：链表在添加和删除节点时通常是高效的，但在搜索和查找节点时可能非常慢。
如果你发现自己需要做大量遍历、迭代或快速索引级访问，那么链表可能是你的敌人。在这些情况下，数组可能是更好的解决方案，因为你可以快速找到东西（利用数组下标进行索引级访问时间复杂度是O(1)），而不必花时间遍历整个列表。
然而，如果你想要将一堆元素添加到列表中，并且不担心以后查找元素，那么链表可能是你的新朋友。
下面是对于链表和数组对于各种操作的时间复杂度：
Algorithm Array List
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
很长一段时间里，我不知道链表是什么。当我终于了解它们时，我却不知道它们到底有什么用处。现在，我明白了它们的优缺点。如果有一天需要，我会知道何时选择使用它们来帮助我。
希望你也和我一样，对链表有同样的感受！
链表代码实现
我们将用Java编写一个单链表程序，包括节点的插入、删除和查找功能,如果理解了前面所介绍的链表知识，则实现起来应该是比较简单。
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
Node head;
// 插入节点到链表末尾
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// 删除指定值的节点
public void delete(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
// 查找节点是否存在
public boolean search(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
// 打印链表
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
}
public class SinglylinkedlistExample {
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
// 插入节点
list.insert(1);
list.insert(2);
list.insert(3);
list.printList(); // 输出: 1 -> 2 -> 3 -> null
// 删除节点
list.delete(2);
list.printList(); // 输出: 1 -> 3 -> null
// 查找节点
System.out.println(list.search(3)); // 输出: true
System.out.println(list.search(2)); // 输出: false
}
}
问题是，如果是双向链表，该如何实现？我偷点懒，这个问题还是留给屏幕前的您们了！
下一篇文章将和大家一起探讨一种有趣的数据结构-栈 ！
更多高质量原创技术文章可扫码订阅公众号：“非科班大厂码农”
