Java 数据结构与算法系列精讲之单向链表

2024-04-02 19:04:59 826人浏览独家记忆

Python 官方文档：入门教程 => 点击学习

摘要

目录概述链表单向链表单向链表实现node 类add 方法remove 方法get 方法set 方法contain 方法main完整代码概述从今天开始, 小白我将带大家开启 Jave

概述

从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.

链表

链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大.

链表包括三类:

单向链表
双向链表
循环链表

单向链表

单向链表 (Single Linked List) 是链表中最简单的一种形式. 单向链表每个节点包含两个部分, 第一部分是信息, 第二部分是下一个节点. (元素 + 指针)

单向链表实现

Node 类


// Node类
private class Node {


    public E e;  // 元素
    private SingleLinkedList.Node next;  // 下一个节点

    // 构造
    public Node(E e) {
        this.e = e;
        this.next = null;
    }

    @Override
    public String toString() {
        return e.toString();
    }
}

add 方法


// 添加数据
public void add(int index, E e) {

    // 检查索引是否越界
    if (index < 0 || index > size) {
        throw new RuntimeException("Invalid Index");
    }

    // 获取index前一个节点
    SingleLinkedList.Node prev = dummyHead;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }

    // 添加数据
    SingleLinkedList.Node node = new SingleLinkedList.Node(e);
    node.next = prev.next;
    prev.next = node;
    size++;
}

remove 方法


// 删除数据
public void remove(int index) {

    // 检查索引是否越界
    if (index < 0 || index > size) {
        throw new RuntimeException("Invalid Index");
    }

    // 获取index前一个节点
    Node prev = dummyHead;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }

    // 删除数据
    Node retNode = prev.next;
    prev.next = retNode.next;

    size --;
}

get 方法


// 通过索引获取链表数数据
public E get(int index) {

    // 检查索引是否越界
    if (index < 0 || index > size) {
        throw new RuntimeException("Invalid Index");
    }

    // 获取index前一个节点
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    
    return cur.e;
}

set 方法


// 通过索引设置链表数据
public E set(int index,E e) {

    // 检查索引是否越界
    if (index < 0 || index > size) {
        throw new RuntimeException("Invalid Index");
    }

    // 获取index前一个节点
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }

    // 设置新值
    cur.e = e;

   return cur.e;
}

contain 方法


// 链表是否包含元素
public boolean contains(E e) {
        Node cur = dummyHead.next;

        // 遍历所有节点
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
    return false;
}

main


// main
public static void main(String[] args) {

    // 创建单向链表
    SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

    // 添加数据
    for (int i = 0; i < 8; i++) {
        singleLinkedList.addFirst(i);
        System.out.println(singleLinkedList);
    }

    // 是否包含元素
    System.out.println(singleLinkedList.contains(0));
    System.out.println(singleLinkedList.contains(10));

    // set
    singleLinkedList.set(0, 9);
    singleLinkedList.set(1, 7);
    System.out.println(singleLinkedList);

    // 删除数据
    for (int i = 0; i < 8; i++) {
        singleLinkedList.remove(0);
        System.out.println(singleLinkedList);
    }
}

输出结果:

0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
6->5->4->3->2->1->0->NULL
7->6->5->4->3->2->1->0->NULL
true
false
9->7->5->4->3->2->1->0->NULL
7->5->4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL

完整代码


public class SingleLinkedList<E> {


    private Node dummyHead;  // 头指针
    private int size;  // 链表大小

    // Node类
    private class Node {


        public E e;  // 元素
        private Node next;  // 下一个节点

        // 构造
        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    // 构造
    public SingleLinkedList() {
        dummyHead = new Node(null);
        size = 0;
    }

    // 表首添加元素
    public void addFirst(E e) {
        add(0, e);
    }

    // 表尾添加元素
    public void addLast(E e){
        add(size, e);
    }

