双向链表
双向链表结构其实与单向链表结构非常相似，只是比单向链表多了prev域用于存储前一个节点的地址，从而实现链表的双向性，见下图
节点类及链表头尾的建立
class Node { public int data;//一个节点存在三个区域 public Node prev; public Node next; public Node(int data) {//构造方法用于初始化实例对象 this.data = data; } } public class MyLinkedList { public Node head; public Node tail; public void addFirst(int data); //1.头插法 public void addLast(int data); //2.尾插法 public void display(); //3.打印链表 public boolean contains(int key); //4.查找是否包含关键字key是否在单链表当中 public int size(); //5.求链表长度 public void addIndex(int index,int data); //6.任意位置插入,第一个数据节点为0号下标 public void remove(int key); //7.删除第一次出现关键字为key的节点 public void removeAllKey(int key); //8.删除所有值为key的节点 public void clear(); //9.清空链表 }
以下即为双向链表的各接口的实现
1.头插法
头插节点有两种情况，第一种情况时空链表第一次插入，第二种为后续插入
public void addFirst(int data) { Node node=new Node(data);//将data的值new为一个节点 if (this.head == null) {//第一次插入 this.head=node;//头尾节点都指向该节点 this.tail=node; }else { node.next=this.head;//完成连接 this.head.prev=node;//改变域值 this.head=node;//头节点前移 } }
2.尾插法
与头插类似，两种情况>
public void addLast(int data) { Node node=new Node(data); if(this.head==null) { this.head=node; this.tail=node; }else { this.tail.next=node;//续尾 node.prev=this.tail;//变值 this.tail=node;//移尾 } }
3.打印链表
遍历链表完成打印
public void display() { Node cur=this.head; while(cur != null) { System.out.print(cur.data+" "); cur=cur.next; } System.out.println(); }
4.查找是否包含关键字
遍历链表，查找是否包含关键字
public boolean contains(int key) { Node cur=this.head; while(cur!=null) { if(cur.data==key) return true; cur=cur.next; } return false; }
5.求链表长度
遍历求和
public int size() { int a=0; Node cur=this.head; while(cur!=null) { a++; cur=cur.next; } return a; }
6.任意位置（index）插入
完成这项任务需要分步进行
1.判断index的合法性
2.是否为头插
3.是否为尾插
4.中间插入
在单链表删除关键字时，还需要设置前后节点完成连接，因为双向链表中存在上一个节点的地址，所以只需要设置一个节点遍历即可完成任务
private void checkIndex(int index) {//判断index位置合法性 if(index<0||index>this.size()) { throw new RuntimeException("index位置不合法"); } } private Node searchIndex(int index) {//查找插入的位置 Node cur=this.head; int a=0; while(a!=index) { a++; cur=cur.next; } return cur; } public void addIndex(int index,int data) { checkIndex(index); if(index==0) {//头插 this.addFirst(data); return; } if(index==this.size()) {//尾插 this.addLast(data); return; } Node node=new Node(data);//实例化node节点 Node cur=searchIndex(index);//cur存储index位置节点 node.next=cur;//左边四步完成连接过程，先对node中的值改变对原链表无影响 node.prev=cur.prev; cur.prev.next=node;//然后连接前后 cur.prev=node; }
7.删除第一次出现关键字为key的节点
设置cur节点遍历链表，当cur.data==key时，删除该节点（特殊极端情况单独考虑）>
public void remove(int key) { Node cur=this.head; while(cur!=null) { if(cur.data==key) {//如果找到关键字key if(cur==this.head) {//头节点的data为key this.head=cur.next;//头节点后移完成头节点删除 if(this.head!=null)//防止空指针异常 this.head.prev=null; }else {//中间找到key cur.prev.next=cur.next; if(cur.next!=null) cur.next.prev=cur.prev; else//如果cur.next==null，尾节点即为所需删除节点 this.tail=cur.prev; } break;//完成删除后跳出循环 } cur=cur.next;//如果没有进if语句中，cur继续往后遍历 } }
8.删除所有值为key的节点
与7代码相同，只是无需跳出循环，让cur完成遍历，把关键字全部删除即可
public void remove(int key) { Node cur=this.head; while(cur!=null) { if(cur.data==key) {//如果找到关键字key if(cur==this.head) {//头节点的data为key this.head=cur.next;//头节点后移完成头节点删除 if(this.head!=null)//防止空指针异常 this.head.prev=null; }else {//中间找到key cur.prev.next=cur.next; if(cur.next!=null) cur.next.prev=cur.prev; else//如果cur.next==null，尾节点即为所需删除节点 this.tail=cur.prev; } } cur=cur.next;//如果没有进if语句中，cur继续往后遍历 } }
9.清空链表
在单链表清空链表时，直接将this.head置为空即可（当this.head置为空时，没有对象引用头节点，则其内存被JVM自动收回，后续节点也被收会），而当双向链表清空时，只把this.head置为空时，因为为双向链表，所以第二个节点的prev仍然指向头节点，所以无法完成清空，则需遍历链表完成置空.
public void clear() {//完成遍历，所有都置为空，则内存被收回 while (this.head!=null) { Node cur=this.head.next; this.head.prev=null; this.head.next=null; this.head=cur; } this.tail=null; }
