Java数据结构与算法——单向链表

简介: Java数据结构与算法——单向链表

1.简介



·       误区

1.    认为学习数据结构和算法需要很扎实的数学和编程功底,学起来并不容易;

2.    数据结构和算法在平时开发过程中的应用并不多,而且都有现成的类库接口让我们调用,没必要花太多时间去研究。


·       疑问

1.    为什么数据结构和算法使用率这么低,这些大公司还必问呢?这是因为数据结构和算法真的很重要,而且他们的使用率并不低,所有的程序中都有数据结构和算法的身影,他们默默的为程序服务,只是你没重视他们罢了。


·       列举我们为什么要学好数据结构和算法原因

1.    提升代码性能,结省空间复杂度和时间复杂度;

2.    算法锻炼自己的逻辑思维;

3.    你会不自觉的考虑你写的代码处理的数据量级是多少,会考虑你的代码是否能处理大量数据的情况

4.    更好的理解应用软件和框架,很多知名软件和框架中都大量用了数据结构算法,比如mysql的索引用了b+树,redislist底层用了跳跃表,理解这些数据结构能更好的帮助我们理解使用这些软件。

5.    掌握了数据结构与算法,你看待问题的深度,解决问题的角度就会完全不一样。

6.    一流的程序员搞算法,二流的程序员搞架构,三流的程序员搞业务;


数据结构与算法的关系:

1.    程序 = 数据结构 + 算法

2.    数据结构是算法的基础。

3.    图书馆储藏书籍你肯定见过吧?为了方便查找,图书管理员一般会将书籍分门别类进行存储。按照一定规律编号,就是书籍这种数据的存储结构。那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法。

4.    数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。


线性结构与非线性结构:

·       线性结构:数组、队列、链表和栈。

1.    线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系。

2.    线性结构有两种不同的存储结构,即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。

3.    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素结点存放数据元素以及相邻元素的地址信息。

·       非线性结构:二维数组,多维数组,广义表,树,图。

2.单向链表


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

特点:

1.    链表是以结点形式存储的,是链式存储。

2.    每个结点包含data区域和next区域。

3.    如上图各个结点并不是连续存储的。

4.    链表分带头结点链表和没有带头结点链表,根据实际的需求来确定。

3.代码案例


我们首先需要一个实体类,它对应的便是单链表中每个节点的数据信息。

package com.szh.unidirectional;
/**
 *
 */
public class GoodsNode {
    public int id;
    public String name;
    public double price;
    public GoodsNode next;
    public GoodsNode(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }
    @Override
    public String toString() {
        return "GoodsNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

接下来,我们写一个具体对单链表进行CRUD的操作类。

package com.szh.unidirectional;
/**
 *
 */
public class DLLinkedList {
    private GoodsNode node = new GoodsNode(0, "", 0.0);
    //在单向链表末尾插入节点
    public void addLast(GoodsNode goodsNode) {
        GoodsNode temp = node; //辅助变量
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = goodsNode;
    }
    //在单向链表中间某个位置插入节点
    public void addOrder(GoodsNode goodsNode) {
        GoodsNode temp = node; //辅助变量
        boolean flag = false;  //标记变量
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id > goodsNode.id) {
                break;
            } else if (temp.next.id == goodsNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("已经存在了该商品,不能添加重复元素");
        } else {
            goodsNode.next = temp.next;
            temp.next = goodsNode;
        }
    }
    //修改单向链表的某个节点
    public void updateNode(GoodsNode goodsNode) {
        //如果链表为空
        if (node.next == null) {
            System.out.println("链表为空....");
            return;
        }
        GoodsNode temp = node.next; //辅助变量
        boolean flag = false;  //标记变量
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.id == goodsNode.id) { //找到了要修改的链表节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = goodsNode.name;
            temp.price = goodsNode.price;
        } else {
            System.out.println("在整个链表中未找到目标节点....");
        }
    }
    //删除单向链表的某个节点
    public void deleteNode(int id) {
        //如果链表为空
        if (node.next == null) {
            System.out.println("链表为空....");
            return;
        }
        GoodsNode temp = node; //辅助变量
        boolean flag = false;  //标记变量
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("未找到删除的结点....");
        }
    }
    //遍历单向链表,查看每个节点元素
    public void list() {
        //如果链表为空
        if (node.next == null) {
            System.out.println("链表为空....");
            return;
        }
        GoodsNode temp = node.next; //辅助变量
        int index = 0;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println("第 " + (++index) + " 个节点元素为:" + temp);
            temp = temp.next;
        }
        //System.out.println("此单向链表中共有 " + index + " 个节点元素。");
    }
    //统计单向链表中节点的个数
    public int getNodeNum() {
        //如果链表为空
        if (node.next == null) {
            System.out.println("链表为空....");
            return 0;
        }
        GoodsNode temp = node.next;
        int num = 0;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        return num;
    }
}

