主题：双向链表
头插法双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
方法：
public void addFirst(int data){ ListNodeD node=new ListNodeD(data); if(head==null){ this.head=node; }else{ node.next=this.head; this.head.prev=node; this.head=node; } }
2.尾插法
方法：
public void addLast(int data){ ListNodeD node=new ListNodeD(data); if(head==null){ this.head=node; this.last=node; }else{ this.last.next=node; node.prev=this.last; this.last=node; } }
3.任意位置插入,第一个数据节点为0号下标
方法：（1）先找出index的位置
（2）index位置不合法的情况
（3）index位置为0（在开头）：头插法
（4）index位置在结尾（在末尾）：尾插法
（5）在中间的情况，先改变插入元素的前驱和后驱
public ListNodeD findIndex(int index){ ListNodeD cur=this.head; while(index!=0){ cur=cur.next; index--; } return cur; } public void addIndex(int index,int data){ ListNodeD node=new ListNodeD(data); ListNodeD cur=findIndex(index); if(index<0||index>size()){ System.out.println("index位置不合法"); return ; } if(index==0){ addFirst(data); return; } if(index==size()){ addLast(data); return; } node.next=cur; node.prev=cur.prev; node.prev.next=node; cur.prev=node; }
4.查找是否包含关键字key是否在单链表当中
public boolean contains(int key){ if(head==null){ return false; } ListNodeD cur=this.head; while(cur!=null){ if(cur.data==key){ return true; } cur=cur.next; } return false; }
5.删除第一次出现关键字为key的节点
（1）若删除的关键字为头节点，有两种情况：一种是后面还有结点，一种是只有一个结点。
（2）若删除的关键字为中间，尾节点。
public void remove(int key){ ListNodeD cur=this.head; while(cur!=null){ if(cur.data==key){ //前方的 if(cur==this.head){ this.head=cur.next; if(this.head==null){//防止只有一个结点 this.last=null; }else { this.head.prev = null; } }else { cur.prev.next = cur.next; //后方的 if (cur == this.last) { this.last = cur.prev; } else { cur.next.prev = cur.prev; } } return; }else{ cur=cur.next; } } }
6.删除所有值为key的节点
方法：将5.中的return改为 cur=cur.next，进行所有k的删除。
public void removeAllKey(int key){ ListNodeD cur=this.head; while(cur!=null){ if(cur.data==key){ //前方的 if(cur==this.head){ this.head=cur.next; if(this.head==null){//防止只有一个结点 this.last=null; }else { this.head.prev = null; } }else { cur.prev.next = cur.next; //后方的 if (cur == this.last) { this.last = cur.prev; } else { cur.next.prev = cur.prev; } } cur=cur.next;//继续往后走，不要停，直到null为止 }else{ cur=cur.next; } } }
7.得到链表的长度
public int size() { int len=0; if(head==null){ return len; } ListNodeD cur=this.head; while(cur!=null){ cur=cur.next; len++; } return len; }
8.打印链表
public void display(){ if(this.head==null){ return; } ListNodeD cur=this.head; while(cur!=null){ System.out.print(cur.data+" "); cur=cur.next; } System.out.println(); }
9.清除链表
方法：把中间的删完了以后，再删除头节点和尾结点。
public void clear(){ ListNodeD cur=this.head; while(cur!=null){ ListNodeD curNext=cur.next; cur.prev=null; cur.next=null; cur=curNext; } this.head=null; this.last=null; }