Java数据结构之链表相关知识总结

2023年5月17日上午1:33 • 数据结构

Java数据结构之链表相关知识总结

链表是一种非常常用的数据结构，它有许多实际应用，比如链表可以用来实现栈、队列、散列表和图等数据结构。在Java语言中，链表的实现方式主要有单向链表、双向链表和循环链表。

单向链表

单向链表是一种链表结构，每个节点包含两个元素：节点值和一个指向下一个节点的引用。链表的头结点（第一个节点）不包含值，仅包含指向链表中第一个实际节点的引用。

单向链表的实现示例如下：

public class SingleLinkedList {
    private Node head; // 头结点，不包含值
    private int size; // 链表长度

    // 内部类Node，封装链表节点的值和next引用
    private class Node {
        Object value; // 节点的值
        Node next; // 指向下一个节点的引用

        public Node(Object value) {
            this.value = value;
        }
    }

    // 在头部插入节点
    public void addFirst(Object value) {
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode;
        size++;
    }

    // 在尾部插入节点
    public void addLast(Object value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 在指定位置插入节点
    public void add(int index, Object value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            addFirst(value);
        } else if (index == size) {
            addLast(value);
        } else {
            Node newNode = new Node(value);
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
            size++;
        }
    }

    // 删除头节点，返回删除的节点值
    public Object removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        Object value = head.value;
        head = head.next;
        size--;
        return value;
    }

    // 删除尾节点，返回删除的节点值
    public Object removeLast() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        if (head.next == null) {
            Object value = head.value;
            head = null;
            size--;
            return value;
        }
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        Object value = current.next.value;
        current.next = null;
        size--;
        return value;
    }

    // 删除指定位置的节点，返回删除的节点值
    public Object remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            return removeFirst();
        } else if (index == size - 1) {
            return removeLast();
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            Object value = current.next.value;
            current.next = current.next.next;
            size--;
            return value;
        }
    }

    // 获取链表长度
    public int size() {
        return size;
    }

    // 获取指定位置的节点值
    public Object get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.value;
    }
}

双向链表

双向链表是一种链表结构，每个节点包含三个元素：前一个节点的引用、节点值和下一个节点的引用。链表的头结点（第一个节点）和尾节点（最后一个节点）都存在。

双向链表的实现示例如下：

public class DoubleLinkedList {
    private Node head; // 头结点，不包含值
    private Node tail; // 尾节点，不包含值
    private int size; // 链表长度

    // 内部类Node，封装链表节点的值、prev引用和next引用
    private class Node {
        Object value; // 节点的值
        Node prev; // 指向前一个节点的引用
        Node next; // 指向下一个节点的引用

        public Node(Object value) {
            this.value = value;
        }
    }

    // 在头部插入节点
    public void addFirst(Object value) {
        Node newNode = new Node(value);
        if (head != null) {
            head.prev = newNode;
        } else {
            tail = newNode;
        }
        newNode.next = head;
        head = newNode;
        size++;
    }

    // 在尾部插入节点
    public void addLast(Object value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
        }
        tail = newNode;
        size++;
    }

    // 在指定位置插入节点
    public void add(int index, Object value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            addFirst(value);
        } else if (index == size) {
            addLast(value);
        } else {
            Node newNode = new Node(value);
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            newNode.prev = current;
            current.next.prev = newNode;
            current.next = newNode;
            size++;
        }
    }

    // 删除头节点，返回删除的节点值
    public Object removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        Object value = head.value;
        head = head.next;
        if (head != null) {
            head.prev = null;
        } else {
            tail = null;
        }
        size--;
        return value;
    }

    // 删除尾节点，返回删除的节点值
    public Object removeLast() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        Object value = tail.value;
        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        } else {
            head = null;
        }
        size--;
        return value;
    }

    // 删除指定位置的节点，返回删除的节点值
    public Object remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            return removeFirst();
        } else if (index == size - 1) {
            return removeLast();
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            Object value = current.next.value;
            current.next = current.next.next;
            current.next.prev = current;
            size--;
            return value;
        }
    }

    // 获取链表长度
    public int size() {
        return size;
    }

    // 获取指定位置的节点值
    public Object get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.value;
    }
}

示例说明

示例一

SingleLinkedList list = new SingleLinkedList();
list.addFirst(1); // 在头部插入节点
list.addLast(3); // 在尾部插入节点
list.add(1, 2); // 在指定位置插入节点
System.out.println(list.size()); // 获取链表长度
System.out.println(list.get(0)); // 获取第一个节点的值
System.out.println(list.get(1)); // 获取第二个节点的值
System.out.println(list.get(2)); // 获取第三个节点的值

以上代码输出的结果是：

示例二

