本站消息

站长简介/公众号


站长简介:高级软件工程师,曾在阿里云,每日优鲜从事全栈开发工作,利用周末时间开发出本站,欢迎关注我的微信公众号:程序员总部,程序员的家,探索程序员的人生之路!分享IT最新技术,关注行业最新动向,让你永不落伍。了解同行们的工资,生活工作中的酸甜苦辣,谋求程序员的最终出路!

  价值13000svip视频教程,java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-02(285)

2021-03(330)

2021-04(139)

2021-05(108)

2021-06(48)

【java数据结构】双链表的设计与实现

发布于2022-01-06 08:37     阅读(298)     评论(0)     点赞(10)     收藏(4)


双链表介绍:
双向链表也叫双向表,是链表的一种,它由多个结点组成,每个结点都由一个数据域和两个指针域组成,数据域用于存放数据,其中一个指针域用来指向后继结点,另一个指针域用来指向前驱结点。链表的头结点的数据域不存放数据,指向前驱结点的指针域值为null,指向后继结点的指针域指向第一个真正存储数据的结点。

按照面向对象的思想,我们需要设计一个类来实现双向链表,由于结点是属于链表的,所以我们把结点类作为链表类的一个内部类来实现

双链表的四个成员变量

head头结点是整个双链表的入口,last用来表示链表的最后一个结点,N记录双链表长度,Node内部类实现结点

在这里插入图片描述

结点类的实现

    private class Node{
        //指向前一个结点
        private Node pre;
        //指向后一个结点
        private Node next;
        private T item;
        //构造方法
        public Node(T item,Node pre, Node next ) {
            this.pre = pre;
            this.next = next;
            this.item = item;
        }
    }

双向链表的构造方法

初始化头结点(没有数据域,没有前驱结点,没有后继结点)和链表长度

//双向链表的构造方法
     public TwoWayList(){
        //初始化头结点和尾结点
        this.N=0;
        this.head=new Node(null,null,null);
        //刚开始不存在尾结点
        this.last=null;
    }

在双链表尾部添加元素

首先判断链表是否为空,为空则直接让新结点的上一个结点成为头结点,让头结点的下一个结点成为新结点,并让新结点成为尾结点;
若不为空则让原本尾部的结点的下一个结点变为新结点,让新结点的上一个结点变为原来的尾部结点,让新结点成为尾部结点

    //在链表最后插入元素
    public void insert(T item){
        //链表为空,插在头结点后面
        if (isEmpty()){
            //创建新结点,新结点前面指向头结点
            Node newNode = new Node(item, head, null);
            //新节点作为尾结点
            last=newNode;
            //头结点指向尾结点
            head.next=last;
        }
        //链表不为空
        else{
        //创建新结点,新结点前面指向尾结点
        Node newNode = new Node(item, last, null);
        //让尾结点指向新结点
        last.next=newNode;
        //使新结点成为尾结点
        last=newNode;
        }
        N++;
    }

在指定的下标位置添加元素

找到指定下标位置的前一个元素,找到指定下标的元素,创建新结点(前面指向前一个元素,后面指向指定下标的元素)
让前一个元素的下一个结点变为新结点,让指定下标的元素的上一个结点变为新结点,让新结点成为尾部结点

  //在双链表的i索引处插入值为item的数据元素
    public void insert(int i,T item){
        Node pre=head;
        //找到i-1处的结点
        for (int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        //找到i索引处的结点
        Node curr=pre.next;
        //创建新结点,新结点上一个结点是i-1处,下一个结点是i处
        Node newNode = new Node(item, pre, curr);
        //让i位置的前一个结点的下一个结点变为新结点
        pre.next=newNode;
        //让i位置的前一个结点变为新结点
        curr.pre=newNode;
        N++;
    }

获取指定下标位置的元素

从下标0处开始遍历,找到指定的位置停下来,每次遍历指针往后移一位

 //获取指定索引的结点值
    public T get(int i){
        Node node=head;
        for (int index=0;index<=i;index++){
            node=node.next;
        }
        return node.item;
    }

删除指定下标位置的元素

找到指定下标位置的前一个元素,找到指定下标的元素,找到指定下标的下一个元素
首先判断要删除的元素是不是链表的最后一个元素,如果是则让前一个元素的next域不指向任何元素,让前一个元素成为尾部结点
如果是删除中间元素,则让上一个元素的下一个结点成为下一个结点,让下一个结点的前一个结点成为上一个元素

//删除双链表i索引处的结点,并返回该结点的值
    public T remove(int i){
        Node pre=head;
        //找到位置i-1的结点(i位置的前一个结点)
        for(int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        //找到i位置的结点
        Node curr=pre.next;
        //找到位置i的下一个结点
        Node nextNode=curr.next;
        //删除的是最后一个结点
        if(nextNode==null){
            pre.next=null;
            last=pre;
        }
        //删除的是中间结点
        else{
            //让i位置的前一个结点的下一个结点变为i位置的下一个结点
            pre.next=nextNode;
            //让i位置的下一个结点的上一个结点变为i位置的前一个结点
            nextNode.pre=pre;
        }
        N--;
        return  curr.item;
    }

返回元素在双链表中第一次出现的下标

从0下标开始遍历查找,直到遍历完整个链表

//返回结点item第一次出现的索引位置,若不存在,返回-1
    public int  indexOf(T item){
        Node node=head;
        for(int index=0;node.next!=null;index++){
            node=node.next;
            //相等,返回下标索引
            if(node.item.equals(item)){
                return  index;
            }
        }
        return -1;
    }

遍历整个双向链表

双链表的遍历与单链表一模一样,只是我们还可以倒序遍历双链表

遍历原理:我们可以学习集合ArrayList的forEach遍历方法,去实现Iterator迭代器我们通过链表类去实现Iterable接口,重写Iterable的Iterator方法,实现迭代器,由于Iterator方法的返回值是接口类型的Iterator,所以我们还创建了一个内部类去实现这个Iterator接口,以实现Iterator的类的对象返回。

 @Override
    public Iterator<T> iterator() {
        //用内部类实现Iterator接口
        return new LIterator();
    }

    //内部类
    private class LIterator implements Iterator{
        private Node node;
        public LIterator(){
            this.node=head;
        }
        @Override
        public boolean hasNext() {
            return node.next!=null;
        }

        @Override
        public Object next() {
            node=node.next;
            return node.item;
        }
    }

原文链接:https://blog.csdn.net/zbcwmq/article/details/122332250



所属网站分类: 技术文章 > 博客

作者:长这么胖

链接:http://www.javaheidong.com/blog/article/372938/65ad73d811bb72909cc8/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

10 0
收藏该文
已收藏

评论内容:(最多支持255个字符)