链表是啥?如何搞定它?

简介: 链表是啥?如何搞定它?

前言

链表是一种 递归 的数据结构,或者为空 null,或者指向一个结点(node)的引用,一个结点含有 一个泛型元素和一个指向另一条链表的引用。


通常分为如下三种类型:


单向链表:结点被分成两个部分。第一个部分保存或者显示关于结点的信息,第二个部分存储下一个结点的地址,只能向一个方向遍历。

双向链表:每个数据结点中都有两个指针,分别指向直接后继和直接前驱。

循环链表:一种 链式存储结构,它的最后一个结点指向头结点,形成一个环。

单向链表

单向链表包括一个值和一个指向下一结点的指针,其典型结构定义如下:


image.png

public class Node{
    // 数据对象
    private Object val;
    // 指向后继结点
    private Node next;
    // 无参构造函数
    public Node(){
        // 指向数据对象和后继结点的引用都置空
        this.val = null;
        this.next = null;
    }
    // 有参构造函数
    public Node(Object val, Node node){
        this.val = val;
        this.next = node;
    }
    // 获取当前存放位置的数据对象
    public Object getVal(){
        return this.val;
    }
    // 将给定元素存放至当前位置,同时返回此前存放的数据对象
    public Object setVal(Object value){
        Object oldVal = this.val;
        this.val = value;
        return oldVal;
    }
    // 取当前结点后继结点
    public Node getNext(){
        return this.next;
    }
    // 修改当前结点后继结点
    public void setNext(Node newNext){
        this.next = newNext;
    }
}

image.png

public class DoubleNode{
  // 数据对象
    private Object val; 
    // 指向前驱结点
    private DoubleNode prev;
    // 指向后继结点
    private DoubleNode next;
    // 无参构造函数
    public DoubleNode(){
        this.val = null;
        this.prev = null;
        this.next = null;
    }
    // 有参构造函数
    public DoubleNode(Object value, DoubleNode previous, DoubleNode next){
        this.val = value;
        this.prev = previous;
        this.next = next;
    }
    // 获取当前位置数据对象
    public Object getVal(){
        return val;
    }
    // 将给定元素放在当前位置,返回此前存放的元素
    public Object setVal(Object value){
        Object oldVal = val;
        val = value;
        return oldVal;
    }
    // 获取当前结点后继结点
    public DoubleNode getNext(){
        return next;
    }
    // 修改后继结点
    public void setNext(DoubleNode newNext){
        next = newNext;
    }
    // 获取当前位置前驱结点
    public DoubleNode getPrev(){
        return prev;
    }
    // 修改前驱结点
    public void setPrev(DoubleNode newPrev){
        prev = newPrev;
    }
}

单向链表的增删改查

基于链表实现栈

public class MyStack{
    // 指向栈顶元素(头结点)
    private Node head;
    // 栈中元素数目
    private int size;
    // 构造方法(构造一个空栈)
    public MyStack(){
        this.head = null;
        this.size = 0;
    }
    // 查询栈中元素个数
    public int getSize(){
        return size;
    }
    // 判断栈是否为空
    public boolean isEmpty(){
        return head == null;
        // 或者 size == 0;
    }
    // 读取栈顶(首结点信息)
    public Object getTop(){
        if(isEmpty()){
            System.out.println("栈空");
        }     
        return head.getVal();
    }
    // 压栈(即插入首结点)
    public void insertAtHead(Object val){
        // 创建一个新结点,将其作为首结点插入
        Node node = new Node(val, head);
        // 更新首结点引用
        head = node;
        // 栈中元素数目增加
        size++;
    }
   // 出栈(删除首结点)
    public Object removeAtHead(){
        if(isEmpty){
            System.out.println("栈空");
        }
        // 当前结点数据对象
        Object tmp = head.getVal();
        // 更新首结点引用
        head = head.getNext();
        size--;
        return tmp;
    }
} 

基于链表实现队列

