广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > Python >Java实现无头双向链表操作
  • 225

0
分享到

Java实现无头双向链表操作

2024-04-02 19:04:59 225人浏览 薄情痞子

Python 官方文档：入门教程 => 点击学习

摘要

本文实例为大家分享了Java实现无头双向链表的具体代码，供大家参考，具体内容如下 无头双向链表的结构： 代码分析 节点结构 class node {     private int

本文实例为大家分享了Java实现无头双向链表的具体代码，供大家参考，具体内容如下

无头双向链表的结构：

代码分析

节点结构

class node {
    private int data;
    private Node next;
    private Node prev;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

    private Node head;  // 头节点
    private Node last;  // 尾节点
    public DoubleLinked() {
    this.head = null;
    this.last = null;
}

1. 头插法


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

先判断链表是否为空，若为空，则直接插入，头节点和尾节点都直接指向新插入的元素；
若链表不为空，则把要插入节点的 next 指向链表头节点，头节点的 prev 指向新插入的节点，最后更新头节点为新插入节点，插入过程如下图所示：

2. 尾插法


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

若链表为空，同头插法；
若链表不为空，则把链表尾节点的 next 指向要插入节点，要插入节点的 prev 指向链表尾节点，最后更新尾节点为新插入节点，插入过程如下图所示：

3. 查找是否包含关键字 key 在单链表中

// 查找
    private Node searchIndex(int index) {
        checkIndex(index);
        int count = 0;
        Node cur = this.head;
        while (count != index) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    // 合法性检查
    private void checkIndex(int index) {
        if (index < 0 || index > getLength()) {
            throw new IndexOutOfBoundsException("下标不合法！");
        }
    }

    
    @Override
    public boolean addIndex(int index, int data) {
        if (index ==0) {
            addFirst(data);
            return true;
        }

        if (index == getLength()) {
            addLast(data);
            return true;
        }

        // cur 指向index位置的节点
        Node cur = searchIndex(index);
        Node node = new Node(data);

        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

        return true;
    }

4. 查找是否包含关键字 key 在单链表中


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

5. 删除第一次出现关键字为 key 的节点


@Override
public int remove(int key) {
    Node cur = this.head;
    int oldData = 0;
    while (cur != null) {
        if (cur.data == key) {
            oldData = cur.data;
            // 头节点
            if (cur == this.head) {
                this.head = this.head.next;
                this.head.prev = null;
            } else {
                // cur.next != null --->不是尾节点
                if (cur.next != null) {
                    cur.next.prev = cur.prev;
                } else {
                    this.last = cur.prev;
                }
            }
            return oldData;
        }
        cur = cur.next;
    }
    return -1;
}

6. 删除所有值为 key 的节点


@Override
public void removeAllKey(int key) {
    Node cur = this.head;
    while (cur != null) {
        if (cur.data == key) {
            // 头节点
            if (cur == this.head) {
                this.head = this.head.next;
                this.head.prev = null;
            } else {
                cur.prev.next = cur.next;
                // cur.next != null --->不是尾节点
                if (cur.next != null) {
                    cur.next.prev = cur.prev;
                } else {
                    this.last = cur.prev;
                }
            }
        }
        cur = cur.next;
    }
}

7. 得到单链表的长度


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

8. 打印链表


@Override
public void display() {
    if (this.head == null) {
        return ;
    }

    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = cur.next;
    }

    System.out.println();
}

9. 清空顺序表以防内存泄漏


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

接口、实现方法、测试

1. 接口

package com.GitHub.doubly;

// 不带头节点单链表的实现
public interface IDoubleLinked {
    // 1.头插法
    void addFirst(int data);

    // 2.尾插法
    void addLast(int data);

    // 3.任意位置插入，第一个数据节点为0号下标
    boolean addIndex(int index, int data);

    // 4.查找是否包含关键字 key 在单链表中
    boolean contains(int key);

    // 5.删除第一次出现关键字为 key 的节点
    int remove(int key);

    // 6.删除所有值为 key 的节点
    void removeAllKey(int key);

    // 7.得到单链表的长度
    int getLength();

    // 8.打印链表
    void display();

    // 9.清空顺序表以防内存泄漏
    void clear();
}

2. 实现方法

package com.github.doubly;

public class DoubleLinked implements IDoubleLinked {

    class Node {
        private int data;
        private Node next;
        private Node prev;

        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private Node head;  // 头节点
    private Node last;  // 尾节点
    public DoubleLinked() {
        this.head = null;
        this.last = null;
    }

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

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

    // 查找
    private Node searchIndex(int index) {
        checkIndex(index);
        int count = 0;
        Node cur = this.head;
        while (count != index) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    // 合法性检查
    private void checkIndex(int index) {
        if (index < 0 || index > getLength()) {
            throw new IndexOutOfBoundsException("下标不合法！");
        }
    }

    
    @Override
    public boolean addIndex(int index, int data) {
        if (index ==0) {
            addFirst(data);
            return true;
        }

        if (index == getLength()) {
            addLast(data);
            return true;
        }

        // cur 指向index位置的节点
        Node cur = searchIndex(index);
        Node node = new Node(data);

        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

        return true;
    }

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

    
    @Override
    public int remove(int key) {
        Node cur = this.head;
        int oldData = 0;
        while (cur != null) {
            if (cur.data == key) {
                oldData = cur.data;
                // 头节点
                if (cur == this.head) {
                    this.head = this.head.next;
                    this.head.prev = null;
                } else {
                    // cur.next != null --->不是尾节点
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = cur.prev;
                    }
                }

                return oldData;
            }
            cur = cur.next;
        }
        return -1;
    }

    
    @Override
    public void removeAllKey(int key) {
        Node cur = this.head;
        while (cur != null) {
            if (cur.data == key) {
                // 头节点
                if (cur == this.head) {
                    this.head = this.head.next;
                    this.head.prev = null;
                } else {
                    cur.prev.next = cur.next;
                    // cur.next != null --->不是尾节点
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

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

    
    @Override
    public void display() {
        if (this.head == null) {
            return ;
        }

        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }

        System.out.println();
    }

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

3. 测试

package com.github.doubly;

public class TestDemo {
    public static void main(String[] args) {
        DoubleLinked doubleLinked = new DoubleLinked();
        doubleLinked.addFirst(10);
        doubleLinked.addFirst(20);
        doubleLinked.addFirst(30);
        doubleLinked.addFirst(40);
        doubleLinked.addFirst(50);
        doubleLinked.display();


        doubleLinked.addIndex(0,100);
        doubleLinked.addIndex(1,200);
        doubleLinked.addIndex(0,300);
        doubleLinked.addLast(40);
        doubleLinked.addLast(50);
        doubleLinked.display();

        doubleLinked.remove(300);
        doubleLinked.display();

        doubleLinked.removeAllKey(50);
        doubleLinked.display();
    }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程网。

您可能感兴趣的文档:
点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: Java实现无头双向链表操作

本文链接: https://www.lsjlt.com/news/163175.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • Java实现无头双向链表操作
    本文实例为大家分享了Java实现无头双向链表的具体代码，供大家参考，具体内容如下 无头双向链表的结构： 代码分析 节点结构 class Node {     private int...
    99+
    2022-11-13
  • Java如何实现无头双向链表操作
    这篇文章主要介绍了Java如何实现无头双向链表操作，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。具体内容如下无头双向链表的结构：代码分析节点结构class Node...
    99+
    2023-06-28
  • Java双向链表的操作
    目录前言一、认识双向链表二、双向链表的增删改查1.插入头插尾插在index位置插入2.修改3.查询4.删除删除index位置的节点头删尾删删除第一个值为val的节点删除所有值为val...
    99+
    2022-11-13
  • Java实现双向链表
    本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下 1、双向链表 1.1 双向链表的每个节点组成包含节点数据，上一个节点（pre），下一个节点（next） ...
    99+
    2022-11-13
  • Python实现双向链表基本操作
    双向链表的基本操作的实现，供大家参考，具体内容如下 在之前的博客中介绍了三种链表，分别是单链表、单向循环链表以及双向链表。本篇博客将用Python来实现双向链表的如下操作。（用到的工...
    99+
    2022-11-11
  • java模拟实现双向链表
    双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点 下图是双...
    99+
    2022-11-13
  • java代码实现双向链表
    本文实例为大家分享了双向链表java实现代码，供大家参考，具体内容如下 一、双向链表简介 1、单链表的缺陷 单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据...
    99+
    2022-11-13
  • 基于Java实现双向链表
    本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下 双向链表与单链表的对比： 1、单向链表查找只能是一个方向，双向链表可以向前或者向后查找2、单向链表不能自...
    99+
    2022-11-13
  • java双向链表怎么实现
    Java中的双向链表可以通过定义一个Node类来实现，该类包含一个值和两个指针，分别指向前一个节点和后一个节点。具体实现如下： pu...
    99+
    2023-10-22
    java
  • Java如何实现双向链表
    本篇内容介绍了“Java如何实现双向链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！1、双向链表1 双向链表的每个节点组成包含节点数据，上...
    99+
    2023-06-30
  • JAVA中怎么实现链表和双向链表
    这篇文章给大家介绍JAVA中怎么实现链表和双向链表，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。JAVA基础:语言中链表和双向链表的实现(转)[@more@]链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语...
    99+
    2023-06-03
  • C语言实现带头双向循环链表
    目录前言1. 创建结构体2.malloc新节点3.创建哨兵位节点4.尾插5.打印6.尾删7.头插8.在指定位置pos的前面进行插入9. 删除指定位置pos节点10.销毁链表前言 在...
    99+
    2022-11-13
  • C语言实现带头双向环形链表
    双向循环链表 上一次我们讲了单向无头非循环链表的实现，单向无头非循环链表的特点是：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。而带头双向循环链表则恰恰与无...
    99+
    2022-11-12
  • C++带头双向循环链表怎么实现
    这篇文章主要介绍“C++带头双向循环链表怎么实现”，在日常操作中，相信很多人在C++带头双向循环链表怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++带头双向循环链表怎么实现”的疑惑有所帮助！接下来...
    99+
    2023-06-29
  • C++如何实现带头双向循环链表
    这篇文章主要为大家展示了“C++如何实现带头双向循环链表”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“C++如何实现带头双向循环链表”这篇文章吧。什么是带头双向循环链表什么是带头？双向？循环？(...
    99+
    2023-06-29
  • Python实现双向链表
    之前写的单向链表和环形链表都只是单向的，只能单向遍历，不能根据后面的节点获取前面的节点，除非进行反转操作。 双向链表每个节点都有两个指针，这两个指针分别指向前后两个节点，这样就可以从...
    99+
    2022-11-11
  • Java如何实现双向链表功能
    双向链表实现 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继...
    99+
    2022-11-12
  • java中的双向链表怎么实现
    在Java中，可以使用自定义的双向链表类来实现双向链表。以下是一个简单的双向链表的实现示例： public class Doubly...
    99+
    2023-10-24
    java
  • java实现双向链表的增删改
    双向链表：java实现双向链表的增删改，供大家参考，具体内容如下 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找 单向链表不能自我删除，需要靠辅助节点，而双向链表...
    99+
    2022-11-13
  • Java数据结构之链表实现（单向、双向链表及链表反转）
    前言 之前学习的顺序表查询非常快，时间复杂度为O(1)，但是增删改效率非常低，因为每一次增删改都会元素的移动。可以使用另一种存储方式-链式存储结构。 链表是一种物理存储单元上非连续、...
    99+
    2022-11-12
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作