一、链表 LinkedList
由于数组申请的内存是连续的，当数组的容量非常大时会造成内存空间的浪费，而且一旦容量到达临界点需要重新申请一块更大的内存，如果此时没有连续的内存空间供使用，那么将会造成数据的丢失。而链接是一种链式存储的线性表，所有元素的内存地址不一定是连续的，可以完美解决空间浪费的缺点
0 是头节点,3 是尾节点
一个链表中肯定至少包含两个成员变量，一个是链表的长度 size，另一个是链表的节点 Node，而根据图示每个 Node 节点中肯定至少包含节点中的元素以及下一个节点 Node。
二、链表LinkedList实现
创建一个新的 Module 名为LinkedList，在 entity 包中新增一个 Node 实体类
public class Node<T> { private T element; private Node<T> next; public Node(T element, Node<T> next) { this.element = element; this.next = next; } public T getElement() { return element; } public void setElement(T element) { this.element = element; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } } 复制代码
在 linked 包中定义 LinkedList 类，链表的接口和动态数组都是线性表，因此他们所包含的接口是一致的，可以定义一个上层接口 List<T>。
在 List 接口中定义线性表的接口，接口中只声明，不实现，但是链表和动态数组确实有些接口的实现是相同的，如 size()、isEmpty() 等，针对这种情况可以再定义一个 AbstractList 抽象类实现 List 接口，将一些相同的代码方法在 AbstractList 中，让 LinkedList 和 ArrayList 都继承这个抽象类。
List 接口
public interface List<T> { public static final int ELEMENT_NOT_FOUND = -1; void clear(); int size(); boolean isEmpty(); boolean contains(T element); void add(T element); T get(int index); T set(int index, T element); void add(int index, T element); T remove(int index); int indexOf(T element); } 复制代码
AbstractList 抽象类的定义
public abstract class AbstractList<T> implements List<T> { public int size; public int size(){ return size; } public boolean isEmpty(){ return size == 0; } public boolean contains(T element){ return indexOf(element) != ELEMENT_NOT_FOUND; } public void add(T element) { add(size, element); } } 复制代码
clear 接口的实现，首先 size=0，然后 first 指向空即可
@Override public void clear() { size = 0; first = null; } 复制代码
add (int index, T element) - 指定位置添加元素
将55这个节点添加到索引为2的位置上，需要先将要增加的元素将55这个节点添加到索引为2的位置上，然后找到索引2的前一个元素，即索引为1的元素，让索引为1的元素即22指向新增加的元素（1号线），这样新增加的元素的索引就变成2，原来索引为2的元素索引变为3，整个列表长度增加1。新增元素完成。
新增一个方法，获取指定索引位置的元素，链表不是顺序排列的，无法通过list[index]方式快速获取指定索引对应的元素。
//获取指定索引对应的元素 public Node getNodeByIndex(int index){ CheckUtils.checkIndex(index,size); Node<T> node = first; for (int i = 0; i < index; i++) { node = node.getNext(); } return node; } 复制代码
get方法就可以通过调用getNodeByIndex方法获取指定索引的Node,在去通过Node调用getElement方法获取该节点的元素
@Override public T get(int index) { return (T) getNodeByIndex(index).getElement(); }