public class MyQueue{
    // 队列首元素(首结点)
    private Node head;
    // 队列尾元素(尾结点)
    private Node tail;
    // 队列规模
    private int size;
    // 构造空队列
    public MyQueue(){
        head = null;
        tail = null;
        size = 0;    
    }
    // 队列规模
    public int getSize(){
        return size;
    }
    // 判断当前队列是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    // 查看队首元素
    public Object getFront(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        return head.getElem();
    }
    // 入队
    public void enQueue(Object val){
        Node node = new Node();
        // 新结点作为末结点插入
        node.setVal(val);
        node.setNext(null);
        // 若当前队列为空,则直接插入
        if(size == 0){
            head = node;
        }else {
            // 否则将新结点接至队列末端
            tail.setNext(node);
        }
        // 更新指向末结点的引用
        tail = node;
        // 更新队列规模
        size++;
    }
    // 出队
    public Object deQueue(){
        if(size == 0){
            System.out.println("队列为空");
        }
        Object tmp = head.getVal();
        head = head.getNext();
        // 更新队列规模
        size--;
        // 队列为空时,将末结点引用置空
        if(size == 0){
            tail = null;
        }
        return tmp;
    }
    // 遍历队列
    public void traversal(){
        Node node = head;
        while(node != null){
            System.out.println(node.getVal() + "\t");
            node = node.getNext();
        }
    }
}

双向链表的增删改查

实现双向链表时,通常在最前端和最后端各设置一个 哑元结点,分别称为 头结点 和 尾结点,起着 哨兵 的作用。但实际上两者并不存储任何实质的数据对象,头(尾)结点的 next(prev)引用指向首(末)结点,而 prev(next)引用为空。


首尾结点的插入

假设要进行首结点的插入,则通常需要如下步骤,而末结点的插入则是和首结点的插入过程对称。


首先生成一个新结点;

然后将其接入队列的前端;

接着将头结点的 next 的引用指向新插入的结点,同时将首结点的 prev 的引用指向新插入的结点。

首尾结点的删除

假设要进行末结点的删除,通常需要如下步骤,而首结点的删除过程适合尾结点的删除过程对称。


将新的末结点的 next 引用指向尾结点;

同时将尾结点的 prev 引用指向新的末结点;

最后原先的末结点将会被系统回收。

一般结点的插入与删除

要实现在一般结点之间插入新结点,通常需要进行如下步骤:


创建一个新的结点,然后将其 prev 引用指向前一个结点,同时将其 next 引用指向后一个结点;

然后将前一个结点的 next 引用指向新结点,同时将后一个结点的 prev 引用指向新结点。

而要实现在一般结点之间删除结点,通常需要进行如下步骤:


首先找到要删除的结点的前驱和后继结点;

然后将其前驱结点的 next 引用指向后驱结点,同时将后驱结点的 prev 引用指向前驱结点。


public class MyDoubleQueue{
    // 指向头结点(哨兵)
    private DoubleNode header;
    // 指向尾结点(哨兵)
    private DoubleNode trailer;
    // 队列规模
    private int size;
    // 无参构造函数
    public MyDoubleQueue(){
        header = new DoublNode();
        trailer = new DoubleNode();
        header.setNext(trailer);
        trailer.setPrev(trailer);
        size = 0;
    }
    // 获取当前队列规模
    public int getSize(){
        return size;
    }
    // 判断队列是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    // 取首元素
    public Object getHead(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        return header.getNext().getVal();
    }
    // 取末元素
    public Objecct getTrail(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        return trailer.getPrev().getVal();
    }
    // 遍历
    public void traversal(){
        DoubleNode node = header.getNext();
        while(node != trailer){
            System.out.print(node.getVal() + "\t");
            node = node.getNext();
        }
        System.out.println();
    }
    // 前端插入新结点
    public void insertFirst(Object val){
        DoubleNode second = header.getNext();
        DoubleNode first = new DoubleNode(val, header, second);
        second.setPrev(first);
        header.setNext(first)
            size++;
    }
    // 前端删除结点
    public Object removeFirst(){
        if(isEmpty()){
            System.out.println("队列为空"); 
        }
        // first 是要删除的结点,找到要删除结点的后继结点 second
        DoubleNode first = header.getNext();
        DoubleNode second = first.getNext();
        // 要删除结点的值
        Object value = first.getVal();
        // 将头结点的 next 指向要删除的后继结点 second,同时将 second 的前驱结点指向头结点
        header.setNext(second);
        second.setPrev(header);
        // 更新规模
        size--;
        return value;
    }
    // 后端插入新结点
    public void insertLast(Object val){
        DoubleNode second = trailer.getPrev();
        DoubleNode first = new DoubleNode(val, second, trailer);
        second.setNext(first);
        trailer.setPrev(first);
        size++;
    }
    // 后端删除结点
    public Object removeLast(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        DoubleNode first = trailer.getPrev();
        DoubleNode second = first.getPrev();
        // 要删除结点的值
        Object value = first.getVal();
        // 将尾结点的 prev 指向要删除的前驱结点 second,同时将 second 的后继结点指向尾结点
        trailer.setPrev(second);
        second.setNext(trailer);
        // 更新规模
        size--;
        return value;
    }
}

