数据结构奇妙旅程之顺序表和链表

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页:xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏:xiaoxie的JAVA系列专栏——CSDN博客●'ᴗ'σσணღ*
我的目标:"团团等我💪( ◡̀_◡́ ҂)" 

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​+关注(互三必回)!

目录

​编辑一.顺序表

1.底层实现

2.构造方法

3.常用方法

4.Arrays的遍历方法

​编辑5.实战演示

一.顺序表

1.底层实现

首先我们要清楚,数据结构是一门逻辑十分清晰的学科,所以我们需要清楚的认识到每个结构的底层是什么,这样才能更好的掌握这个结构。

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成 数据的增删查改。

2.构造方法

在集合框架中, ArrayList 是一个普通的类,实现了 List接口,并且ArrayList是一个泛型类
而ArrayList的构造方法如下所示
public class Text {
    public static void main(String[] args) {
         //无参
        List<Integer> list = new ArrayList<>();
        //指定顺序表初始容量
        List<Integer> list1 = new ArrayList<>(20);
        list1.add(1);
        list1.add(11);
        //ArrayList(Collection<? extends E> c) 利用其他 Collection 构建 ArrayList
        List<Integer> list2 = new ArrayList<>(list1);
        
    }
}

3.常用方法

ArrayList是一个普通的类,实现了List接口,所以它实现了许多接口内的方法,博主现在为大家列举出一些常用的方法

List<Integer> list = new ArrayList<>();
        //尾插入元素
        list.add(1);
        list.add(12);
        list.add(11);
        //指定位置插入参数为 位置 和 元素
        list.add(2,3);
        //顺序表长度
        list.size();
        //删除指定位置元素
        list.remove(2);
        //是否包含某个元素
        list.contains(4);
        //截取部分 list
        list.subList(0,1);
        //获取下标 index 位置元素
        list.get(2);
        //将下标 index 位置元素设置为 element
        list.set(3,9);
        //返回第一个 o 所在下标
        list.indexOf(8);
        //返回最后一个 o 的下标
        list.lastIndexOf(8);

4.Arrays的遍历方法

1.直接输出

 List<Integer> list = new ArrayList<>();
        //尾插入元素
        list.add(1);
        list.add(12);
        list.add(11);
        System.out.println(list);

2.for循环和for-each

List<Integer> list = new ArrayList<>();
        //尾插入元素
        list.add(1);
        list.add(12);
        list.add(11);
        System.out.println("for循环遍历");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("for-each循环遍历");
        for (Integer x:list) {
            System.out.print(x+" ");
        }

3.使用迭代器

List<Integer> list = new ArrayList<>();
        //尾插入元素
        list.add(1);
        list.add(12);
        list.add(11);
        System.out.println("迭代器正序输出");
        Iterator<Integer>it = list.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
        System.out.println("迭代器逆序输出");
        ListIterator <Integer> it1 = list.listIterator(list.size());
        while (it1.hasPrevious()) {
            System.out.print(it1.previous()+" ");
        }
    }

5.实战演示

杨辉三角 力扣的118题,难度不大,感兴趣的朋友可以去尝试一下

解答代码如下

/*
        1
       1 1 
      1 2 1
     1 3 3 1
    1 4 6 4 1 
 由图可知每一行的第一个为1,最后一个也为一中间部分等于上一行的前一个加上上一行同一列的
 一个,并且最后一个也为一。
*/
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        list.add(1);//第一行
        ans.add(list);
        for(int i = 1;i < numRows;i++) {
            List<Integer> temp = new ArrayList<>();
            temp.add(1);//每一行的第一个都为一
             List<Integer> row =ans.get(i-1);//上一行
            for(int j = 1; j <i;j++) {
                int x = row.get(j)+row.get(j-1);//中间部分为上一行的前一个加上上一行同一列的一个
                temp.add(x);
            }
            temp.add(1);//一行的最后一个元素也为1
            ans.add(temp);
        }
        return ans;
    }
}

以上是博主解答这题的思路和代码,时间复杂度为O(n^2)如果你有更好的方法或者是不懂的地方都可以私聊博主,大家一起交流进步

二.链表

1.底层实现

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

当然链表的结构不仅仅是这一种其他还有1. 单向或者双向  2. 带头或者不带头  3. 循环或者非循环

虽然有这么多的链表的结构,但是我们重点掌握两种 :
无头单向非循环链表 结构简单 ,一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ,如
哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。
无头双向链表 :在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。

2.无头单向非循环链表

