1. Toy模板网首页
  2. >Toy博客

数据结构 模拟实现LinkedList双向不循环链表

1年前作者：tao滔不绝分类：Toy博客阅读(12)违法举报

这篇具有很好参考价值的文章主要介绍了数据结构 模拟实现LinkedList双向不循环链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一、双向不循环链表的概念

二、链表的接口

三、链表的方法实现

（1）display方法

（2）size方法

（3）contains方法

（4）addFirst方法

（5）addLast方法

（6）addIndex方法

（7）remove方法

（8）removeAllKey方法

（9）clear方法

四、最终代码

一、双向不循环链表的概念

双向不循环链表中的节点有三个域，一个是存储数据的val域，一个是前驱prev域，还有一个是下个节点next域，和单向不同的就是多了一个前驱域。如图：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

定义一个MyLinkedList类，这个类包含要模拟实现的方法，还有一个内部类ListNode，这个内部类就是链表的节点，代码如下：

public class MyLinkedList implements Ilist{
    public ListNode head;//头结点
    public ListNode last;//尾结点

    static class ListNode {
        int val;
        ListNode next;
        ListNode prev;
        public ListNode(int val) {
            this.val = val;
        }
    }
}

二、链表的接口

代码如下：

public interface Ilist {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    void clear();
    void display();
}

三、链表的方法实现

（1）display方法

此方法是打印所有链表节点的val值，因此要遍历一遍链表的节点。代码如下：

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

（2）size方法

此方法计算链表中有多少个节点，所以也要遍历一遍链表，代码如下：

    public int size() {
        ListNode cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

（3）contains方法

此方法查看是否有key值，有就返回true，没有就返回false，所以也要遍历一遍链表，代码如下：

    public int size() {
        ListNode cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

（4）addFirst方法

此方法是头插方法，参数是链表的val域的值，所以调用此方法时，要创建一个节点，再把这个节点进行头插；头插时，要修改要插入节点的next域，指向原来的头结点，还有原来头结点的prev域，指向要插入的节点，最后再把头结点改为要插入的这个节点，如图：绿色箭头是修改指向

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表因为是新建的节点，所以这个节点的prev和next域都是null

修改完后，如图：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

代码如下：

    public void addFirst(int data) {
        ListNode cur = new ListNode(data);
        if(this.head == null) {
            this.head = cur;
            this.last = cur;
        } else {
            cur.next = this.head;
            this.head.prev = cur;
            this.head = cur;
        }
    }

执行效果如下：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

（5）addLast方法

此方法是尾插法，这里的尾插法时间复杂度是O(1)，因为双向链表有一个记录尾结点的last，所以尾插的时候直接在尾结点插入要插入的节点，修改原来的尾结点的next域，要插入的节点prev修改成原来的尾结点，最后再把尾结点last修改成插入的节点，代码如下：

    public void addLast(int data) {
        ListNode cur = new ListNode(data);
        if(last == null) {
            head = cur;
            last = cur;
        } else {
            last.next = cur;
            cur.prev = last;
            last = cur;
        }
    }

执行效果如下：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

（6）addIndex方法

此方法是在指定位置插入节点，第一要检查要插入位置的index下标是否合法，不合法就抛异常，这里定义第一个节点下标为0，第二个节点下标为1，依次类推，如果要插入位置的下标是0，就是头插，如果要插入位置的下标是链表长度（size方法），就是尾插；

要插入的位置在链表中间，我们要找出指定位置的前一个节点，修改前一个节点的next域，修改成要插入的节点，还有指定位置原来的节点的prev域也要修改，修改成要插入的节点。代码如下：

    public void addIndex(int index, int data) {
        //检查下标是否合法
        if(index < 0 || index > size()) {
            throw new IndexException("下标不合法");
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = new ListNode(data);
        ListNode prev = this.head;
        int count = 0;
        while (count < index - 1) {
            prev = prev.next;
            count++;
        }
        ListNode prevNext = prev.next;
        prev.next = cur;
        cur.prev = prev;
        cur.next = prevNext;
        prevNext.prev = cur;
    }
//自定义异常类
public class IndexException extends RuntimeException{
    public IndexException(String e) {
        super(e);
    }
}

执行效果如下：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

（7）remove方法

此方法是移除第一个值为key的链表节点的方法，参数是就是key；要移除某一个节点，就要从头遍历一遍链表，如果没找到key值，就直接返回，不做任何操作；

这里要提前处理一些特殊情况，如果头结点的val值就是key，就要把head放在head的next域，然后判断这时候head是不是空，如果head不是空，head的prev就要修改成空，如果head是空，就要把last设为空，直接返回。

如果找到了，就要找要删除节点的前一个节点，这里会分两种情况，一种是要删除的节点后面没有节点了（尾结点），这时我们把要删除节点的前一个节点的next域改成null，last改成前一个节点；如果要删除的节点后面有节点，就要把前一个节点的next域改成要删除的节点的next，后一个的prev域改成前一个节点，代码如下：

    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            if(head != null) {
                head.prev = null;
            } else {
                last = null;
                return;
            }
        }
        ListNode prev = findPrev(key);
        if(prev == null) {
            //没有要删的元素
            return;
        }
        ListNode cur = prev.next;
        if(cur.next != null) {
            prev.next = cur.next;
            cur.next.prev = cur.prev;
        } else {
            //最后一个元素
            prev.next = cur.next;//null
            last = prev;
        }
    }
    //找到要删除节点的前一个节点
    private ListNode findPrev(int key) {
        ListNode cur = this.head;
        ListNode curNext = cur.next;
        while (curNext != null) {
            if(curNext.val != key) {
                cur = cur.next;
                curNext = curNext.next;
            } else {
                return cur;
            }
        }
        return null;
    }

执行效果如下：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

（8）removeAllKey方法

此方法是删除所有节点的val值为key的方法，所以，我们要遍历一遍链表，如果head为空的话，就直接返回，不做任何操作；

我们定义prev是头结点，cur是头结点的next节点（要删除的节点），从头到尾遍历的是cur，如果cur的val值不等于key，prev和cur都要往后走一步；如果cur的val值等于key，会分成两种情况，就是cur后面是有没有节点，如果后面有节点，prev节点的next域就要改成cur的next，cur的下一个节点的prev域要改成prev，然后cur往后走一步；如果cur后面的节点为空，就直接把prev节点的next域改成空，把last改成prev，cur还要往后走一步结束循环。

最后不要忘了头结点还没有判断，要判断头结点的val值是否和key相等，如果不相等就不做任何操作，相等就把头结点head改成头结点的next，此时的头结点的prev改成null，注意，这里修改头结点的prev，要头结点head不为空，才能执行上面的操作，不然会空指针异常。

    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if(cur.val == key) {
                if(cur.next != null) {
                    prev.next = cur.next;
                    cur.next.prev = prev;
                } else {
                    prev.next = cur.next;//null
                    last = prev;
                }
                cur = cur.next;
            } else {
                prev = prev.next;
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
            if(head != null) {
                head.prev = null;
            }
        }
    }