DoubleLinkedList list = new DoubleLinkedList();
list.addFirst(1); // 在头部插入节点
list.addLast(3); // 在尾部插入节点
list.add(1, 2); // 在指定位置插入节点
System.out.println(list.size()); // 获取链表长度
System.out.println(list.get(0)); // 获取第一个节点的值
System.out.println(list.get(1)); // 获取第二个节点的值
System.out.println(list.get(2)); // 获取第三个节点的值

以上代码输出的结果是：

以上就是Java数据结构之链表相关知识的总结，希望对大家有所帮助！

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java数据结构之链表相关知识总结 - Python技术站

数据结构

0 0 打赏

微信扫一扫

支付宝扫一扫

C++数据结构之二叉搜索树的实现详解

上一篇 2023年5月17日

C#数据结构与算法揭秘一

下一篇 2023年5月17日

java编程队列数据结构代码示例

下面是“Java编程队列数据结构代码示例”的完整攻略。什么是队列队列是一种有序的数据结构，特点是先进先出（FIFO）。队列中不管是插入操作还是删除操作，都是在队列的两端进行的，插入操作在队列的尾部进行，删除操作在队列的头部进行。队列的一个重要用途是在计算机的操作系统中，实现进程和所有需要等待资源的实体之间的交互。队列的实现队列数据结构可以采用数组或链…

数据结构 2023年5月17日
000
Java实题演练二叉搜索树与双向链表分析

Java实题演练二叉搜索树与双向链表分析题目描述给定一个二叉搜索树，将它转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。思路分析对于一颗二叉搜索树，有以下性质：若左子树不为空，则左子树上所有结点的值均小于它的根结点的值；若右子树不为空，则右子树上所有结点的值均大于它的根结点的值；左右子树也为二叉搜索树。我们考虑…

数据结构 2023年5月17日
000
PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例

下面我来为大家详细讲解一下“PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例”的攻略。一、SplQueue 首先，我们先来介绍一下SplQueue。SplQueue是一个双向队列，它基于一个双向链表实现，可以在队列的两端插入和删除元素，既可以按照先进先出的顺序来操作队列，也可以反过来按照先进后出的顺序来操作…

数据结构 2023年5月17日
000
php数据结构与算法(PHP描述) 查找与二分法查找

以下是详细讲解“php数据结构与算法(PHP描述) 查找与二分法查找”的完整攻略。 1. 数据结构与算法简介数据结构是计算机中存储和组织数据的方式。它涉及到数据的表示、处理和存储方式等。算法则是完成特定任务的步骤集合。算法设计可以优化计算机程序的效率和速度。 PHP是一种非常流行的服务器端脚本语言，数据结构和算法对web开发者来说非常重要。因此，我们需要…

数据结构 2023年5月17日
000
Java数据结构的十大排序

Java数据结构的十大排序攻略简介在计算机科学中，排序算法是一种将一串数据按照特定顺序进行排列的方法，其中常见的排序算法有很多种，不同的算法适用于不同的数据类型和数据规模。Java是一种常见的编程语言，也提供了很多实现排序算法的类和方法。本文将介绍Java数据结构的十大排序算法，分别为：插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、堆排序…

数据结构 2023年5月17日
000
数据结构与算法之手撕排序算法

数据结构与算法之手撕排序算法本篇攻略介绍如何手撕常见的排序算法。冒泡排序冒泡排序是一种通过不断交换相邻元素来排序的方法。它的时间复杂度为$O(n^2)$。 def bubble_sort(nums): for i in range(len(nums)): for j in range(len(nums)-i-1): if nums[j] > nu…

数据结构 2023年5月17日
000
MySQL数据库体系架构详情

MySQL数据库体系架构是MySQL数据库自身的发展和演变过程中逐渐形成的一个庞大的体系。这个体系由多个组件构成，包括连接器、查询缓存、解析器、优化器、执行器、存储引擎等多个部分，其中存储引擎是其中最具有代表性的组件之一。在这篇攻略中，我们将详细讲解MySQL数据库体系架构的各个部分，介绍它们各自的功能和作用。连接器 MySQL的连接器负责与客户端建立连接…

数据结构 2023年5月17日
000
C语言创建和操作单链表数据结构的实例教程

C语言创建和操作单链表数据结构的实例教程什么是单链表单链表是一种常见的动态数据结构，它由一个个节点组成，每个节点包含范围内的数据和指向下一个节点的指针。单链表通常用于需要频繁插入删除节点的情况。单链表的创建和操作步骤创建单链表定义一个链表节点结构体，结构体中包含要存储的数据和指向下一个节点的指针。定义一个指向链表头部的指针，如果链表为空，则指针为…

数据结构 2023年5月17日
000

Java数据结构之链表相关知识总结

Java数据结构之链表相关知识总结

单向链表

双向链表

示例说明

示例一

示例二

相关文章