一、双向链表概述
双向链表也是线性结构，但是与单链表相比，不仅有next指针指向下一个结点，还有prev指针指向前一个结点，在双向链表中，除了head指向首元结点之外，还有last指向双向链表的最后一个结点。
static class LinkedNode{ public int val; public LinkedNode next; public LinkedNode prev; public LinkedNode(int val){ this.val=val; } } public LinkedNode head; public LinkedNode last;
二、模拟实现双向链表
1、头插法插入元素
由于双向链表有prev指针，所以与单链表的头插法有所不同，此处需要考虑当链表为空时，就将head指向新插入的结点，同时last也指向该结点，当链表不为空时，就将新插入结点的next指向head，head的pre指向新插入的结点，并且head也指向新插入的结点。
//头插法 public void addFirst(int data){ LinkedNode linkedNode = new LinkedNode(data); if(head==null){ head=linkedNode; last=head; }else{ linkedNode.next=head; head.prev=linkedNode; head=linkedNode; } }
2、尾插法插入元素
单链表尾插法在插入元素时需要遍历链表找到尾结点，但是在双向链表中有last指针指向尾结点，就将新插入的结点的pre指向last， last的next指向新插入的结点，同时last指向新插入的结点，尾插法也要考虑链表为空的情况，链表为空的操作与头插法插入结点类似。
//尾插法 public void addLast(int data) { LinkedNode linkedNode = new LinkedNode(data); if(head==null){ head=linkedNode; last=head; }else{ last.next=linkedNode; linkedNode.prev=last; last=linkedNode; } }
3、在指定位置插入元素
在指定位置插入元素时，首先要判断位置的合法性，其次当插入位置为0时，则直接使用头插法，当插入位置为链表长度时则使用尾插法，其余正常情况就遍历到指定位置的结点p，那么就相当于在p之前插入一个结点， 设新插入的结点为s，则:p.prev.next=s;
s.prev=p.prev;
p.prev=s;
s.next=p;
//指定位置插入,第一个数据节点为0号下标 public boolean addIndex(int index,int data) { if(index<0||index>size()){ System.out.println("插入位置不合法"); }else if(index==0){ addFirst(data); }else if(index==size()){ addLast(data); }else{ int len=0; LinkedNode cur=head; while(len!=index){ len++; cur=cur.next; } LinkedNode s=new LinkedNode(data); cur.prev.next=s; s.prev=cur.prev; cur.prev=s; s.next=cur; } return false; }
4、查询双向链表中是否包含key
这个方法与单链表也类似，需要遍历链表，来查看是否包含key值。
//查找是否包含关键字key是否在双向链表当中 public boolean contains(int key) { LinkedNode cur=head; while(cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }
5、删除第一次出现关键字为key的结点
首先判断链表中是否包含key，如果包含key则找到该结点s，由于双向链表中包含两个指针，所以在删除该结点时，需要:s. pre.next=s.next;s.next.pre=s.pre;也需要考虑特殊情况，当删除的结点是首元结点则就需要：s.next.prev=null; head=head.next; 如果要删除的结点是尾结点，则就需要：s.prev.next=null,last=s.prev;
//删除第一次出现关键字为key的结点 public void remove(int key) { if(!contains(key)){ return; }else if(head.val==key){ head.next.prev=head.prev; head=head.next; }else if(last.val==key){ last.prev.next=null; last=last.prev; }else{ LinkedNode cur=head; while(cur!=null){ if(cur.val==key){ cur.next.prev=cur.prev; cur.prev.next=cur.next; return; } cur=cur.next; } } }
6、删除所有值为key的结点
该方法只需在删除第一次出现key的结点的方法中的while循环中去掉return即可，这样就会在while循环中删除所有值为key的结点。
//删除所有值为key的结点 public void removeAllKey(int key) { if(!contains(key)){ return; }else if(head.val==key){ head.next.prev=head.prev; head=head.next; }else if(last.val==key){ last.prev.next=null; last=last.prev; }else{ LinkedNode cur=head; while(cur!=null){ if(cur.val==key){ cur.next.prev=cur.prev; cur.prev.next=cur.next; } cur=cur.next; } } }
7、求双向链表的长度
此处求双向链表长度与单链表相似，定义一个变量len，逐步遍历链表，得到链表长度。
//得到双向链表的长度 public static int size() { int len=0; LinkedNode cur=head; while(cur!=null){ len++; cur=cur.next; } return len; }
8、遍历双向链表
与单链表遍历方法类似。
public void display() { LinkedNode cur=head; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); }
9、清空双向链表
双向链表由于既有前驱指针，又有后继指针，所以需要将链表的所有元素都置为null，并且将last和head也置为null。
//清空双向链表 public void clear() { LinkedNode cur=head; while(cur!=null){ LinkedNode nextNode=cur.next; cur.val=0; cur.prev=null; cur.next=null; cur=nextNode; } head=null; last=null; }
三、双向链表的常用方法
1、双向链表的构造方法
LinkedList():表示无参构造方法。
LinkedList(Collection <? extends E> c):构造方法中的参数表示可以传实现了Collection接口的并且其泛型是E的子类。例如：
ArrayList<String> arrayList=new ArrayList<>(); LinkedList<String> list=new LinkedList<>(arrayList);
2、双向链表的其他常用方法
在双向链表中除了模拟实现的方法，还有以下的常用方法：
四、顺序表和链表的区别
- 在存储空间上，顺序表要求有一段连续的存储空间，并且在容量不足的情况下需要扩容，但是链表靠指针相连，只是在逻辑上连续，存储空间不要求连续，元素之间靠指针进行相连，不存在扩容问题。
- 在用下标频繁访问元素时，顺序表的时间复杂度为O(1)，但链表需要进行遍历，时间复杂度为O(n),所以顺序表比较适合利用下标进行随机访问的情况。
- 在进行插入元素和删除元素时，顺序表需要移动整个表，但链表只需要修改指针的指向即可，所以链表比较适合频繁进行插入元素和删除元素的情况。
