广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > Python >Java实现双链表的示例代码
  • 709

0
分享到

Java实现双链表的示例代码

2024-04-02 19:04:59 709人浏览 安东尼

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

摘要

目录一、双向链表是什么二、具体方法实现定义结点下标访问异常获取链表长度打印链表清空链表头插法尾插法指定位置插入查找元素删除第一次出现的关键字删除所有值为key的节点三、完整代码一、双

一、双向链表是什么

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

LinkedList底层就是一个双向链表，我们来实现一个双向链表。

这里多一个尾指针，方便我们对尾插操作从O(n)降到O(1).每个结点多了前驱结点，方便我们对链表进行操作。

二、具体方法实现

定义结点

class Listnode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

下标访问异常

public class IndexWrongException extends RuntimeException{
    public IndexWrongException() {
    }

    public IndexWrongException(String message) {
        super(message);
    }
}

获取链表长度

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

打印链表

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

清空链表

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

头插法

public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

尾插法

public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }

指定位置插入

public void addIndex(int index,int data) throws IndexWrongException{
        if(index < 0 || index > size()) {
            throw new IndexWrongException("输入下标不合法");
        }
        ListNode node = new ListNode(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

查找元素

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

删除第一次出现的关键字

public void remove(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                        }
                    }
                return;
                }
            cur = cur.next;
            }
        }

删除所有值为key的节点

public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                    }
                }
            }
            cur = cur.next;
        }
    }

三、完整代码

public class LinkedList {
    static class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }
    ListNode head;
    ListNode tail;
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) throws IndexWrongException{
        if(index < 0 || index > size()) {
            throw new IndexWrongException("输入下标不合法");
        }
        ListNode node = new ListNode(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(head == null) {
            return false;
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                        }
                    }
                return;
                }
            cur = cur.next;
            }
        }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                    }
                }
            }
            cur = cur.next;
        }
    }
    //得到单链表的长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
    public void display(){
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.value+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear(){
        if(this.head == null) {
            return;
        }
        ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        tail = null;
    }
}

到此这篇关于Java实现双链表的示例代码的文章就介绍到这了,更多相关Java双链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

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

--结束END--

本文标题: Java实现双链表的示例代码

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

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

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

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

下载Word文档
去做题
猜你喜欢
  • Java实现双链表的示例代码
    目录一、双向链表是什么二、具体方法实现定义结点下标访问异常获取链表长度打印链表清空链表头插法尾插法指定位置插入查找元素删除第一次出现的关键字删除所有值为key的节点三、完整代码一、双...
    99+
    2022-11-13
  • java代码实现双向链表
    本文实例为大家分享了双向链表java实现代码，供大家参考，具体内容如下 一、双向链表简介 1、单链表的缺陷 单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据...
    99+
    2022-11-13
  • java双向循环链表的实现代码
    例1：复制代码 代码如下:package com.xlst.util; import java.util.HashMap;import java.util.Map;import ja...
    99+
    2022-11-15
    java 双向循环链表
  • JavaScript双向链表实现LRU缓存算法的示例代码
    目录目标什么是LRU简介硬件支持寄存器栈代码实现思路链表节点数据结构链表数据结构LRUCache数据结构完整代码测试目标 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束...
    99+
    2022-11-13
  • Python代码实现双链表
    本文实例为大家分享了Python代码实现双链表的具体代码，供大家参考，具体内容如下 双链表的每个节点有两个指针： 一个指向后一个节点，另一个指向前一个节点 class Node(ob...
    99+
    2022-11-11
  • 怎么用java代码实现双向链表
    这篇文章主要介绍“怎么用java代码实现双向链表”，在日常操作中，相信很多人在怎么用java代码实现双向链表问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”怎么用java代码实现双向链表”的疑惑有所帮助！接下来...
    99+
    2023-06-30
  • Golang实现单链表的示例代码
    目录1. 定义节点2. IsEmpty()：3. Length()：4. AddFromHead()：5. AddFromTail()：6. Insert()7. Delet ...
    99+
    2023-03-15
    Golang 单链表
  • C++代码实现双向链表
    本文实例为大家分享了C++实现双向链表的具体代码，供大家参考，具体内容如下 双向链表：两个指针域，一个指向前结点，一个指向后结点 list.h #pragma once #defin...
    99+
    2022-11-13
  • C语言带头双向循环链表的示例代码
    目录前言结构分析链表的基本操作实现创建节点初始化链表链表销毁打印链表链表尾插链表尾删链表头插链表头删链表查找链表pos位置前面去插入删除pos位置链表判空代码复用总代码及头文件前言 ...
    99+
    2022-11-13
    C语言带头双向循环链表 C语言 双向循环链表 C语言 循环链表
  • C++实现双向链表代码分析
    目录前言:一、双向链表优缺点二、C++实现分析（1）节点类（2）链表类分析（3）链表类构造函数（4）isEmpty()判断是否为空（5）size()获取链表长度（6）getNode(...
    99+
    2022-11-13
  • 怎么用Python代码实现双链表
    本文小编为大家详细介绍“怎么用Python代码实现双链表”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么用Python代码实现双链表”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。双链表的每个节点有两个指针： ...
    99+
    2023-06-30
  • C语言实现动态链表的示例代码
    目录结构体定义已经函数声明函数实现创建一个链表判断链表是否为空获得链表中节点的个数在某个特定的位置插入一个元素获得指定下标的节点的元素删除一个节点链表逆序链表的清空链表的销毁链表的遍...
    99+
    2022-11-13
  • C/C++实现线性单链表的示例代码
    目录线性单链表简介C语言实现代码C++语言实现代码线性单链表简介 使用链存储结构的线性存储结构为线性单链表,线性存储结构是元素逻辑结构一对一,链存储结构是元素物理结构不连续,线性单链...
    99+
    2022-11-13
  • Java实现双向链表
    本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下 1、双向链表 1.1 双向链表的每个节点组成包含节点数据，上一个节点（pre），下一个节点（next） ...
    99+
    2022-11-13
  • Python 实现链表实例代码
    Python 实现链表实例代码 前言 算法和数据结构是一个亘古不变的话题，作为一个程序员，掌握常用的数据结构实现是非常非常的有必要的。 实现清单 实现链表，本质上和语言是无关的。但是灵活度却和实现它的语言密...
    99+
    2022-06-04
    实例 链表 代码
  • java 相交链表的实现示例
    目录1.题目2.分析3.完整代码1.题目 相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null...
    99+
    2022-11-12
  • Java实现双端链表LinkedList
    目录一、LinkedList 介绍二、LinkedList 使用一、LinkedList 介绍 1️⃣LinkedList 是 Java 集合框架中一个重要的实现，其底层采用的双向链...
    99+
    2022-11-13
  • python双向链表的示例分析
    小编给大家分享一下python双向链表的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！python是什么意思Python是一种跨平台的、具有解释性、编译性...
    99+
    2023-06-14
  • 如何使用C++代码实现双向链表
    这篇文章主要介绍“如何使用C++代码实现双向链表”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“如何使用C++代码实现双向链表”文章能帮助大家解决问题。双向链表：两个指针域，一个指向前结点，一个指向后...
    99+
    2023-06-30
  • C语言实现无头单向链表的示例代码
    目录一、易错的接口实现 1.1 新节点开辟函数 1.2 尾插 1.3 尾删 二、常见简单接口 2.1 打印链表 2.2 节点计数器 2.3 判断是否为空链表 2.4 通过值查找节点 ...
    99+
    2022-11-12
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作