java学习|实现双向链表(带傀儡节点) 链表|数据结构|链表

引言 【java学习|实现双向链表(带傀儡节点)】在之前的博文中，我简单的向大家分享了一些链表相关的知识及一些面试题，如果感兴趣的老铁可以去瞧瞧，今天做题遇到要实现带傀儡节点的双向链表，做了下，之前的单向链表中我们也遇到要设置傀儡节点（哨兵节点的题），今天我们就来看一下实现双向链表(带傀儡节点)。
基本思路 **对于链表没说带傀儡节点或者虚拟节点，这个链表没有真正的头结点，但是我们把第一个节点叫做头结点，它起到标识的作用，标识这个链表的头结点
这个头结点的位置随时可能发生这变化，是不固定的，之后通过这个头结点我们要完成一些链表的增删查改。如果带傀儡节点这个节点的位置是固定的，那么以后我们操作链表就以这个傀儡节点作为头结点，完成我们的一些基本的增删查改操作。**这就很简单了，具体思路见我之前双链表的博文。
代码如下内有关键注释：
DoubleLinkedList .java

///实现双向链表(带傀儡节点)代码 class ListNode {public int data; public ListNode prev; public ListNode next; public ListNode(int data) {this.data = https://www.it610.com/article/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 =https://www.it610.com/article/= 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(); } }

?过小??如果9??以话记点持，
往期文章：
双向链表的实现（双向链表与单向链表的简单区别联系和实现）
链表的概念和结构及基本功能函数的实现（单链表的实现）