链表和动态数组相比，前面也已经提及过了，动态数组有个明显的缺点就是可能会造成内存空间的大量浪费，做不到用到多少就申请多少内存的功能，但是链表就可以办到了这一点，链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的，表现形式大概如下：
链表图
链表的设计
设计应该如下，让first指向链表的头结点：
链表设计图
接口设计
接口设计应该和动态数组的相差无多，同样有清除clear，获取get，添加add，删除remove，获取索引indexOf,获取索引index位置对应的节点对象node等方法，下面一一分析其实际过程；
清除元素clear
clear 代码图
设置size = 0，first = null; 按照上面的设计图来看，那些节点会释放内存么？是会的，因为没有gcroot的引用，这点和iOS的ARC类似，没有引用，会自动释放对象
添加元素 add(int index,E element)
add 代码图
获取节点node(int index)
node方法图
添加节点图里面为什么会有一个index = 0的判断？是因为添加的时候需要获取前一个节点的元素prevNode,然后让prevNode的下一个元素，也就是prevNode.next = new Node<>(element,prevNode.next),其中element代表要插入的元素，然后新插入的节点的next指向prevNode的next元素，上两个图说明一下这几句话:
添加前图（有元素）
添加后（有元素）
正式因为添加有这样的逻辑，添加之前需要获取前面一个元素，那如果index = 0，的时候，就如果还是按照这种逻辑的话，去除prevNode，那么index - 1 就会等于-1，就会超出边界，这样很明显是有问题的，所以才有判断index == 0的判断，如果index == 0 的话，将会是如下操作：
index == 0
代码 first=newNode<>(element,first); 开始没有元素的时候，也就是说first = null，所以当添加一个元素的时候，first 等于null传递给新元素，也就是新元素的newNode->next = null,让后first指向头结点0，之后size++，size是记录元素的个数值
删除元素E remove(int index)
remove
如果index == 0，那么first.next = null,最终结果也是first = null，如果index 不等于0，也是要先取出前面的元素prevNode，也就是下图中的0节点，然后将0节点的next，也就是1节点赋值给node，然后将1节点的next赋值也就是2节点的值赋值给0节点的next，这样1节点删除，这个时候0指向1，1指向2的线断开，释放内存，并且0指向了原来的2节点
测试源码
测试例子
其他方法就不一一讲解，这里只是将一些主要的方法讲解一下，更多情况可以从demo中获取
额外补充
为了让代码层面更加精简，可以引入虚拟头结点，例如下图
虚拟头结点
但是如果添加虚拟头结点，接口设计的代码就要有所变动了
构造函数
获取节点
添加元素
移除元素
网友评论