Java实现链表

鲜于言悠

发布于 2024-05-30 13:00:01

870

发布于 2024-05-30 13:00:01

文章被收录于专栏：c/c++的学习笔记

链表

前言
一、链表的概念及结构
二、链表的分类
三、链表的实现
- 无头单向非循环链表实现
- 无头双向链表实现
- 具体代码
四、链表习题
五、顺序表和链表的区别

前言

推荐一个网站给想要了解或者学习人工智能知识的读者，这个网站里内容讲解通俗易懂且风趣幽默，对我帮助很大。我想与大家分享这个宝藏网站，请点击下方链接查看。 https://www.captainbed.cn/f1

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是，它不需要在内存中连续存储，因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择，尤其是在需要动态调整数据结构大小的场景中。

在链表的实现中，通常会有头节点和尾节点之分。头节点是链表的第一个节点，而尾节点是链表的最后一个节点。通过遍历链表，我们可以访问链表中存储的所有数据。链表还支持在链表头部或尾部快速添加新节点，这些操作的时间复杂度通常为O(1)。

然而，链表也有一些缺点。比如，访问链表中的某个特定节点需要从头节点开始遍历，这导致访问链表中间节点的平均时间复杂度为O(n)。此外，链表需要额外的空间来存储指针，这增加了内存的使用。

链表有多种类型，如单向链表、双向链表和循环链表等。单向链表是最简单的链表类型，每个节点只有一个指向下一个节点的指针。双向链表则允许节点同时指向前一个和下一个节点，这使得双向链表在某些操作上比单向链表更高效。循环链表则是将尾节点的指针指向头节点，形成一个闭环。

在实际应用中，链表常用于实现栈、队列和哈希表等数据结构。例如，链表可以作为栈的底层数据结构，实现元素的先进后出。此外，链表还可以用于实现动态数组，支持元素的动态插入和删除。

总之，链表作为一种重要的数据结构，在编程和数据处理中发挥着重要作用。尽管链表在某些方面存在不足，但其灵活性和高效性使得它在许多场景中仍然是理想的选择。通过深入了解链表的特性和应用，我们可以更好地利用这种数据结构来解决实际问题。

一、链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

现实中数据结构中

二、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向或者双向

带头或者不带头

循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三、链表的实现

无头单向非循环链表实现

// 1、无头单向非循环链表实现
public class SingleLinkedList {
 //头插法
public void addFirst(int data);
 //尾插法
public void addLast(int data);
 //任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
 //查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
 //删除第一次出现关键字为key的节点
public void remove(int key);
 //删除所有值为key的节点
public void removeAllKey(int key);
 //得到单链表的长度
public int size();
 public void display();
 public void clear();
 }

无头双向链表实现

// 2、无头双向链表实现
public class DoubleLinkedList {
 //头插法
public void addFirst(int data);
 //尾插法
public void addLast(int data);
 //任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
 //查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
 //删除第一次出现关键字为key的节点
public void remove(int key);
 //删除所有值为key的节点
public void removeAllKey(int key);
 //得到单链表的长度
public int size();
 public void display();
 public void clear();
 }

具体代码

// 2、使用无头单向非循环链表实现
public class SingleLinkedList {
    private Node head; // 头节点

    // 节点类
    private class Node {
        private int data; // 数据
        private Node next; // 下一个节点

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

    // 头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    // 尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }

    // 任意位置插入
    public boolean addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            return false;
        }
        if (index == 0) {
            addFirst(data);
            return true;
        }
        if (index == size()) {
            addLast(data);
            return true;
        }
        Node newNode = new Node(data);
        Node cur = findNode(index - 1);
        newNode.next = cur.next;
        cur.next = newNode;
        return true;
    }

    // 查找是否包含关键字
    public boolean contains(int key) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 删除第一个出现的关键字节点
    public void remove(int key) {
        if (head == null) {
            return;
        }
        if (head.data == key) {
            head = head.next;
            return;
        }
        Node cur = head;
        while (cur.next != null && cur.next.data != key) {
            cur = cur.next;
        }
        if (cur.next != null) {
            cur.next = cur.next.next;
        }
    }

    // 删除所有值为关键字的节点
    public void removeAllKey(int key) {
        if (head == null) {
            return;
        }
        // 处理头节点的情况
        while (head != null && head.data == key) {
            head = head.next;
        }
        // 处理其他节点的情况
        Node cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.data == key) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
    }

    // 获取链表长度
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 查找指定位置的节点
    private Node findNode(int index) {
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    // 打印链表
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 清空链表
    public void clear() {
        head = null;
    }
}

四、链表习题

给定一个链表，判断链表中是否有环【思路】快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，…n步行吗？

给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL

解决像这样的题目，我们可以找等式，通过等式来找出相应的关系

结论让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
证明

给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。要求返回这个链表的深度拷贝
其他。ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，大家可以先把c++学一下，在逐步开始刷题 Leetcode + 牛客

五、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低