无头单向非循环链表是一种数据结构,其特点是没有头节点、只有一个指向第一个节点的指针,而且最后一个节点的指针为空(NULL),形成一个单向链表的尾部。这意味着如果需要查找第一个节点,必须从指向第一个节点的指针开始遍历链表。此外,非循环链表是一个单向链表,从第一个节点开始一直到最后一个节点,而最后一个节点指向空(NULL),这样就可以避免链表中的死循环问题。

3.无头双向非循环链表

无头双向非循环链表是一种数据结构,它由多个节点组成,每个节点有两个指针,一个指向前一个节点,一个指向后一个节点。和单向链表不同的是,双向链表可以向前和向后遍历,而且插入和删除节点的操作比较方便。

无头表示链表没有头节点,也就是第一个节点就是链表的起始节点。非循环表示链表没有环,也就是最后一个节点的指针指向 NULL。

在无头双向非循环链表中,我们可以从任意一个节点开始遍历,也可以逆序遍历整个链表。双向链表比单向链表多了一个指针,所以它在一些场景下比单向链表更加方便,比如需要频繁地插入和删除节点时。但是,它也需要更多的内存空间来存储指针。

4.顺序表和链表之间的区别

    顺序表和链表是两种数据结构,它们的主要区别在于存储方式和操作效率不同:

  1. 存储方式不同:顺序表使用一组连续的存储单元存储数据,而链表则使用指针将一组零散的存储单元串联起来。

  2. 随机访问效率不同:顺序表通过下标可以直接访问任意位置的元素,时间复杂度为O(1),但插入和删除操作需要移动数据,时间复杂度为O(n)。而链表不能通过下标直接访问元素,插入和删除操作只需要修改指针,时间复杂度为O(1),但是随机访问需要遍历整个链表,时间复杂度为O(n)。

  3. 空间利用率不同:顺序表预先分配存储空间大小固定,当存储空间不够时需要重新分配内存,可能浪费内存。而链表通过动态分配内存,只在需要时才分配所需的存储空间,空间利用率较高。

总之,应根据实际需求选择合适的数据结构,如果需要频繁随机访问,可以选择顺序表;如果需要频繁插入和删除,可以选择链表。

5.链表面试题

1.给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL 链接

public class Solution {
    // 定义一个方法detectCycle,输入参数为链表头节点head,返回值类型为ListNode(链表节点)
    public ListNode detectCycle(ListNode head) {
        // 如果链表为空或只有一个元素,则没有环,直接返回null
        if(head == null || head.next == null) {
            return null;
        }
        // 初始化两个指针fast和slow,都指向链表头节点
        ListNode fast = head;
        ListNode slow = head;
        
        // 使用快慢指针进行遍历
        while(fast != null && fast.next != null) {
            // 慢指针每次前进一步
            slow = slow.next;
            // 快指针每次前进两步
            fast = fast.next.next;

            // 如果快慢指针相遇,则说明存在环
            if(slow == fast) {
                break;
            }
        }

        // 如果快指针遍历到链表末尾,说明不存在环,返回null
        if(fast == null || fast.next == null) {
            return null;
        }

        // 重新设置快指针fast到链表头节点,慢指针slow保持在相遇点
        fast = head;

        // 当快慢指针再次相遇时,相遇点即为环的起点
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // 返回环的起点
        return fast;
    }
}

2.链表的回文结构链接

public class PalindromeList {
    // 定义一个方法chkPalindrome,输入参数为链表头节点head,返回值类型为布尔值(true表示是回文链表,false表示不是)
    public boolean chkPalindrome(ListNode head) {
        // 如果链表为空,则直接返回true(空链表是回文链表)
        if(head == null ) {
            return true;
        }
        
        // 使用快慢指针找到链表的中间结点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针每次前进一步
            slow = slow.next;      // 慢指针每次前进一步
        }

        // 翻转链表后半部分
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curnext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curnext;
        }

        // 判断翻转后的链表与原链表前半部分是否相等
        while(head != slow) {
            if(head.val != slow.val) { // 如果两个节点的值不相等,则说明不是回文链表
                return false;
            }if(head.next != slow) {   // 奇数情况下,已经比较完所有节点,可以提前结束循环
                return true;
            }
            head = head.next;          // 头节点向后移动一位
            slow = slow.next;          // 反转后的尾节点向前移动一位
        }
        
        // 遍历结束后没有发现不相等的节点,说明是回文链表
        return true;
    }
}

3.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。链接


