链表（Java）实现

2023年6月16日上午8:05 • 数据库 • 阅读 77

链表

先给出自定义的list接口，后面几种链表的实现了该接口

public interface List {
    //统计顺序表元素个数
    int size();

    //判断顺序表是否为空
    boolean isEmpty();

    //判断顺序表内是否有某个元素
    boolean contains(Object o);

    //向顺序表添加元素，添加成功放回true，向表尾添加
    boolean add(E e);

    //根据索引获取元素
    E get(int index);

    //根据索引设置元素
    void set(int index, E value);

    //根据索引移除元素
    E remove(int index);

    //向表头添加元素
    void addFirst(E e);

    //移除表头元素
    E removeFirst();

    //移除表尾元素
    E removeLast();
}

单向链表的实现

public class SingleLinkedList implements List {
    private int size = 0;
    private Node first;//链表头
    private Node last;//链表尾

    public SingleLinkedList() {}
    //内部类，对链表节点的抽象
    private static class Node{
        E data;
        Node next;

        public Node(E data) {
            this.data = data;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        //引用类型为空
        if(o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.data == null)
                    return true;
            }
        }
        else{
            //引用类型需要用equals()方法
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.data))
                    return true;
            }
        }
        return false;
    }

    @Override
    public boolean add(E e) {
        final Node l = last;//尾节点要指向新节点，先保存当前尾节点

        final Node node = new Node(e);
        last = node;
        //链表为空
        if (!isEmpty())
            first = node;//链表为空则新增节点成为首节点
        else
            l.next = node;//原尾节点指向新增节点
        size ++;
        return true;
    }

    private void CheckIndex(int index){
        //当索引超出范围，抛出异常
        if( index < 0 || index > size - 1 )
            throw new IndexOutOfBoundsException("index " + index + " out of bounds");
    }
    @Override
    public E get(int index) {
        CheckIndex(index);
        Node x = first;
        //遍历到索引位置
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        //返回数据
        return x.data;
    }

    @Override
    public void set(int index, E value) {
        CheckIndex(index);
        Node x = first;
        //遍历到索引位置
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        //修改数据
        x.data = value;
    }

    @Override
    public E remove(int index) {
        CheckIndex(index);
        Node x;//待删除节点
        Node p = first;//删除节点的前一个
        //待删除的是头节点
        if (index == 0) {
            x = first;
            first = first.next;
        } else {
            //遍历到被删除节点的前一个
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            x = p.next;//得到被删除节点
            p.next = x.next;
        }
        size --;
        return x.data;
    }

    @Override
    public void addFirst(E e) {
        Node node = new Node(e);
        final Node f = first;
        first = node;
        //链表为空，尾节点也要指向当前节点
        if (size == 0) {
            last = node;
        } else {
            node.next = f;
        }
        size ++;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size-1);
    }
}

循环链表的实现

循环链表相比单向链表，有以下部分需要对原来的代码修改。

contains()方法要设置退出机制
add()方法，链表不为空时，新增节点的next要指向first
remove()方法，要删除的是头节点，尾节点要指向新的first节点

public class SingleLinkedCircleList implements List {
    private int size = 0;
    private Node first;//链表头
    private Node last;//链表尾

    public SingleLinkedCircleList() {}

    //内部类，对链表节点的抽象
    private static class Node{
        E data;
        Node next;

        public Node(E data) {
            this.data = data;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        //引用类型为空
        if(o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.data == null)
                    return true;
                //设置退出机制：
                if (x.next == first)
                    break;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.data))
                    return true;
                //设置退出机制：
                if (x.next == first)
                    break;
            }
        }
        return false;
    }

    @Override
    public boolean add(E e) {
        final Node l = last;
        final Node node = new Node(e);
        last = node;

        //链表为空
        if(size == 0)
            first = node;
        else{
            l.next = node;
            node.next = first;
        }
        size ++;
        return true;
    }
    private void CheckIndex(int index){
        //当索引超出范围，抛出异常
        if( index < 0 || index > size - 1 )
            throw new IndexOutOfBoundsException("index " + index + " out of bounds");
    }
    @Override
    public E get(int index) {
        CheckIndex(index);
        Node x = first;
        //遍历到索引位置
        for (int i = 0; i < index; i++)
            x = x.next;
        //返回数据
        return x.data;
    }

    @Override
    public void set(int index, E value) {
        CheckIndex(index);
        Node x = first;
        //遍历到索引位置
        for (int i = 0; i < index; i++)
            x = x.next;
        //修改数据
        x.data = value;
    }

    @Override
    public E remove(int index) {
        CheckIndex(index);
        Node x;//待删除节点
        Node p = first;//删除节点的前一个
        //待删除的是头节点，尾节点要指向新的头节点
        if (index == 0) {
            x = first;
            first = first.next;
            last.next = first;
        }
        else{
            //遍历到被删除节点的前一个
            for (int i = 0; i < index - 1; i++)
                p = p.next;
            x = p.next;//得到被删除节点
            p.next = x.next;
        }
        size --;
        return x.data;
    }

    @Override
    public void addFirst(E e) {
        Node node = new Node(e);
        final Node f = first;
        first = node;
        //链表为空，尾节点也要指向当前节点
        if (size == 0) {
            last = node;
        } else {
            node.next = f;
            last.next = node;
        }
        size ++;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size - 1);
    }
}

