在上一节，我们知道了动态数组实现的大概原理，不过，动态数组却有一个明显的缺点，即可能会造成内存空间的大量浪费。因为当动态数组空间使用完以后，会申请一个更大的空间，用来保存数据，但是更大空间的数组，却不一定能全部使用，因此可能造成空间浪费。

🤔能否做到用到多少就申请多少内存呢？

有！链表就可以做到这一点。

• 链表

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的；

1566305122630.png

1566305226539.png

1566305313016.png

所以，由于每次添加一个元素，都是新分配的内存空间，说一每个节点之间的内存地址并不一定是连续的。

1566305570732.png

• 链表的设计

链表中应该包含的元素

1. size - 保持链表的大小

2. first - 指向链表的头节点

1566305881624.png

一个完整的链表，用图形表示如下

1566306009091.png

了解了链表的设计以后，我们就可以来了解一下链表的接口设计了。

• 链表的接口设计

小提示：在阅读该小节时，建议结合demo源码进行同步阅读效果更佳，demo源码地址

1566310283422.png

1566310539362.png

至此，链表的接口设计就完成了，接下来再来了解一下接口的实现

• 清空链表 - clear()

1566310888924.png

我们需要做的事情就是

1. 将size设置为0

2. 将LinkedList对象中的first字段设置为null，当我们将first设置为null时，相当于头节点没有引用指向它，头节点的内存就会被系统回收，然后后节点依次被系统销毁
   1566311205757.png

🤔这里的next需要设置为null吗？

• 添加节点 - add(int index, E element)

1566311487936.png

操作步骤如下

1. 将新节点的next指向Node为1的节点
   1566311664168.png

2. 然后再让Node为1节点前面的节点里面的next指向新的节点

   
   
   1566311737348.png

3. 最后更新索引，就完成了节点的添加
   1566311790460.png

1566312668890.png

因此，编写链表的过程中，要注意边界测试，如index = 0、size - 1、size时

• 删除元素 - remove(int index)

  假设有以下一个链表对象，其中我们要删除Node为1的节点
  1566313216717.png

1566313330502.png

1566313429508.png

删除节点具体步骤

1. 找到被删除节点的前一个节点

2. 将前一个节点中的next赋值为下被删除节点的next即可

好工具分享-推荐一个神奇的网站给大家 数据结构和算法动态可视化 ，又兴趣的读者可以去看看，非常推荐

链表练习题 - 题目来自leetcode

题目1 删除链表中的节点

题目2 反转一个链表 题目解析

题目3 判断一个链表是否有环 题目解析

demo源码下载地址

本节完！