文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

java中单向链表和双向链表是什么

2023-06-19 10:34

关注

小编给大家分享一下java中单向链表和双向链表是什么,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

一、链表简介

1、链表概念

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,节点可以在运行时动态生成,节点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

2、基础特点

内存存储

java中单向链表和双向链表是什么

逻辑结构

java中单向链表和双向链表是什么

特点描述

链表结构解决数组存储需要预先知道元素个数的缺陷,可以充分利用内存空间,实现灵活的内存动态管理。

二、单向链表

1、基础描述

java中单向链表和双向链表是什么

单向链表是链表的一种,其特点是链表的链接方向是单向的,链表的遍历要从头部开始顺序读取;结点构成,head指针指向第一个成为表头结点,终止于最后一个指向NULL的指针。

2、基础操作

添加数据

java中单向链表和双向链表是什么

删除数据

java中单向链表和双向链表是什么

遍历找到要删除的节点,把删除节点前个节点的指针指向该删除节点的下个节点;

三、双向链表

1、概念描述

java中单向链表和双向链表是什么

双向链表也叫双链表,是链表的一种,链表的每个数据结点中都有两个指针,分别指向直接后继和直接前驱,从双向链表中的任意一个结点开始,都可以很快速地访问它的前驱结点和后继结点,链表结构的使用多数都是构造双向循环链表。

2、基础操作

添加数据

java中单向链表和双向链表是什么

删除数据

java中单向链表和双向链表是什么

通过上述流程的操作,就把链表中一个节点删除,剩下节点再度连接成链式结构。

3、源码分析

在Java的API中,LinkedList是典型的双向链表结构,下面基于LinkedList源码看双向链表的操作。

基础案例

public class M01_Linked {    public static void main(String[] args) {        List<User> userList = new LinkedList<>() ;        User removeUser = new User(200,"Second") ;        // 添加元素        userList.add(new User(100,"First")) ;        userList.add(removeUser) ;        userList.add(new User(300,"Third")) ;        System.out.println("初始化:"+userList);        // 修改元素        userList.get(0).setUserName("Zero");        System.out.println("修改后:"+userList);        // 删除元素        userList.remove(removeUser) ;        System.out.println("删除后:"+userList);    }}class User {    private Integer userId ;    private String userName ;    public User(Integer userId, String userName) {        this.userId = userId;        this.userName = userName;    }    @Override    public String toString() {        return "User{" +                "userId=" + userId +                ", userName='" + userName + '\'' +                '}';    }    // 省略Get和Set方法}

节点描述

节点三个核心描述:数据,next指针,prev指针。

private static class Node<E> {    E item;         // 数据    Node<E> next;   // 下个指针    Node<E> prev;   // 上个指针    Node(Node<E> prev, E element, Node<E> next) {        this.item = element;        this.next = next;        this.prev = prev;    }}

首位节点处理

基于LinkedList源码,首尾节点方式,针对上图双链表的首位指针特点,这里源码很好理解。

public class LinkedList {    transient Node<E> first;    transient Node<E> last;    // 处理首节点    private void linkFirst(E e) {        final Node<E> f = first;        final Node<E> newNode = new Node<>(null, e, f);        first = newNode;        if (f == null)            last = newNode;        else            f.prev = newNode;    }    // 处理尾节点    void linkLast(E e) {        final Node<E> l = last;        final Node<E> newNode = new Node<>(l, e, null);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;    }}

添加节点

添加节点的方法直接调用linkLast方法,把新节点放到链表的尾部即可。

public boolean add(E e) {    linkLast(e);    return true;}

删除节点

遍历对比,找到要删除的节点;

public boolean remove(Object o) {    if (o == null) {        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {                unlink(x);                return true;            }        }    } else {        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {                unlink(x);                return true;            }        }    }    return false;}

移除节点,重新搭建链表结构,并且把当前链表的数据置为null,并返回被移除的节点;

E unlink(Node<E> x) {    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    x.item = null;    return element;}

如上就是对Java中LinkedList双链表源码的部分结构分析,这种代码看多了,总感觉自己写的代码不是Java。

四、环形链表

在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点,这样就形成了环形链表:

java中单向链表和双向链表是什么

环形链表链表的一种结构,特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

以上是“java中单向链表和双向链表是什么”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