当前位置： 首页 > article >正文

链表的底层实现（Java版）（单向，双向，循环）

article 2025/2/22 2:16:38

目录

一.什么是链表？

链表的类型

链表的特点

使用场景：

二.单向链表的实现：

首先创建节点类以及对应的构造方法：

然后创造头结点（哨兵结点），方便找到固定的位置来对链表进行操作：

最后列出简单的对链表的增删改查操作： 

三.双向链表的实现：

首先创建节点类以及对应的构造方法：

 然后创建头尾哨兵，便于在两哨兵中间插入元素以及双向链表的操作：

随后创建这个双向链表的构造方法：

最后实现对双向链表的操作： 

四.双向循环链表的实现：

 首先创造哨兵结点以及其构造函数：

随后实现对双向循环链表的操作： 

一.什么是链表？

链表（Linked List） 是一种线性数据结构，其中元素称为节点（Node）。每个节点包含两个部分：

  1. 数据域（data）：存储节点的值。
  2. 指针域（next）：存储下一个节点的地址（或引用），指向链表中的下一个节点。

与数组不同，链表的元素在内存中不一定连续存储。链表的灵活性在于可以动态调整大小，因为元素的插入和删除操作不涉及移动其他元素。

链表的类型

  1. 单向链表（Singly Linked List）：每个节点只有一个指针指向下一个节点。
  2. 双向链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。
  3. 循环链表（Circular Linked List）：链表的最后一个节点指向第一个节点，形成一个闭环。

链表的特点

  • 动态大小：与数组不同，链表不需要在创建时指定大小。
  • 插入和删除效率高：特别是在中间或开头插入和删除操作，链表的效率要高于数组。
  • 随机访问效率低：由于链表节点不连续存储，无法像数组那样通过索引直接访问元素。

 

使用场景：

  • 频繁插入和删除：在需要频繁在中间插入和删除元素的场景，链表表现较好，因为插入和删除操作的时间复杂度为 O(1)，不需要像数组那样移动元素。
  • 动态大小：当不确定数据的大小时，链表比数组更适合，因为它可以根据需要动态调整大小。
  • 内存碎片化：链表不要求内存连续分配，适合在内存较为分散的场景。

二.单向链表的实现：

每个节点只有一个指针指向下一个节点。 

 

首先创建节点类以及对应的构造方法：

//结点类
//做成内部类，以此来对外隐藏
private static class Node {
    int value; // 值
    Node next; // 下一个结点指针

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

然后创造头结点（哨兵结点），方便找到固定的位置来对链表进行操作：

private Node head = new Node(666,null);

最后列出简单的对链表的增删改查操作： 

package LinkListStudy;

import java.util.Iterator;
import java.util.function.Consumer;

public class SinglyLinkedListSentinel implements Iterable<Integer> {
    //头指针
//    private Node head = null;
    //哨兵结点
    private Node head = new Node(666,null);

    //迭代器遍历链表
    @Override
    public Iterator<Integer> iterator(){
        //匿名内部类 -> 带名字的内部类
        return new Iterator<>() {
            //头结点为哨兵结点，需要从下一个结点开始
            Node pointer = head.next;

            @Override
            public boolean hasNext() {
                return pointer != null;
            }

            @Override
            public Integer next() {
                int v = pointer.value;
                pointer = pointer.next;
                return v;
            }
        };
    }

    //结点类
    //做成内部类，以此来对外隐藏
    private static class Node {
        int value; // 值
        Node next; // 下一个结点指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    //向链表中添加元素
    public void addFirst(int value) {
        //链表为空
//        head = new Node(value, null);
        //链表非空
//        head = new Node(value, head);
        insert(0,value);
    }

    //使用函数式接口遍历链表
    public void loop1(Consumer<Integer> consumer) {
        Node pointer = head;
        while (pointer != null) {
            consumer.accept(pointer.value);//consumer接受数据
            pointer = pointer.next;//指针移动
        }
    }
    public void loop2(Consumer<Integer> consumer) {
        for (Node pointer = head.next; pointer != null; pointer = pointer.next) {
            consumer.accept(pointer.value);
        }
    }

