1、双向不带头链表的实现
1.1 节点成员和构造方法
双向不带头链表相比于单向多了一个prev域，它能使链表获得前驱节点。
如上图是双向不带头链表的一个节点，它可以直接找到前驱和后继节点。
由上面的讲解可得到代码：（注意：节点的类为静态内部类）
//静态内部类
static class ListNode {
private int val;//值域
private ListNode prev;//前驱
private ListNode next;//后继
//构造方法
public ListNode(int val) {
this.val = val;
}
}相比于单向链表的头节点，在双向链表中，多了一个尾巴节点last，方便了尾插法。
1.2 size（）、display（）、contains（）
求链表长度、打印链表、查找链表中是否包含该元素
这三个方法与单链表相同都是通过头节点遍历链表，这里就不做过多赘述。
代码如下：
//得到双链表的长度
public int size(){
int length = 0;
ListNode cur = head;
while(cur != null){
length++;
cur = cur.next;
}
return length;
} // 打印链表
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
} //查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}1.3 addFirst（）
头插法
相比于单链表的头插法，双链表的头插法又有什么不同呢？
如图，要将33头插入当前双链表中，在单链表中，我们只需要绑定后面的元素 ，然后再把头节点给到node，而双链表则还需要改掉原来头节点的前驱。
由此，有代码如下：
node.next = head;
head.prev = node;
head = node;此时，观察代码我们会想：如果我的链表中没有元素，那这里的不就发生空指针异常了吗？
因此，我们需要判断，当head==null的时候，我们把链表的头节点和尾巴节点都给到node，代码如下：
if(head == null){
head = node;
last = node;
}完整代码：
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
}1.4 addLast （）
尾插法
与头插法大同小异，只需要把原来的last的next改为node，再把当前节点的前驱改为last，再让last = node即可，如果链表中没有元素，就把头和尾巴都给到head。
完整代码：
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
node.prev = last;
last.next = node;
last = node;
}
}1.5 addIndex（）
在下标位置插入
在单链表中，addIndex方法需要找到下标的前一个元素。而在双链表中则可以直接找到该下标的元素（因为我们可以通过前驱来找到前一个元素）。
如图所示，我们需要改动4处位置，这里一定要注意这4处的顺序：建议最先改node的prev和next，然后改cur.prev.next,前面的顺序可以改变，但是cur的prev一定是最后改的。 因为是任意位置插入，在0位置我们直接调用头插法函数；在size（）位置直接调用尾插法函数；下标不合法，抛异常。
完整代码：
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
ListNode listNode = new ListNode(data);
if(index < 0 ||index > size()){
throw new IndexErrorException(index+"下标错误，无法插入");
}
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
int count = 0;
ListNode cur = head;
while(count != index){
cur = cur.next;
count++;
}
listNode.next = cur;
listNode.prev = cur.prev;
cur.prev.next = listNode;
cur.prev = listNode;
}1.6 remove（）
删除第一次出现值为key的节点
例如：要删除的key为34。
因为有了前驱和后继，我们可以直接让cur遍历到值为key节点 ，然后让cur.next.prev = cur.prev; cur.prev.next = cur.next;
细心的同学此时会发现问题:那我如果要删除的元素是头节点或尾节点，不发生空指针异常了吗？
是的，所以我们需要写两个if语句进行判断来单独删除头节点和尾巴节点：删除头节点：head = head.next; head.prev = null;此外，还应考虑链表只有一个节点的情况：只需将last置空即可。删除尾节点：cur.next.prev = null; last = last.prev;
代码如下
1.7 removeAllKey（）
删除所有值为key的节点
删除所有值为key的元素，只需要把remove（）代码中的return删去，让cur继续走下去即可。
代码如下：
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
//删除头结点
if(cur == head){
head = head.next;
if(head != null) {
head.prev = null;
}else{//只有一个节点的情况
last = null;
}
}else {//删除中间和尾巴
//删除尾巴
if(cur.next == null){
cur.prev.next = cur.next;
last = last.prev;
}else {//删除中间
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}1.8 clear（）
清空链表
清空链表的所有节点，有两种方法：
1、暴力清空（将head和last直接置空）
public void clear(){
head = null;
last = null;
}2、将所有节点的前驱和后继置空
public void clear(){
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
last = null;
}2、LinkedList和ArrayList的区别
一、从存储方面：ArrayList在物理和逻辑上都是连续的；LinkedList在物理上不连续，但在逻辑上是连续的。
二、增删查改和访问元素方面：
ArrayList在插入的时候需要将被删元素后面的元素后移一个单位，时间复杂度为O（n），而LinkedList只需要直接把节点插进去，时间复杂度为O（1）。此外，ArrayList空间不够需要1.5倍扩容；而链表对容量没有概念，只需要新建一个节点插入即可。
ArrayList可以通过下标随机访问元素，时间复杂度O（1）；LinkedList则只能通过cur一个一个寻找，复杂度为O（n）。
总结：访问元素次数多的使用顺序表，增删查改次数多则使用链表。