public class Partition {
    // 定义一个方法partition,输入参数为链表头节点head和整数x,返回值类型为ListNode(链表节点)
    public ListNode partition(ListNode head, int x) {
        // 如果链表为空,则直接返回null
        if(head == null) {
            return null;
        }
        
        // 初始化两个指针de和dx,用于记录小于x的元素链表的尾节点和当前节点
        ListNode de = null;
        ListNode dx = null;
        // 初始化两个指针pe和px,用于记录大于等于x的元素链表的尾节点和当前节点
        ListNode pe = null;
        ListNode px = null;
        
        // 初始化一个指针cur,指向链表的头节点
        ListNode cur = head;
        
        // 遍历链表中的每个节点
        while(cur != null) {
            // 如果当前节点的值小于x
            if(cur.val < x) {
                // 如果小于x的元素链表尚未创建,则将当前节点设置为头节点和尾节点
                if(de == null) {
                    de = cur;
                    dx = cur;
                }else { // 否则将当前节点添加到小于x的元素链表的末尾
                    dx.next = cur;
                    dx = dx.next;
                }
            }else { // 如果当前节点的值大于等于x
                // 如果大于等于x的元素链表尚未创建,则将当前节点设置为头节点和尾节点
                if(pe == null) {
                    pe = cur;
                    px = cur;
                }else { // 否则将当前节点添加到大于等于x的元素链表的末尾
                    px.next = cur;
                    px = px.next;
                }
            }
            
            // 指针cur向后移动一位
            cur = cur.next;
        }
        
        // 如果不存在小于x的元素,则直接返回大于等于x的元素链表
        if(dx == null) {
            return pe;
        }
        
        // 将大于等于x的元素链表接到小于x的元素链表的末尾
        dx.next = pe;
        
        // 如果存在大于等于x的元素,则将其尾节点的next指针置为null
        if(pe != null) {
            px.next = null;
        }
        
        // 返回小于x的元素链表的头节点
        return de;
    }
}

三.结语

数据结构一门逻辑十分严谨的一门学科,而顺序表和链表都是十分基础的结构,也是后续学习的基础,所以应该要多花时间去搞清楚它的底层,好了本文到这里就结束了,感谢您的阅读,祝您一天愉快

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/213664.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数据库-PostgreSQL学习笔记

目录 PostgreSQL介绍与安装docker安装腾讯云免费领用1个月 数据库操作连接数据库实例创建数据库查看数据库列表使用数据库删除数据库修改数据库属性 表操作字段类型整数浮点数日期与时间类型字符串类型 DDLCREATEDROPALTER DMLINSERTUPDATEDELETE 查询查询所有数据查询部分列指…

HttpRunner自动化测试之响应中文乱码处理

响应中文乱码&#xff1a; 当调用接口&#xff0c;响应正文返回的中文是乱码时&#xff0c;一般是响应正文的编码格式不为 utf-8 导致&#xff0c;此时需要根据实际的编码格式处理 示例&#xff1a; 图1中 extract 提取title标题&#xff0c;output 输出 title 变量值&#x…

Reactor实战,创建一个简单的单线程Reactor(理解了就相当于理解了多线程的Reactor)

