下载掌阅APP，畅读海量书库
立即打开
链表采用链式结构存储数据。在链式存储结构中，一个最小的存储单元称为一个结点，结点类似于链条中的一个环。多个结点串在一起构成一个链，形成如图2-8所示的一条链条。
图2-8 链条示意图
使用链式存储可以克服顺序表需要预先知道数据大小和插入删除元素造成的数据移动等缺点，链式存储结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了结点的指针域，空间开销较大。
单向链表也称作单链表，是链表中很简单的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
下面将阐述链表增加元素、查找元素和删除元素的过程。
单链表中的数据是以结点来表示的。每个结点的构成包括元素值和指向下一个结点（通常称作后继结点）的引用。单链表中第一个结点通常称作头结点。单链表如图2-9所示。
图2-9 单链表示意图
在单链表的实现中，需要一个结点类Node，用于表示链表中的一个结点。Node中含有一个用于存储数据的data属性和指向链表中后一个结点的引用。
单链表添加元素之前如图2-10所示。
将值为element的新结点插入第index的位置上。首先找到索引为index-1的结点，然后生成一个数据为element的新结点，并将index-1处结点的next引用指向新结点，新结点的next引用指向原来index处的结点。单链表添加元素之后的示意图如图2-11所示。
图2-10 单链表添加元素之前示意图
图2-11 单链表添加元素之后示意图
在单链表中查找element元素，必须从单链表的第一个元素开始向后遍历，直至找到目标元素为止。单链表的查找过程如图2-12所示。
图2-12 单链表查找元素示意图
将值为element的元素从单链表中删除，需要从单链表的头结点开始查找，找到element元素所在的index位置后，将index-1位置上的结点的next引用指向index+1位置上的结点。
单链表删除元素之前如图2-13所示。
图2-13 单链表删除元素之前示意图
单链表删除元素之后如图2-14所示。
图2-14 单链表删除元素之后示意图
在链表的实现中，用内部类Node表示链表中的一个结点。Node中含有一个用于存储数据的data属性和指向链表中后一个结点的引用next。链表的代码如下：
创建链表测试类，验证链表功能。测试类的代码如下：
执行链表测试类，测试结果如下：
----------向单链表新增元素----------
0 1 2 3 4 5 6 7 8 9
----------单链表是否为空----------
false
----------单链表删除元素后----------
1 2 3 4 5 6 7 8 9
（1）单链表的概念：单链表是使用链式结构存储的线性表。单链表只有一个方向。
（2）单链表的存储：单链表是使用离散的存储结构存储数据的。每个结点都保存了数据和指向后继结点的引用。
（3）单链表的优点：
· 单链表不需要使用连续的存储空间存储数据。
· 单链表没有固定的容量限制。
· 添加或删除单链表中的元素只需修改相关结点的引用，无须移动其他元素。
（4）单链表的缺点：
· 访问链表中的元素所需的时间复杂度为O(n)。
· 每个结点保存下一个结点的引用，占用更多存储空间。
· 单链表只能从头结点向后查找元素，不能从后向前查找元素。