    // 添加数据
    public void add(int index, E e) {

        // 检查索引是否越界
        if (index < 0 || index > size) {
            throw new RuntimeException("Invalid Index");
        }

        // 获取index前一个节点
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        // 添加数据
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    // 删除数据
    public void remove(int index) {

        // 检查索引是否越界
        if (index < 0 || index > size) {
            throw new RuntimeException("Invalid Index");
        }

        // 获取index前一个节点
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        // 删除数据
        Node retNode = prev.next;
        prev.next = retNode.next;

        size --;
    }


    // 通过索引获取链表数数据
    public E get(int index) {

        // 检查索引是否越界
        if (index < 0 || index > size) {
            throw new RuntimeException("Invalid Index");
        }

        // 获取index前一个节点
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.e;
    }

    // 通过索引设置链表数据
    public E set(int index,E e) {

        // 检查索引是否越界
        if (index < 0 || index > size) {
            throw new RuntimeException("Invalid Index");
        }

        // 获取index前一个节点
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        // 设置新值
        cur.e = e;

        return cur.e;
    }

    // 链表是否包含元素
    public boolean contains(E e) {
        Node cur = dummyHead.next;

        // 遍历所有节点
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 获取链表大小
    public int getSize() {
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.next;
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.next;
        }
        builder.append("NULL");
        return builder.toString();
    }

    // main
    public static void main(String[] args) {

        // 创建单向链表
        SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

        // 添加数据
        for (int i = 0; i < 8; i++) {
            singleLinkedList.addFirst(i);
            System.out.println(singleLinkedList);
        }

        // 是否包含元素
        System.out.println(singleLinkedList.contains(0));
        System.out.println(singleLinkedList.contains(10));

        // set
        singleLinkedList.set(0, 9);
        singleLinkedList.set(1, 7);
        System.out.println(singleLinkedList);

        // 删除数据
        for (int i = 0; i < 8; i++) {
            singleLinkedList.remove(0);
            System.out.println(singleLinkedList);
        }
    }
}

到此这篇关于Java 数据结构与算法系列精讲之单向链表的文章就介绍到这了,更多相关Java 单向链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

您可能感兴趣的文档:

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: Java 数据结构与算法系列精讲之单向链表

本文链接: https://www.lsjlt.com/news/139666.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

Java 数据结构与算法系列精讲之单向链表

目录概述链表单向链表单向链表实现Node 类add 方法remove 方法get 方法set 方法contain 方法main完整代码概述从今天开始, 小白我将带大家开启 Jave...

99+

2024-04-02
Java数据结构与算法系列精讲之环形链表

目录概述链表环形链表环形链表实现Node 类insert 方法remove 方法main完整代码概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章....

99+

2024-04-02
Java 数据结构与算法系列精讲之队列

目录概述队列队列实现enqueue 方法dequeue 方法main完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 队列队列 (Q...

99+

2024-04-02
Java 数据结构与算法系列精讲之栈

目录概述栈栈实现push方法pop方法main完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈栈 (Stack) 是一种运算受限...

99+

2024-04-02
Java数据结构与算法系列精讲之KMP算法

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. KMP 算法 KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法...

99+

2024-04-02
Java 数据结构与算法系列精讲之数组

目录概述数组声明数组的两个方法创建数组的两个方法索引自定义数组泛型构造函数元素操作调用完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. ...

99+

2024-04-02
Java数据结构与算法系列精讲之排序算法

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的...

99+

2024-04-02
Java 数据结构与算法系列精讲之贪心算法

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状...

99+

2024-04-02
Java 数据结构与算法系列精讲之汉诺塔

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 汉诺塔汉诺塔 (Tower of Hanoi) 是一个源于印度的古老益智玩具. 汉诺塔由三...

99+

2024-04-02
Java数据结构与算法系列精讲之二叉堆

目录概述优先队列二叉堆二叉堆实现获取索引添加元素siftUp完整代码概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列优先队列 (P...

99+

2024-04-02
Java数据结构与算法系列精讲之红黑树

目录概述红黑树红黑树的实现Node 类添加元素左旋右旋完整代码概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 红黑树红黑树 (Red Bl...

99+

2024-04-02
Java数据结构与算法系列精讲之哈希算法实现

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 获取哈希值 hashCode()方法可以返回一个对象的哈希值. 需要注意的是, 我们需要对值...

99+

2024-04-02
Java数据结构与算法系列精讲之背包问题

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 动态规划动态规划 (Dynamic Programming) 的核心思想是把大问题划分为小...

99+

2024-04-02
Java数据结构与算法学习之双向链表

目录双向链表的储存结构示意图双向链表的初始化结构1.双向链表的结点2.双向链表的头结点3.总代码双向链表中的指定文件插入元素 1.插入的为第一个位置2.其他位置插入总代码双向链表的删...

99+

2024-04-02
Java数据结构与算法系列精讲之字符串暴力匹配

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一...

99+

2024-04-02
Java数据结构与算法之单链表深入理解

目录一、单链表(Linked List)简介二、单链表的各种操作1.单链表的创建和遍历2.单链表的按顺序插入节点以及节点的修改3.单链表节点的删除4.以上单链表操作的代码实现 (通...

99+

2024-04-02
java数据结构基础:单链表与双向链表

目录单链表：实现思路：代码实现：双向链表：实现思路：代码实现：总结单链表：每个数据是以节点的形式存在的每个节点分为数据域和指针域数据域中保存该节点的数据指针域中保存指向下一个...

99+

2024-04-02
C语言数据结构与算法之单链表

目录基本概念读取数据元素获取第i个结点的数据元素插入数据元素初始化链表打印链表顺序表查空顺序表的删除删除第i个结点及其数据元素情况1：当删除的是第一个元素情况2：除第一个结点外完...

99+

2024-04-02
Java数据结构之链表实现（单向、双向链表及链表反转）

前言之前学习的顺序表查询非常快，时间复杂度为O(1)，但是增删改效率非常低，因为每一次增删改都会元素的移动。可以使用另一种存储方式-链式存储结构。链表是一种物理存储单元上非连续、...

99+

2024-04-02
Java数据结构与算法系列精讲之时间复杂度与空间复杂度

目录概述算法的衡量标准时间复杂度最优时间复杂度平均时间复杂度最坏时间复杂度O(1)O(n)O(n^2)O(logN)空间复杂度O(1)O(n)概述从今天开始, 小白我将带大家开启 ...

99+

2024-04-02