    //寻尾部结点对象
    public Node findLast(){
        for(Node pointer = head.next;; pointer = pointer.next) {
            if(pointer.next == null){
                return pointer;
            }
        }
    }

    //尾插法
    public void addLast(Integer value) {
        Node last = findLast();
        //插入
        last.next = new Node(value, null);
    }

    //获取结点索引值
    public Node findNode(int index){
        //哨兵为 -1 索引
        int i = -1;
        for(Node pointer = head; pointer != null; pointer = pointer.next,i++) {
            if(i == index){
                return pointer;
            }
        }
        return null;
    }

    //返回某一位置索引值
    public int get(int index) throws IllegalArgumentException{
        Node node = findNode(index);
        if(node == null) {
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index));
        }
        return node.value;
    }

    //向索引位置插入
    public void insert(int index, int value) throws IllegalArgumentException{
        Node node = findNode(index - 1);
        if(node == null){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));
        }
        node.next = new Node(value, node.next);
    }

    //删除第一个节点
    public void removeFirst() throws IllegalArgumentException{
//        if(head == null){
//            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));
//        }
//        head = head.next;
        remove(0);
    }

    //删除指定结点索引元素
    public Node remove(int index){
        Node node = findNode(index - 1);
        if(node == null){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));
        }
        Node removed = node.next;
        if(removed == null){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));
        }
        node.next = node.next.next;
        return removed;
    }

    //递归遍历
    private void recursion(Node curr){
        if(curr == null){
            return ;
        }
        System.out.println(curr.value);
        recursion(curr.next);
    }
    public void loop3(){
        recursion(head);
    }
}

三.双向链表的实现：

每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。 

 

首先创建节点类以及对应的构造方法：

static class Node{
    int value;//值
    Node next;//下一个结点
    Node prev;//上一个结点
    public Node(Node prev, int value , Node next) {
        this.prev = prev;
        this.value = value;
        this.next = next;
    }
}

 然后创建头尾哨兵，便于在两哨兵中间插入元素以及双向链表的操作：

private Node head;//头哨兵
private Node tail;//尾哨兵

随后创建这个双向链表的构造方法：

//头 <=> 尾
public DoubleLinkedListSentinel() {
    head = new Node(null, 0, null);
    tail = new Node(null, 0, null);
    head.next = tail;
    tail.prev = head;
}

最后实现对双向链表的操作： 

package LinkListStudy;

import java.util.Iterator;

public class DoubleLinkedListSentinel implements Iterable<Integer>{

    static class Node{
        int value;//值
        Node next;//下一个结点
        Node prev;//上一个结点
        public Node(Node prev, int value , Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    //哨兵
    private Node head;//头哨兵
    private Node tail;//尾哨兵

    //头 <=> 尾
    public DoubleLinkedListSentinel() {
        head = new Node(null, 0, null);
        tail = new Node(null, 0, null);
        head.next = tail;
        tail.prev = head;
    }

    //根据索引位置找到结点
    private Node findNode(int index){
        int i = -1;
        //当p = tail时停止循环
        for(Node p = head; p != tail; p = p.next){
            if(i == index){
                return p;
            }
        }
        return null;
    }

    //在指定位置插入结点
    public void insert(int index , int value) throws IllegalArgumentException{
        Node prev = findNode(index - 1);
        if(prev == null){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));
        }
        Node next = prev.next;
        Node newNode = new Node(prev, value, next);
        prev.next = newNode;
        next.prev = newNode;
    }

