引言
在之前的博文中，我简单的向大家分享了一些链表相关的知识及一些面试题，如果感兴趣的老铁可以去瞧瞧，今天做题遇到要实现带傀儡节点的双向链表，做了下，之前的单向链表中我们也遇到要设置傀儡节点（哨兵节点的题），今天我们就来看一下实现双向链表(带傀儡节点)。
基本思路
对于链表没说带傀儡节点或者虚拟节点，这个链表没有真正的头结点，但是我们把第一个节点叫做头结点，它起到标识的作用，标识这个链表的头结点
这个头结点的位置随时可能发生这变化，是不固定的，之后通过这个头结点我们要完成一些链表的增删查改。如果带傀儡节点这个节点的位置是固定的，那么以后我们操作链表就以这个傀儡节点作为头结点，完成我们的一些基本的增删查改操作。这就很简单了，具体思路见我之前双链表的博文。
代码如下内有关键注释：
DoubleLinkedList .java
///实现双向链表(带傀儡节点)代码
class ListNode {
public int data;
public ListNode prev;
public ListNode next;
public ListNode(int data) {
this.data = data;
}
}
public class DoubleLinkedList {
public ListNode dummyHead;//虚拟头结点
public ListNode last;//尾结点
public DoubleLinkedList() {
this.dummyHead = new ListNode(-1);//傀儡节点
}
//找到某一位置的节点,用于删除节点
public ListNode findIndex(int index) {
ListNode cur = dummyHead.next;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//头插法
public void addFirst(int data) {
ListNode node=new ListNode(data);
//第一次插入一个节点也没有时的情况
if(this.dummyHead.next==null) {
node.prev=this.dummyHead;
this.dummyHead.next=node;
this.last=node;
return;
// this.head=node;//带头了就不用再定义头了
}else {
//新插入的节点和他前后的节点连接
node.next=this.dummyHead.next;
node.prev=this.dummyHead;
this.dummyHead.next.prev=node;
this.dummyHead.next=node;
}
}
//尾插法
public void addLast(int data) {
ListNode node=new ListNode(data);
if(this.dummyHead.next==null&&this.last==null) {
node.prev=this.dummyHead;
this.dummyHead.next=node;
this.last=node;
return;
}else {
this.last.next=node;
node.prev=this.last;
this.last=node;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
//判断位置的合法性，任意位置插入,第一个数据节点为0号下标
if (index < 0 || index > size()) {
System.out.println("输入的位置不合法");
return;
} else {
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
}else {
//中间插
ListNode node = new ListNode(data);
ListNode cur;
cur = findIndex(index);
cur.prev.next = node;//当index==size时，如果不采用尾插法，会出现空指针异常
node.prev = cur.prev;
cur.prev = node;
node.next = cur;
}
}
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = this.dummyHead.next;
while (cur != null) {
if (cur.data == key) return true;
cur=cur.next;
}
//return false;
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
ListNode cur = this.dummyHead.next;
while(cur != null) {
if(cur.data == key) {
if(cur == this.dummyHead.next) {
//头结点是唯一的一个节点或不是唯一的一个节点的情况是一样的，
// 都是下面的代码和之前的不带头结点的双向链表不同
this.dummyHead.next = this.dummyHead.next.next; //两步代码是前后承接的
this.dummyHead.next.prev = this.dummyHead;
} else {
cur.prev.next = cur.next;
//判断是不是最后一个节点
//要删除的节点不是最后一个节点
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
//要删除的节点是最后一个节点
this.last = cur.prev;
}
}
return;
} else {
cur = cur.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key) {
ListNode cur = dummyHead.next;
while (cur != null) {
//
if (cur.data == key) {
//判断是不是头结点
if (cur == this.dummyHead.next) {//注意这里不要出错
this.dummyHead.next=this.dummyHead.next.next;
this.dummyHead.next.prev=null;
} else {
cur.prev.next = cur.next;
//判断是不是最后一个节点
if (cur.next == null) {
this.last = cur.prev;
} else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;继续往后走 不要停 直到为null 的时候
}
}
//得到单链表的长度
public int size() {
ListNode cur =this.dummyHead.next;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void display() {
ListNode cur = this.dummyHead.next;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
public void clear() {
//把所有的节点都置为null
ListNode cur = this.dummyHead.next;
ListNode curNext;
while (cur != null) {
curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.dummyHead = null;
this.last = null;
}
}
测试类
ublic class TestDemo {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList =new DoubleLinkedList();
doubleLinkedList.addFirst(1);
doubleLinkedList.addFirst(2);
doubleLinkedList.addFirst(3);
doubleLinkedList.addFirst(0);
System.out.println(doubleLinkedList.size());
doubleLinkedList.display();
System.out.println(doubleLinkedList.contains(0));
System.out.println("======================================");
doubleLinkedList.removeAllKey(1);
doubleLinkedList.display();
doubleLinkedList.addFirst(0);
doubleLinkedList.display();
}
}