循环链表解决约瑟夫问题

N个人围成一圈，从第K个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，K=1，M=5，被杀掉的顺序是：5，4，6，2，3。

约瑟夫问题用链表求解非常简单，首先last和first先同时移动k-1步，然后进入循环，每前进m-1步就删除当前first指向的节点，删除用两句代码就可以实现： first = first.next; last.next = first 。
将约瑟夫问题解决方法也封装到了循环链表中。

public void JosephSolution(int num, int start, int m){
        SingleLinkedCircleList list = new SingleLinkedCircleList();
        //初始化约瑟夫环
        for (int i = 0; i < num; i++)
            list.add(i+1);
        System.out.println("约瑟夫问题的出圈顺序");
        //移动(start - 1)到起始位置
        for (int i = 0; i < start - 1; i++) {
            list.first = list.first.next;
            list.last = list.last.next;
        }
        while(true){
            if(list.first == list.last) {
                System.out.println(list.first.data + "\n出圈结束");
                break;
            }
            //每向下走(m-1)次到达需要删除的节点上。
            for (int i = 0; i < m - 1; i++) {
                list.last = list.last.next;
                list.first = list.first.next;
            }
            System.out.printf(list.first.data + "->");
            //以下两行是解决问题的关键所在，删除了当前first节点。first指向下一节点。
            list.first = list.first.next;
            list.last.next = list.first;
        }
    }

双向链表的实现

双向链表可以在任意节点向前向后遍历，查找效率高于单向链表。不过会占据更多存储空间。与单向链表相比，以下部分需要修改。

add()方法，链表不为空时，新增节点的next要指向first。
get()和set()方法，根据索引位置选择从头找还是从尾找。
remove方法，从头开始找，删除头节点要特殊处理，其它情况时，被删除节点的下一节点的前驱指向p(此时p是被删除节点的前驱)；从尾开始找，删除为尾点节点要特殊处理，其它情况时，被删除节点的下一节点的后驱指向p(此时p是被删除节点的后驱)。 从头从尾处理是对称的。
addFirst()方法，链表不为空时，原来的首节点的前驱要指向当前新增加的节点。

public class LinkedList implements List {
    private int size = 0;
    private Node first;//链表头
    private Node last;//链表尾
    //内部类，对链表节点的抽象
    public LinkedList() {}

    private static class Node {
        E data;
        Node next;
        Node prev;