    //删除指定位置的结点
    public void remove(int index) throws IllegalArgumentException{
        Node prev = findNode(index - 1);
        if(prev == null){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));
        }
        Node remove = prev.next;
        if(remove == tail){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index));
        }
        Node next = remove.next;
        //断开联系
        prev.next = next;
        next.prev = prev;
    }

    //在尾部结点前添加结点
    public void addLast(int index , int value) throws IllegalArgumentException{
        Node last = tail.prev;
        Node newNode = new Node(last, value, tail);
        last.next = newNode;
        tail.prev = newNode;
    }

    //删除最后一个结点
    public void removeLast() throws IllegalArgumentException{
        //没有结点的情况
        if(tail.prev == head){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));
        }
        Node remove = tail.prev;
        Node prev = remove.prev;
        prev.next = null;
        tail.prev = prev;
    }

    //迭代器
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

}

四.双向循环链表的实现：

链表的最后一个节点指向第一个节点，形成一个闭环。

 

 首先创造哨兵结点以及其构造函数：

    private static class Node{
        Node prev;
        int value;
        Node next;
        public Node(Node prev, int value , Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    //哨兵节点
    private Node sentinel = new Node(null, -1, null);
    //哨兵节点构造函数
    public DoubleLinkedListCirtleSentinel(){
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }

随后实现对双向循环链表的操作： 

package LinkListStudy;

import java.util.Iterator;

public class DoubleLinkedListCirtleSentinel implements Iterable<Integer>{


    private static class Node{
        Node prev;
        int value;
        Node next;
        public Node(Node prev, int value , Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    //哨兵节点
    private Node sentinel = new Node(null, -1, null);
    //哨兵节点构造函数
    public DoubleLinkedListCirtleSentinel(){
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }

    //添加节点到第一个   a <=> newNode <=> a(b)
    public void addFirst(int value){
        Node a = sentinel;//哨兵
        Node b = sentinel.next;
        Node newNode = new Node(a, value, b);
        a.next = newNode;
        b.prev = newNode;
    }

    //添加节点到最后一个
    public void addLast(int value){
        Node b = sentinel;
        Node a = sentinel.prev;
        Node newNode = new Node(a, value, b);
        a.next = newNode;
        b.prev = newNode;
    }

    //删除第一个
    public void removeFirst(){
        Node removed = sentinel.next;
        if(removed == sentinel){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    //删除最后一个
    public void removeLast() throws IllegalArgumentException{
        Node removed = sentinel.prev;
        if(removed == sentinel){
            throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));
        }
        Node a = removed.next;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    //根据目标值删除
    public void removeByValue(int value){
        Node removed = findByValue(value);
        if(removed == null){
            return ;//不用删
        }
        Node a = removed.prev;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    //寻找目标值索引位置
    public Node findByValue(int value){
        Node p = sentinel.next;
        while(p != sentinel){
            if(p.value == value){
                return p;
            }
            p = p.next;
        }
        return null;
    }

    //迭代器遍历
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }
    
    //递归函数
    private void recursion(Node curr){//某个节点要进行的操作
        if(curr == sentinel){
            return ;
        }
        System.out.println(curr.value);
        recursion(curr.next);
    }

}

好了，看到这里感谢观看，记得三连支持，后序继续更新数据结构与算法相关知识！！！


http://www.kler.cn/a/328230.html

相关文章：

  • 2024年云南省职业院校技能大赛-云计算应用
  • ECMAScript标准
  • 【Android 14源码分析】Activity启动流程-1
  • 15分钟学 Python 第31天 ：Web Scraping
  • java通过redis完成幂等性操作
  • Invalid row number (65536) outside allowable range (0..65535)
  • thinkphp6开发的通用网站系统源码
  • UI设计师面试整理-问题应对策略
  • Python从入门到高手4.1节-掌握条件控制语句
  • Rockchip RK3588 Android SDK编译方法
  • JWT（JSON Web Token）的介绍
  • 物理学基础精解【41】
  • 上位机图像处理和嵌入式模块部署（软硬结合才是嵌入式的精髓）
  • Elasticsearch基础_2.数据类型
  • python网站创建001：内容概览
  • 机器学习常用的评价指标原理和代码
  • 支持分页的环形队列
  • SqlSugar使用
  • JMeter 性能测试基本过程及示例
  • Spring Web MVC课后作业