最后是我们的主方法类,我们需要对上面写好的代码功能进行测试。

package com.szh.unidirectional;
/**
 * 单向链表相关操作
 */
public class LinkedTest {
    public static void main(String[] args) {
        DLLinkedList dlLinkedList = new DLLinkedList();
        GoodsNode goodsNode1 = new GoodsNode(1, "西游记", 55.55);
        GoodsNode goodsNode2 = new GoodsNode(2, "水浒传", 66.66);
        GoodsNode goodsNode3 = new GoodsNode(3, "红楼梦", 88.88);
        GoodsNode goodsNode4 = new GoodsNode(4, "三国演义", 99.99);
        System.out.println("单向链表的插入操作:");
        dlLinkedList.addLast(goodsNode1);
        dlLinkedList.addLast(goodsNode3);
        dlLinkedList.addOrder(goodsNode4);
        dlLinkedList.addOrder(goodsNode2);
        dlLinkedList.list();
        System.out.println("此单向链表中共有 " + dlLinkedList.getNodeNum() + " 个节点元素。");
        System.out.println();
        System.out.println("单向链表的修改操作:");
        dlLinkedList.updateNode(new GoodsNode(3, "Java编程思想", 11.11));
        dlLinkedList.list();
        System.out.println("此单向链表中共有 " + dlLinkedList.getNodeNum() + " 个节点元素。");
        System.out.println();
        System.out.println("单向链表的删除操作:");
        dlLinkedList.deleteNode(2);
        dlLinkedList.list();
        System.out.println("此单向链表中共有 " + dlLinkedList.getNodeNum() + " 个节点元素。");
    }
}

4.单向链表的CRUD图解


在单向链表的末尾插入新的节点。

 

在单向链表的中间某个位置插入新的节点。


单向链表的修改操作。(比较简单)

单向链表的删除操作。

相关文章
|
24天前
|
监控 算法 网络协议
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
66 15
|
3月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
112 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
16天前
|
运维 监控 算法
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
58 32
|
6天前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
3天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
36 6
|
3天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
27 5
|
14天前
|
存储 监控 算法
探秘局域网桌面监控:深入剖析 Java 语言核心算法
在数字化办公时代,局域网桌面监控如同企业的“智慧鹰眼”,确保工作效率与数据安全。本文以Java为载体,揭示哈希表在监控中的关键应用。通过高效的数据结构和算法,哈希表能快速索引设备连接信息,大幅提升监控的时效性和响应速度。代码示例展示了如何用Java实现设备网络连接监控,结合未来技术如AI、大数据,展望更智能的监控体系,助力企业在数字化浪潮中稳健前行。
|
30天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
37 6
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法

热门文章

最新文章

  • 1
    局域网屏幕监控系统中的Python数据结构与算法实现
    123
  • 2
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    41
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    36
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    42
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    43
  • 6
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    33
  • 7
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    52
  • 8
    2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    33
  • 9
    2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    39
  • 10
    2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    35