动态数组与链表有相同部分，共用一个父类AbstracList，该父类继承接口List
数组：查询快，增删慢
链表：查询慢，增删快
2、链表
链表是一种链式存储的线性表，地址不一定是连续的
一个链表包括头结点、普通结点、尾结点
头结点内含：size（链表长度）、first（头指针）
其他结点内含：element（内容）、next（指向下一结点的指针，其中尾结点指针值为null）
头指针供外界使用，其他指针不需要，为静态内部类
private static class Node{
E element; //内容
Nodeprev; //指向前一个结点的指针
Nodenext; //指向下一个结点的指针
public Node(Nodeprev, E element, Nodenext) {
this.prev = prev;
this.element = element;
this.next = next;
}
} clear()
首先要让size等于0
只需要将头结点的指针指向空即可
其他结点没有头指针连接，会被自动回收，因此不需要管其他的结点
public void clear() {
size = 0;
first = null;
last = null;
}查找对应位置的结点
通过观察可以发现，从头结点到目标结点使用的指针数目与该结点位置-1相同，因此可以使用for循环，定义一个指针指向头结点地址，不断next直到到达目标结点的地址
private Nodenode(int index){
rangeCheck(index); //查看index是否正常
Nodenode = first;
for(int i = 0; i< index; i++){
node = node.next; //使指针指向下一个结点地址
}
return node;
} add(int index, E element)
先令要插入的结点指向插入位置原结点
再令前一个结点指向新插入的这个结点
public void add(int index, E element){
if(index == 0){ //由于插入位置为第一个时，node(index - 1)会报错
first = new Node<>(element,first);
}else{
Nodeprev = new node(index - 1); //原位置前一个结点为新结点的前一个结点
prev.next = new Node<>(element,prev.next); //创建新结点并将其与前后结点相连
}
size++;
} remove(int index)
令删除位置前一个结点的指针指向index+1，删除位置结点被断开后自动垃圾回收
public E remove(int index){ //返回删除位置原来的内容
Nodenode = first;
if(index == 0){
first = first.next;
}else{
Nodeprev = new node(index - 1); //找到前一个结点
node = prev.next; //node就是要删除的结点
prev.next = node.next; //前一个结点连接后一个结点，删除node
}
return node.element;
} indexOf(E element)
通过循环，找到对应元素的位置
public int indexOf(E element) {
if (element == null) { //空元素单独设条件
Nodenode = first;
for (int i = 0; i< size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Nodenode = first;
for (int i = 0; i< size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return -1;
} 虚拟头结点
上述功能基本都会将index=0的情况单独列出来，为了精简这些代码，我们在原头结点前设一个新的头结点，叫虚拟头结点
在头结点前另设一个头结点，它的值为null，它被头指针连接，且next指针指向真正的头结点
//构造函数，内含虚拟头结点的定义
public linklist(){
first = new Node<>(null,null);
}双向链表
拥有两个指针：头指针first和尾指针last，分别连接链表的头部和尾部，从而让链表连成一个环
每个结点又各自拥有两个指针，一个是与单向链表相同的next指针，从头指向尾的方向；另一个是prev指针，与next方向相反，从尾指向头
因此要找某个结点，比较它的index与1/2size的大小，小于说明离头结点比较近，用next指针，大于说明离尾结点比较近，用prev指针
双向链表添加元素，不需要寻找元素前一个结点（已经有prev指针了）
index不是0也不等于size时，顺序：添加结点的next连接原为index处的结点，prev连接这个结点的前一个结点，即index-1位置的结点；后一个结点的prev连接添加结点，前一个结点的next连接添加结点
Nodenext = node(index); //新结点的next为相应index位置的结点
Nodeprev = next.prev; //新结点的prev连接index位置结点的前一个结点
Nodenode = new Node<>(prev,element,next); //创建新结点
next.prev = node; //新结点变成获取结点的前一个结点，即变成了index位置的结点
prev.next = node; //新结点再与前一个结点的next相连 index为0时：头指针first改变，需要与添加结点相连，添加结点的prev变为null，也是上述代码中的prev = next.prev，唯一需要改动的就是prev是null时它没有next，所以最后一句代码进行修改：
if(next == first){
first = node; //新结点就是头结点，与头指针相连
}else{
prev.next = node;
}index为size时，尾指针last改变，需要与添加结点相连，添加结点的next变成null，原先的尾结点的next指向它
如果链表是空的，添加元素是链表第一个结点，last.prev不存在
if(index == size){
Nodeoldlast = last; //旧的尾结点
last = new Node<>(oldlast,element,null); //新的尾结点，它的prev指向oldlast,next指向null
if(oldlast == null){ //如果这是第一个结点
first = last; //头指针尾指针都指向新结点
}else{
oldlast.next = last;
}
} 删除某个结点时，由于双向链表能够轻松找到结点的前一个结点与后一个结点，所以只需要让他们断开（前一结点的next指向后一结点，后一结点的prev指向前一结点），再把index为0和size单独处理即可
单向循环链表：与单向链表不同的是，它的尾结点的next指向头结点
双向循环链表：比单向循环链表多一个，头结点的prev指向尾结点
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
