当前位置:首页 » 《关注互联网》 » 正文

实现双向链表(带傀儡节点)_Ischanged的博客

15 人参与  2022年01月13日 12:34  分类 : 《关注互联网》  评论

点击全文阅读


引言

在之前的博文中,我简单的向大家分享了一些链表相关的知识及一些面试题,如果感兴趣的老铁可以去瞧瞧,今天做题遇到要实现带傀儡节点的双向链表,做了下,之前的单向链表中我们也遇到要设置傀儡节点(哨兵节点的题),今天我们就来看一下实现双向链表(带傀儡节点)。

基本思路

**对于链表没说带傀儡节点或者虚拟节点,这个链表没有真正的头结点,但是我们把第一个节点叫做头结点,它起到标识的作用,标识这个链表的头结点
这个头结点的位置随时可能发生这变化,是不固定的,之后通过这个头结点我们要完成一些链表的增删查改。如果带傀儡节点这个节点的位置是固定的,那么以后我们操作链表就以这个傀儡节点作为头结点,完成我们的一些基本的增删查改操作。**这就很简单了,具体思路见我之前双链表的博文。
代码如下内有关键注释:
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();
    }
}

🛣️过🉐小🧑🏽‍🤝‍🧑🏼如果9️⃣🉐🉑以🉐话记🉐点👍🏻🍹持👇🏻,🦀🦀
往期文章:
双向链表的实现(双向链表与单向链表的简单区别联系和实现)
链表的概念和结构及基本功能函数的实现(单链表的实现)


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/33172.html

节点  结点  链表  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1