资料内容：
一、前言
链表的历史
于 1955-1956 年，由兰德公司的 Allen Newell、Cliff Shaw 和 Herbert A. Simon 开发
了链表，作为他们的信息处理语言的主要数据结构。链表的另一个早期出现是由
Hans Peter Luhn 在 1953 年 1 月编写的IBM内部备忘录建议在链式哈希表中使
用链表。
到 1960 年代初，链表和使用这些结构作为主要数据表示的语言的实用性已经很
好地建立起来。MIT 林肯实验室的 Bert Green 于 1961 年 3 月在 IRE
Transactions on Human Factors in Electronics 上发表了一篇题为“用于符号操作的
计算机语言”的评论文章，总结了链表方法的优点。1964 年 4 月，Bobrow 和
Raphael 的一篇评论文章“列表处理计算机语言的比较”发表在 ACM 通讯中。
二、链表数据结构
在计算机科学中，链表是数据元素的线性集合，元素的线性顺序不是由它们在内
存中的物理地址给出的。它是由一组节点组成的数据结构，每个元素指向下一个
元素，这些节点一起，表示线性序列。
在最简单的链表结构下，每个节点由数据和指针（存放指向下一个节点的指针）
两部分组成，这种数据结构允许在迭代时有效地从序列中的任何位置插入或删除
元素。
链表的数据结构通过链的连接方式，提供了可以不需要扩容空间就更高效的插入
和删除元素的操作，在适合的场景下它是一种非常方便的数据结构。但在一些需
要遍历、指定位置操作、或者访问任意元素下，是需要循环遍历的，这将导致时
间复杂度的提升。
三、链表分类类型
链表的主要表现形式分为；单向链表、双向链表、循环链表，接下来我们分别介
绍下。
1. 单向链表
单链表包含具有数据字段的节点以及指向节点行中的下一个节点的“下一个”
字段。可以对单链表执行的操作包括插入、删除和遍历。
2. 双向链表
在“双向链表”中，除了下一个节点链接之外，每个节点还包含指向序列中“前
一个”节点的第二个链接字段。这两个链接可以称为'forward（'s'）和'backwards'，
或'next'和'prev'（'previous'）。
3. 循环链表
在列表的最后一个节点中，链接字段通常包含一个空引用，一个特殊的值用于指
示缺少进一步的节点。一个不太常见的约定是让它指向列表的第一个节点。在这
种情况下，列表被称为“循环”或“循环链接”；否则，它被称为“开放”或“线
性”。它是一个列表，其中最后一个指针指向第一个节点。
四、实现一个链表
像 Java 的源码中本身就提供了非常多的数据结构，包括我们所学习的链表
LinkedList 在日常的开发使用中也是非常频繁。
所以我们在学习的过程中，以使用 Java 程序员本身常用的语言来分析学习，并
通过简化结构的方式把 LinkedList 手写实现，让读者更能方便的理解链表