执行效果如下：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表

（9）clear方法

此方法是把链表中的所有节点中所有域都置为空，所以要遍历一遍链表，把节点prev和next域改为null，因为这里的val域类型是int，所以不用修改val域，代码如下：

    public void clear() {
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }

执行效果如下：

数据结构 模拟实现LinkedList双向不循环链表,数据结构,链表文章来源地址https://www.toymoban.com/news/detail-778073.html

四、最终代码

public class MyLinkedList implements Ilist{
    public ListNode head;//头结点
    public ListNode last;//尾结点

    static class ListNode {
        int val;
        ListNode next;
        ListNode prev;
        public ListNode(int val) {
            this.val = val;
        }
    }

    @Override
    public void addFirst(int data) {
        ListNode cur = new ListNode(data);
        if(this.head == null) {
            this.head = cur;
            this.last = cur;
        } else {
            cur.next = this.head;
            this.head.prev = cur;
            this.head = cur;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode cur = new ListNode(data);
        if(last == null) {
            head = cur;
            last = cur;
        } else {
            last.next = cur;
            cur.prev = last;
            last = cur;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        //检查下标是否合法
        if(index < 0 || index > size()) {
            throw new IndexException("下标不合法");
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = new ListNode(data);
        ListNode prev = this.head;
        int count = 0;
        while (count < index - 1) {
            prev = prev.next;
            count++;
        }
        ListNode prevNext = prev.next;
        prev.next = cur;
        cur.prev = prev;
        cur.next = prevNext;
        prevNext.prev = cur;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            if(head != null) {
                head.prev = null;
            } else {
                last = null;
                return;
            }
        }
        ListNode prev = findPrev(key);
        if(prev == null) {
            //没有要删的元素
            return;
        }
        ListNode cur = prev.next;
        if(cur.next != null) {
            prev.next = cur.next;
            cur.next.prev = cur.prev;
        } else {
            //最后一个元素
            prev.next = cur.next;//null
            last = prev;
        }
    }

    private ListNode findPrev(int key) {
        ListNode cur = this.head;
        ListNode curNext = cur.next;
        while (curNext != null) {
            if(curNext.val != key) {
                cur = cur.next;
                curNext = curNext.next;
            } else {
                return cur;
            }
        }
        return null;
    }

    @Override
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if(cur.val == key) {
                if(cur.next != null) {
                    prev.next = cur.next;
                    cur.next.prev = prev;
                } else {
                    prev.next = cur.next;//null
                    last = prev;
                }
                cur = cur.next;
            } else {
                prev = prev.next;
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
            if(head != null) {
                head.prev = null;
            }
        }
    }

    @Override
    public int size() {
        ListNode cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

//自定义异常类
public class IndexException extends RuntimeException{
    public IndexException(String e) {
        super(e);
    }
}

都看到这了，点个赞再走吧，谢谢谢谢谢！！！

到了这里，关于数据结构 模拟实现LinkedList双向不循环链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包赞助服务器费用

相关文章

  • 数据结构（Java实现）LinkedList与链表（下）

    数据结构（Java实现）LinkedList与链表（下）

    ** ** 结论 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下： 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(12)
  • 数据结构（Java实现）LinkedList与链表（上）

    数据结构（Java实现）LinkedList与链表（上）

    链表 逻辑结构 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 链表的实现 创建一个链表 遍历单链表 、 得到

    2024年02月11日
    浏览(21)
  • 【数据结构】_4.List接口实现类LinkedList与链表

    【数据结构】_4.List接口实现类LinkedList与链表

    目录 1.链表的结构与特点 1.1 链表的结构： 1.2 链表的特点： 2. 不带头单链表的模拟实现 3. 单链表OJ 3.1 题目1：移除链表元素:  3.2 题目2：反转一个单链表 3.3 题目3：返回链表的中间结点 3.4 题目4：链表的倒数第k个结点 3.5 题目5：合并两个有序链表 3.6 题目6：链表的回文结构

    2024年02月15日
    浏览(11)
  • 数据结构——实现双向链表

    数据结构——实现双向链表

    怎么说呢？光乍一听名字好像很难的样子是吧，那如果你这样认为的话，可就要让你大跌眼镜了哦，其实双向带头循环链表从操作和理解上来说都是要易于单项不带头不循环链表（俗称单链表）的。 咱们就来见识见识吧！希望真的能让你们“大跌眼镜”哈！ 双向带头循环链

    2024年02月07日
    浏览(12)
  • 【数据结构】实现带头双向循环链表

    【数据结构】实现带头双向循环链表

    之前我们已经学习了单链表，有了单链表的基础，现在开始学习带头双向循环链表~ 结构最复杂 ，一般用在单独存储数据。 实际中使用的链表数据结构，都是带头双向循环链表 。另外这个结构虽然结构复杂，但是使用代码实现以后会发现 结构会带来很多优势 ，实现反而简单

    2024年02月10日
    浏览(12)
  • 【（数据结构）— 双向链表的实现】

    【（数据结构）— 双向链表的实现】

    注意： 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念，实际前面的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点，实际为 “哨兵位” ，哨兵位节点不存储任何有效元素，只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(14)
  • 【数据结构】双向链表的实现

    【数据结构】双向链表的实现

    我要扼住命运的咽喉，他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表，创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(9)
  • 数据结构——双向链表的实现

    数据结构——双向链表的实现

    注意： 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点，实际为“ 哨兵位 ”，哨兵位节点不存储任何有效元素，只

    2024年02月06日
    浏览(13)
  • [Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现

    [Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现

    上篇文章我们已经对顺序表进行了实现,并且对ArrayList进行了使用,我们知道ArrayList底层是使用数组实现的. 由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时， 就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低 ，因此ArrayList不适合做

    2024年04月26日
    浏览(48)
  • 数据结构双向链表，实现增删改查

    数据结构双向链表，实现增删改查

            在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点，可以用 双向链表 。         在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。 2.1 双向链表结点创建 2.2 双向链表

    2024年02月16日
    浏览(10)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包