        public Node(E data) {
            this.data = data;
        }
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        //引用类型为空
        if(o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.data == null)
                    return true;
            }
        }
        else{
            //引用类型需要用equals()方法
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.data))
                    return true;
            }
        }
        return false;
    }

    @Override
    public boolean add(E e) {
        final Node node = new Node(e);
        final Node l = last;
        last = node;
        //链表为空
        if(isEmpty()){
            first = node;
        }else{
            l.next = node;
            node.prev = l;
        }
        size ++;
        return true;
    }
    private void CheckIndex(int index){
        //当索引超出范围，抛出异常
        if( index < 0 || index > size - 1 )
            throw new IndexOutOfBoundsException("index " + index + " out of bounds");
    }
    @Override
    public E get(int index) {
        CheckIndex(index);
        Node x;
        //索引靠后，则从前往后遍历
        if(index < (size >> 1)){
            x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
        }
        //索引靠后从后往前找
        else{
            x = last;
            for (int i = 0; i < size - index - 1; i++)
                x = x.prev;
        }
        return x.data;
    }

    @Override
    public void set(int index, E value) {
        Node x;
        CheckIndex(index);
        if(index < (size >> 1)){
            x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
        }
        //索引靠后从后往前找
        else{
            x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
        }
        x.data = value;
    }

    @Override
    public E remove(int index) {
        CheckIndex(index);
        final Node x;//指向被删除节点
        Node p;//指向被删除节点的前驱节点或者后驱节点

        //索引靠后，则从前往后遍历
        if (index < (size >> 1)) {
            //删除头指针，特殊处理
            if (index == 0) {
                x = first;
                first = x.next;
            } else {
                p = first;//从前往后找被删除节点的前驱节点
                for (int i = 0; i < index - 1; i++)
                    p = p.next;
                x = p.next;//x指向被删除节点
                p.next = x.next;
                x.next.prev = p;//被删除节点的下一节点的前驱指向p
            }
        }
        //索引靠后从后往前找
        else {
            //因为是从后往前找，删除尾节点也要同上面一样的方式处理
            if (index == size - 1) {
                x = last;
                last = x.prev;
            }else {
                p = last;
                for (int i = size - 1; i > index + 1; i--)
                    p = p.prev;//从后往前找删除节点的后驱节点
                x = p.prev;
                p.prev = x.prev;
                x.prev.next = p;//被删除节点的下一节的后驱指向p
            }
        }
        size --;
        return x.data;
    }

    @Override
    public void addFirst(E e) {
        Node node = new Node(e);
        final Node f = first;
        first = node;
        //链表为空，尾节点也要指向当前节点
        if (size == 0) {
            last = node;
        } else {
            node.next = f;
            f.prev = node;
        }
        size ++;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size - 1);
    }
}

LeetCode链表练习题

非递归方法:

使用两个指针遍历链表(head和slow)，一个临时指针(temp)保存下一节点位置，这里要注意的问题是slow一开始要指向空，如果让slow指向head，head指向head.next，这种初状态转来遍历链表的话会出现环。

public ListNode reverseList(ListNode head) {
        ListNode fast = head;
        ListNode slow = null;
        ListNode temp;
        while(head != null){
            temp = head.next;
            head.next = slow;
            slow = head;
            head = temp;
        }
        return slow;
    }

递归方法:

递归方法的思路是将head推到最后，然后在回溯的过程中，把节点的指向反转，同样要考虑形成环的可能。除此之外，写这道题意外的抛出了空指针异常，这是因为 if(head == null || head.next == null) 和 if(head.next == null || head == null) 是不一样的。如果链表为空，后一句先判断head.next == null，而head指向空没有next域，于是抛出空指针异常。

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;//没有这一行会出现环。
        return res;
    }

非递归方法

一开始的思路是操作两个链表，然后插入另一个链表的节点，过程比较复杂，把自己给绕晕了。后来看了别人的解法，可以创建一个新的节点，然后只需要比较两个链表当前指向节点的数据大小，就可以让node的next指向它。如果一个链表为空，可以把另外一个链表后续的所有节点直接挂到next上

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode();
        ListNode dummy = node;
        while(list1!=null && list2!=null){
            if(list1.val

递归方法：

递归的解法很巧妙，没有多余空间的开销，而是只用两个链表就完成了操作，思路是分治法的思想：比较两个链表当前指向节点的数据域，小的那一个链表节点的next将指向以它下一个节点作为头节点的链表和和另外一个链表的合并。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1==null)
        return list2;
    if(list2==null)
        return list1;
    if(list1.val < list2.val){
        list1.next = mergeTwoLists(list1.next,list2);
        return list1;
    }else{
        list2.next = mergeTwoLists(list1,list2.next);
        return list2;
    }
}

链表的实现参考《数据结构与算法基础（Java语言实现）》作者：柳伟卫北京大学出版社

Original: https://www.cnblogs.com/yjh1024/p/16558174.html
Author: Nights_Watch
Title: 链表（Java）实现

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/622263/

转载文章受原作者版权保护。转载请注明原作者出处！

数据库

【自取】最近整理的，有需要可以领取学习：

Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言刷题答案下载！

CSS进阶内容——布局技巧和细节修饰

CSS进阶内容——布局技巧和细节修饰我们在之前的文章中已经掌握了CSS的大部分内容，但仍有一些内容我们没有涉略，这篇文章就是为了补充前面没有涉及的内容，为我们的知识做出补充并且介…