总结

本文从单向链表和双向链表的结构定义出发,然后又分别介绍了如何基于单向链表实现堆和栈,最后则是对双向链表的增删改查进行了总结。对于文中有疏漏的地方,欢迎评论留言。如果你觉得文章对你有所帮助,那就点个赞再走吧!

目录
相关文章
Beyond Compare 4密钥过期解决办法,超实用
Beyond Compare 4密钥过期解决办法,超实用
27178 1
|
机器学习/深度学习 人工智能 安全
云端防御战线:云计算环境中的网络安全策略
【4月更文挑战第22天】 在数字化时代,云计算已成为企业运营的关键基础设施。然而,随着其广泛应用,云服务也成为了网络攻击者的主要目标。本文深入探讨了云计算环境下的网络安全挑战,分析了云服务提供者和使用者面临的安全威胁,并提出了综合性的安全策略。这些策略不仅包括传统的加密和身份验证技术,还涉及更先进的入侵检测系统、行为分析和机器学习算法。文章旨在为读者提供一个关于如何在享受云计算带来的便利同时确保数据和操作安全的综合指南。
Swiper库和Glide.js库的性能有何区别
Swiper和Glide.js是两个流行的响应式轮播图库。Swiper功能强大且灵活,支持多方向滑动,拥有丰富的配置和切换效果,适合复杂需求,其高性能得益于优化的算法和惰性加载。Glide.js则轻量级、快速,专注于基础功能,适合简洁需求。两者各有侧重,选择应基于项目具体需求和性能考虑。
|
前端开发 Java Android开发
打造 Compose 版本的 Banner
打造 Compose 版本的 Banner
483 0
打造 Compose 版本的 Banner
|
NoSQL Java 中间件
kkbida - 开源消息投递中间件详细解析
kkbida - 开源消息投递中间件详细解析 项目简介 kkbida为凯京科技开源的消息投递中间件,谐音必达,旨在保证异构系统间消息通知时消息投递必达,详情见 https://gitee.com/kekingcn/kkbida 快速开始 从gitee拉取代码 git clone https://gitee.
1641 75
|
SQL 监控 JavaScript
基于Quartz编写一个可复用的分布式调度任务管理WebUI组件
创业小团队,无论选择任何方案,都优先考虑节省成本。关于分布式定时调度框架,成熟的候选方案有XXL-JOB、Easy Scheduler、Light Task Scheduler和Elastic Job等等,其实这些之前都在生产环境使用过。但是想要搭建高可用的分布式调度平台,这些框架(无论是否去中心化)都需要额外的服务器资源去部署中心调度管理服务实例,甚至有时候还会依赖一些中间件如Zookeeper。
358 0
基于Quartz编写一个可复用的分布式调度任务管理WebUI组件
|
JavaScript 前端开发
Vue 2.x折腾记 - (17) 基于Ant Design Vue 封装一个配置式的表单组件
写了个类似上篇搜索的封装,但是要考虑的东西更多。 具体业务比展示的代码要复杂,篇幅太长就不引入了。
534 0
|
JavaScript 前端开发
Taro+React Redux最简单最简单的使用方法
React Redux最简单最简单的使用方法
|
机器学习/深度学习 缓存 Oracle
【数据库设计与实现】第7章:缓存与检查点
缓存与检查点设计原则数据缓冲区与检查点是相辅相成的,所以放在同一个章节介绍。由于CPU与持久化设备之间存在巨大的速度差距,所以在内存中引入缓冲区缩小这个差距。从读的角度来看,将热点数据或预判用户可能读取的数据提前加载到内存中,从而将持久化设备的读时延和带宽提升至内存的时延和带宽。从写的角度来看,直接修改缓冲区中的数据而不是磁盘中的数据,可以带来两方面的优势。其一,将持久化设备的写时延和带宽提升至内
【数据库设计与实现】第7章:缓存与检查点
|
Dubbo 应用服务中间件 Nacos
Nacos注册部署使用
Nacos注册部署使用
224 0
Nacos注册部署使用

热门文章

最新文章