无头双向单链表的基础功能实现
在单链表的学习中，我们已经掌握了求单链表的长度，是否包含了某一个元素，以及打印单链表，无头双链表的求长度，判断是否包含了某一个元素，打印双链表，都是与单链表的写法一样的，所以这里就不在多做赘述。
头插法
变化前
变化后
代码实现：
//头插法 public void addFirst(int data){ listnode add=new listnode(data); if (head==null){//还得考虑链表为空的情况 head=add; last=add; return; } add.next=head; head.prve=add; head=add; }
尾插法
变化前
变化后
代码实现：
//尾插法 public void addLast(int data){ listnode add=new listnode(data); if (head==null){//同样需要考虑要是有空列表的情况 head=add; last=add; return; } last.next=add; add.prve=last; last=add; }
删除第一次出现关键字为key的节点
一般情况
出现在头部情况（假设要删除的第一次数据在头部出现）：
出现在尾部（假设要删除的数据最后才第一次出现）：
对以上情况进行分析之后，我们必须通过遍历来解决，具体实现代码如下：
//删除第一次出现关键字为key的节点 public void remove(int key){ if (head==null)return; listnode cur=head; while (cur!=null){ if (cur.val==key){ if (cur==head){ cur.next.prve=null; head=head.next; }else{ cur.prve.next=cur.next; if (cur==last){ last=cur.prve; }else{ cur.next.prve=cur.prve; } } return; }else{ cur=cur.next; } } }
但是在这里代码是有缺陷的，因为如果就是一个节点的时候，那么此时代码会报错，我们就需要单独讨论一下，具体代码实现如下：
public void remove(int key){ if (head==null)return; listnode cur=head; while (cur!=null){ if (cur.val==key){ if (cur==head){ head=head.next; if (head!=null){ head.prve=null; }else{ last=null;//尾节点要变成null，不然会被一直引用 } }else{ cur.prve.next=cur.next; if (cur==last){ last=cur.prve; }else{ cur.next.prve=cur.prve; } } }else{ cur=cur.next; } } }
删除所有的值为key的节点
这个就需要在删第一次为key的基础上，把return去掉，然后要让cur一直往下走，具体实现代码如下：
//删除所有值为key的节点 public void removeAllKey(int key){ if (head==null)return; listnode cur=head; while (cur!=null){ if (cur.val==key){ if (cur==head){ head=head.next; if (head!=null){ head.prve=null; }else{ last=null; } }else{ cur.prve.next=cur.next; if (cur.next!=null){ cur.next.prve=cur.prve; }else{ last=last.prve; } } } cur=cur.next； } }
任意位置插入
插入前：
插入后
代码实现如下：
//任意位置插入,第一个数据节点为0号下标 public listnode search(int index){ if (index<0||head==null)return null; listnode cur=head; while (index!=0){ cur=cur.next; if (cur==null){//说明超出链表的长度 return null; } index--; } return cur; } public void addIndex(int index,int data){ listnode listnode=new listnode(data); if (index==0){//如果是第一个位置就是头插法 addFirst(data); return; } if (index==size()){//最后一个位置就是尾插法 addLast(data); return; } listnode ret=search(index); if (ret==null)return; ret.prve.next=listnode; listnode.next=ret; listnode.prve=ret.prve; ret.prve=listnode; }
清空双链表
代码实现：
public void clear(){ while(head!=null){ listnode cur=head.next; head.prve=null; head.next=null; head=cur; } last=null;//要把尾节点手动置为null，不然还在被引用 }