数据库 2023年6月14日
0078
linux ftp报530 530 Login incorrect pam_unix(crond:account): expired password for user

今天用FTP登录服务器，要传些数据文件，一直登录不上，重启之后依然无法登陆。就提交了工单，阿里云的售后居然在网上给我找了两篇处理530的帮助文档，直接无语！无奈… …

数据库 2023年6月14日
00118
DM-DM之间的DBLINK

1 创建外部链接创建一个外部链接。语法格式 CREATE [OR REPLACE] [PUBLIC] LINK STANDBY FIRST | PRIMARY ONLY | S…

数据库 2023年6月11日
0067
一，Flink快速上手

1.依赖配置 1.1 pom文件 8 8 1.13.0 1.8 2.12 1.7.30 org.apache.flink flink-java ${flink.version} o…

数据库 2023年6月6日
0085
锁定文件失败打不开磁盘“D:Windows7Windows7 64 位.vmdk”或它所依赖的某个快照磁盘。模块“Disk”启动失败。

Windows7虚拟机非正常关闭，再次打开有时候会出现”锁定文件失败，打不开磁盘……”的错误提示解决办法：打开虚拟机所在路径删除.v…

数据库 2023年6月14日
0079
MySql 删除数据表

定义：删除数据表就是删除数据库中已经存在的表。请注意，当表被删除时，表的定义和表中的所有数据都将被删除。因此，在执行删除操作之前，最好对表中的数据进行备份，以避免无法挽回的后果。…

数据库 2023年5月24日
0075
2. 函数

404. 抱歉，您访问的资源不存在。可能是URL不正确，或者对应的内容已经被删除，或者处于隐私状态。 [En] It may be that the URL is incorre…

数据库 2023年5月24日
0082
《Unix环境高级编程》笔记

基础 Unix操作系统体系结构操作系统就是一种软件，它管理控制计算机的硬件资源，提供程序运行的环境，这种软件又被称为内核（Kernel）。内核提供的接口被称为系统调用（Syste…

数据库 2023年6月11日
0096
list对象中的数据如何去重呢？

下文笔者讲述list对象的去重方法分享，list的实现类是我们存储数据的容器，当里面存储的对象存在重复值时，我们该如何对其进行去重操作呢？下文笔者将一一道来，首先我们需了解对象…

数据库 2023年6月11日
0084
docker部署mysql集群

docker部署mysql集群 1.0 安装环境 1.1 安装Centos7 Docker官方建议在Ubuntu中安装，因为Docker是基于Ubuntu发布的，而且一般Docke…

数据库 2023年6月9日
0085
【必知必会】手把手教你配置MySQL环境变量——图文详解

一、先决条件假设我们已经成功安装MySQL数据库。如果还有小伙伴不知道如何安装MySQL数据库，可以在本文下留言，留言数超20，则出一期”手把手教你安装MySQL数据…

数据库 2023年6月14日
0049
对于Java循环中的For和For-each，哪个更快

Which is Faster For Loop or For-each in Java 对于Java循环中的For和For-each，哪个更快通过本文，您可以了解一些集合遍历技…

数据库 2023年6月11日
0078
redhat 7.4从openssh7.6离线升级openssh8.4p1解决方法

具体需求这几天生产环境服务器又进行了安全扫描，每次都会报一下漏洞错误。虽然只有一个高危问题，但是每次看到ssh远程漏洞都很烧脑 “主要是里面坑太多了”，闲…

数据库 2023年6月14日
0069
DNS 查询原理详解

你可能会问，难道 DNS 服务器（比如 1.1.1.1）保存了世界上所有域名（包括二级域名、三级域名）的 IP 地址？当然不是。DNS 是一个分布式系统，1.1.1.1 只是用户…

数据库 2023年6月14日
0094
学会Linux，看完这篇就行了！

转载请注明出处❤️ 作者：测试蔡坨坨原文链接：caituotuo.top/797ab07d.html 你好，我是测试蔡坨坨。对于测试同学来说，Linux基本属于必学必会内容，招…

数据库 2023年6月11日
0069
Hadoop生态二—Hadoop资源管理调度平台Yarn

Yarn是一个资源调度平台，负责为运算程序提供服务器运算资源，相当于一个分布式的操作系统平台，而mapreduce等运算程序则相当于运行于操作系统之上的应用程序Yarn是一个资源调…

数据库 2023年6月6日
00105

2024 年 4 月
一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30