单线程Reactor package org.example.utils.echo.single;import java.io.IOException; import java.net.InetSocketAddress; import java.nio.channels.*; import java.util.Iterator; import java.util.Set;public class EchoServerReactor implements Runnable{Selector sele…

10 分钟解释 StyleGAN

一、说明 G在过去的几年里&#xff0c;生成对抗网络一直是生成内容的首选机器学习技术。看似神奇地将随机输入转换为高度详细的输出&#xff0c;它们已在生成图像、生成音乐甚至生成药物方面找到了应用。 StyleGAN是一种真正推动 GAN 最先进技术向前发展的 GAN 类型。当Karras …

rust入门(rust教程、rust安装方法)

文章目录 Rust开发入门Rust的特性Rust的应用场景Rust安装——环境配置1. 安装rustup具体执行步骤 2. 验证安装 Rust的卸载基本语法变量与数据类型控制流函数 Rust的所有权系统错误处理实战&#xff1a;构建一个小项目创建新项目编写代码运行项目安装相关链接器运行 删除项目 Ru…

第十五届蓝桥杯模拟赛(第二期)

第一题 计算 答案&#xff1a;108 std::cout<<36*30/10; 第二题 快速幂 答案&#xff1a;608 #include<bits/stdc.h> const int mod1e3; #define int long long int qmi(int a,int b) {int res1;while(b){if(b&1) res(res*a)%mod;b>>1;aa*a%mod;}return…

【数据库】基于封锁的数据库调度器,以及等待锁处理的优先级策略

封锁调度器的体系结构 ​专栏内容&#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发&#xff0c;开发的步骤&#xff0c;以及开发过程中的涉及的原理&#xff0c;遇到的问题等&#xff0c;让大家能跟上并且可以一起开发&#xff0c;让每个需要的人成为参与者。 本专栏会…

Redis中分布式锁的使用

在分布式系统中&#xff0c;如果使用JVM中的同步锁在高并发的场景下仍然会产生线程安全问题。首先我们来查看在多个服务器时为什么会产生线程安全问题&#xff0c;有这样一个案例&#xff0c;有一件商品购买规则为一个用户只能购买一次&#xff0c;如果使用同步锁锁住用户id&am…

C# Spire操作Excel数据透视表

一、概述 数据透视表&#xff08;Pivot Table&#xff09;是一种交互式的表&#xff0c;可以进行某些计算&#xff0c;如求和与计数等&#xff0c;可动态地改变透视表版面布置&#xff0c;也可以重新安排行号、列标和页字段。当改变版面布置时&#xff0c;数据透视表也会按照新…

PMP-01

考纲 需要看的书籍 学习计划

奇技淫巧第9期

今天回顾一下 5~12 月所遇到的零碎知识点。 文章目录 歪门邪道优雅删除“学习资料”快速下载 vscode两种硬盘格式zotero在word中插入参考文献markdown 下划线查看 CPU Linux 命令postgres 无法通过 root 用户操作bash 初学者礼包gitwin 11 edge 浏览器0x80190001 报错 python …

Pycharm调用Conda虚拟环境

参考这个链接的评论区回答&#xff1a;Pycharm调用Conda虚拟环境 笑死&#xff0c;我之前也是这样的&#xff0c;不过好像也能用&#xff0c;搞不懂~

蓝桥杯每日一题2023.12.2

题目描述 蓝桥杯大赛历届真题 - C 语言 B 组 - 蓝桥云课 (lanqiao.cn) 题目分析 答案&#xff1a;3598180 由题目分析可以知道&#xff0c;给小明发的牌一共有13种类型&#xff0c;每种类型的牌一共有四张。对于每种牌&#xff0c;我们都有5种选择&#xff0c;不拿、拿一张、…

WebGL笔记:矩阵缩放的数学原理和实现

矩阵缩放的数学原理 和平移一样&#xff0c;以同样的原理&#xff0c;也可以理解缩放矩阵让向量OA基于原点进行缩放 x方向上缩放&#xff1a;sxy方向上缩放&#xff1a;syz方向上缩放&#xff1a;sz 最终得到向量OB 矩阵缩放的应用 比如我要让顶点在x轴向缩放2&#xff0c;y轴…

ArrayList 与 顺序表 (附洗牌算法)!

曾经我也是一枚学霸&#xff0c;直到有一天想去学渣的世界看看&#xff0c;结果就找不到回去的路了。 目录 1. 线性表 2.顺序表 2.1 接口的实现 3. ArrayList简介 4. ArrayList使用 4.1 ArrayList的构造 4.2 ArrayList常见操作 4.3 ArrayList的遍历 4.4 ArrayList的扩…

分享66个焦点幻灯JS特效,总有一款适合您

分享66个焦点幻灯JS特效&#xff0c;总有一款适合您 66个焦点幻灯JS特效下载链接&#xff1a;https://pan.baidu.com/s/10bqe09IAZt_hbsZlXaxkxw?pwd6666 提取码&#xff1a;6666 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;…

万能的视频格式播放器

今天博主给大家带来一款“万能”的视频播放器——VLC Media Player&#xff0c;支持的文件格式非常多&#xff0c;大家快来一起看看吧&#xff01; VLC Media Player 是一款可播放大多数格式&#xff0c;而无需安装编解码器包的媒体播放器。可以播放 MPEG-1、MPEG-2、MPEG-4、D…

Tektronix泰克示波器

一、what’s the oscilloscope&#xff1f; 【ref】https://www.tek.com.cn/blog/what-is-an-oscilloscope 二、基础知识 1、带宽&#xff1a;100Mhz&#xff1b;采样率&#xff1a;2.5GS/s 1GS/s指的是采样率&#xff0c;前面大写的S是sample采样的意思 后面的s是秒 也就是示波…

粉丝提问:岗位与描述不一致,小公司感觉学不到东西,工作内容就是调试,想辞职

0、粉丝问题&#xff1a; 大哥&#xff0c;我毕业已经工作两个月了&#xff0c;在一家小公司&#xff0c;岗位和描述的不一致&#xff0c;感觉就像调试一样&#xff0c;写代码的机会很少也没人带&#xff0c; 我想转嵌入式&#xff0c;您有什么建议的方向吗&#xff0c;或者是…

MathType公式编辑器安装教程

一、下载 MathType7是一款可以帮助用户快速完成数学公式编辑的应用软件&#xff0c;这款软件适合在进行教育教学、科研机构、论文写作的时候使用。我们可以直接通过这款软件来获取到大量数学上使用到的函数、数学符号等内容&#xff0c;然后使用这些内容来完成公式编辑。 …
最新文章