数据结构：顺序表+链表

news/2024/9/13 20:43:25/ 标签: 数据结构, 链表, java, 顺序表

数据结构：顺序表+链表

一。顺序表：

首先在了解顺序表和链表之前，先了解一下线性表，**线性表（linear list）**是n个具有相同特征元素的有限序列 ，在逻辑上是线性结构，也就是一条连续的直线，但是在物理上不一定是连续的。常见的线性表：顺序表，链表，栈，队列…

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

下面将了解顺序表的底层实现逻辑：

接口：

java">public interface SeqList {public void add(int data);//新增元素，默认在数组最后进行新增public void add(int pos,int data);//新增元素，在pos这个位置加上data这个数据public boolean contain(int toFind);//查看toFind这个元素是否在数组中存在public int index(int toFind);//查看这个元素在数组中的下标public int get(int pos);//获取pos位置的元素public void set(int pos,int value);//给pos位置的值修改为valuepublic int remove(int toRemove);//删除第一次出现的的关键字keypublic int size();//获取顺序表的长度public void display();//打印顺序表
}

接口的实现：

java">import java.util.Arrays;public class Main implements SeqList{private int[] elem=new int[10];private int usedSize;@Overridepublic void add(int data) {if(isFull()){elem= Arrays.copyOf(elem,elem.length*2);}this.elem[usedSize]=data;usedSize++;}public boolean isFull(){if(usedSize==elem.length){return true;}return false;}@Overridepublic void add(int pos, int data) {if(pos<0 || pos>usedSize){System.out.println("输入不合法");//可以把这个写进一个方法中，然后写一个异常，如果pos不合法就抛出异常}if(isFull()){elem=Arrays.copyOf(elem,elem.length*2);}for(int i=usedSize-1;i >=pos;i--){//先把所有的元素向后移动一个单元，当i<pos的时候就结束elem[i+1]=elem[i];}elem[pos]=data;usedSize++;}@Overridepublic boolean contain(int toFind) {for(int i=0;i<usedSize;i++){if(elem[i]==toFind){return true;}}return false;}@Overridepublic int index(int toFind) {if(this.contain(toFind)){for(int i=0;i<usedSize;i++){if(elem[i] == toFind){return i;}}}return 0;}@Overridepublic int get(int pos) {if(pos<0||pos>usedSize-1){System.out.println("输入的元素不合法");}else {for (int i=0;i<usedSize;i++){if(pos==i){//System.out.println(elem[pos]);return elem[pos];}}}return 0;}@Overridepublic void set(int pos, int value) {if(pos<0||pos>usedSize){System.out.println("输入不合法");}elem[pos]=value;}@Overridepublic void remove(int toRemove) {int ret=this.index(toRemove);//获取删除元素的下标for(int i=ret;i<usedSize-1;i++){elem[i]=elem[i+1];}elem[usedSize-1]=0;usedSize--;}@Overridepublic int size() {int count=0;for(int i=0;i<elem.length;i++){count++;}return count;}@Overridepublic void display() {for(int i=0;i<usedSize;i++){System.out.println(elem[i]+" ");}}
}

二。ArrayList的使用

ArrayList是以泛型方式实现的，使用时必须先要将其实例化

1.ArrayList的构造：

java">List<Integer> list1=new ArrayList<>();//构造一个空的列表
List<Integer> list1=new ArrayList<>(10);//构造一个列表，其中含有10个元素

2.ArrayList的常见操作；

java">import java.util.ArrayList;public class Main {public static void main(String[] args) {ArrayList<Integer> list1=new ArrayList<>();list1.add(10);//加入元素list1.add(0,10)//在0下标的位置插入数字10list1.remove(1);//删除下标为1的值list1.get(2);//获取下标为2的值list1.set(1,3);//把下标为1的位置的值改为3list1.contain(12);//是否有12这个值在此线性表中list1.indexOf(10);//返回第一个值为10的下标list1.size();//获取整个顺序表的元素个数  }
}

注意：

当实例一个空的列表时，第一次add默认分配一个大小为10的内存（在实例化阶段不分配内存）

扩容是自动以1.5倍的形式扩容

3.顺序表的遍历

java">//法一：
for(int i=0;i<list.size();i++){System.out.println(list.get(i));
}
//法二：
System.out.println(list);

三。ArrayList的具体使用例子

杨辉三角的实现：

在这里插入图片描述

上述这个图片就是我们常说的杨辉三角，在高中的时候没少接触这个东西

这个杨辉三角主要的实现方式是通过二维顺序表实现的，下面将对用二维顺序表来实现杨辉三角的实现

java">import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Soulation {public static void main(String[] args) {Scanner sc=new Scanner(System.in);System.out.println("请输入");int input=sc.nextInt();List<List<Integer>> list=new ArrayList<>();//第一行的导入List<Integer> arr=new ArrayList<>();arr.add(1);list.add(arr);//从第二行开始，进行计算、for(int i=1;i<input;i++){List<Integer> curRow=new ArrayList<>();curRow.add(1);List<Integer> prevRow=list.get(i-1);for(int j=1;j<i;j++){int val=prevRow.get(j)+prevRow.get(j-1);}curRow.add(1);list.add(curRow);}}
}

四。链表：

在介绍链表之前，先说一下ArrayList的缺点；当在ArrayList任意位置进行删除元素或者增加元素的时候，就需要将所有元素进行前移或者后移，这样时间复杂度就是O(n)，效率非常低，因此涉及到数据的大量插入和删除的操作就不太适合ArrayList了，因此引入了链表来解决这个问题

链表是一种物理存储上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接的次序进行实现的（物理上是不连续的，但是逻辑上是连续的）

图示：

五。无头单向链表的实现

接口：

java">public interface SingleLinkedList {public void add(int data);//头插法public void addLast(int data);//尾插法public void addIndex(int index,int data);//把data插入到index位置public boolean contains(int key);//链表中是否存在数据keypublic void remove(int key);//删除第一次出现key数据的节点public void display();//展示链表中所有的元素
}

接口的实现：

java">public class SingleList implements SingleLinkedList{static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val=val;}}public ListNode head;@Overridepublic void add(int data) {ListNode node=new ListNode(data);if(this.head==null){head=node;}else {node.next=head;head=node;}}@Overridepublic void addLast(int data) {ListNode node=new ListNode(data);ListNode cur=head;if(head==null){head=node;}else{while(cur.next!=null){cur=cur.next;}cur.next=node;}}@Overridepublic void addIndex(int index, int data) {ListNode node=new ListNode(data);int count=0;ListNode cur=head;if(head==null){head=node;}else{while(cur.next!=null){if(count==index-1){ListNode hi=cur.next;cur.next=node;node.next=hi;break;}count++;}}}@Overridepublic boolean contains(int key) {ListNode cur=head;if(head==null){return false;}else{while(cur.next!=null){if(cur.val==key){return true;}cur=cur.next;}}return false;}@Overridepublic void remove(int key) {ListNode cur=head;ListNode last=head;if(head.val==key){head=head.next;}//当要删除的值是链表的第一位的时候while(cur.next!=null){cur=cur.next;if(cur.val==key){last.next=cur.next;}last=last.next;}}@Overridepublic void display() {ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}}
}

主函数：

java">public class Main {public static void main(String[] args) {SingleList singleList=new SingleList();singleList.addLast(12);singleList.addLast(23);singleList.addLast(34);singleList.addLast(45);singleList.addIndex(1,2);singleList.display();System.out.println(singleList.contains(2));singleList.remove(23);singleList.display();}
}

以上就是单链表的增删查所有的代码，大家可以尝试自己写一遍

六。LinkedList的使用

1.LinkedList介绍：

LinkedList本质上是一个双向链表，由于链表没有将元素存储在连续的空间之中，元素存储在单独的节点之中，然后通过引用节点将节点连接起来了，因此在插入或删除元素的时候，不需要搬移元素，效率较高

2.LinkedList的构造：

java">List<Integer> list1=new LinkedList<>();

3.LinkedList的其他方法的介绍：

java">list1.add(45);//尾插45
list1.add(3,10);//在3这个位置插入10这个数字
list1.remove(2);//删除2位置这个元素
list1.get(2);//获取下标为2的元素的值
list1.set(2,199);//把下标为2的位置的值改为199
list1.contains(199);//查看此链表中是否含有199这个数字
list1.indexOf(199);//返回这个链表中第一次出现199这个元素的下标

4.LinkedList的遍历：

法一：

java">System.out.println(list);

法二：

java">for(int i=0;i<list.size;i++){System.out.println(list.get(i));
}

七。ArrayList与LinkedList的区别

不同点ArrayListLinkedList
存储空间上物理上连续逻辑上连续，但是物理上不一定连续
随机访问支持不支持
头插需要搬移元素，效率低，O（n）只用修改引用的指向，空间复杂读：O（1）
插入空间不够时可以进行扩容没有容量大概念
应用场景元素高效存储+频繁访问任意位置删除添加频繁

http://www.ppmy.cn/news/1475512.html

相关文章

[k8s源码]2.CURD deployment

[k8s源码]2.CURD deployment

加载kubernetes配置 使用 clientcmd方法&#xff0c;是通过"k8s.io/client-go/tools/clientcmd"包加载的。这个函数返回的是config和error两个值。可以看到返回的config是一个指针变量。 func clientcmd.BuildConfigFromFlags(masterUrl string, kubeconfigPath str…
阅读更多...
08 从项目概念到技术概念

08 从项目概念到技术概念

我们从技术转型到管理的路上&#xff0c;如果没有贵人引路&#xff0c;基本上都是要先从项目管理这关过。这其实是一件好事&#xff1b;项目管理里面很多琐碎的知识点&#xff0c;非常有用。我今天想举个例子是项目管理过程中经常提到的 “输入-输出”。 ## 1. 好奇的 DDD DD…
阅读更多...
vue父组件样式穿透修改子组件样式

vue父组件样式穿透修改子组件样式

在 Vue 中&#xff0c;使用父组件样式穿透到子组件通常不推荐&#xff0c;因为它破坏了样式的作用域隔离&#xff0c;但如果你确实需要这样做&#xff0c;可以使用深度选择器。Vue 2 使用 ::v-deep&#xff0c;而 Vue 3 使用 /deep/ 或 ::v-deep 都可以。 以下是使用深度选择器…
阅读更多...
无法访问。你可能没有权限使用网络资源。请与这台服务器的管理员联系以查明你是否有访问权限。【解决办法】

无法访问。你可能没有权限使用网络资源。请与这台服务器的管理员联系以查明你是否有访问权限。【解决办法】

问题描述 新建好一台windows虚拟机&#xff0c;两台设备网络是互通的&#xff0c;但是物理机在访问虚拟机的网络共享文件资源时&#xff0c;出现图下所示的报错&#xff1a;XXX无法访问。你可能没有权限使用网络资源。请与这台服务器的管理员联系以查明你是否有访问权限。用户…
阅读更多...
如何解决数据分析问题：IPython与Pandas结合

如何解决数据分析问题：IPython与Pandas结合

如何解决数据分析问题&#xff1a;IPython与Pandas结合 数据分析是现代科学研究、商业决策和技术开发中的一个重要环节。IPython和Pandas是两个强大的工具&#xff0c;它们可以大大简化和加速数据分析的过程。本文将为初学者详细介绍如何结合使用IPython和Pandas来解决数据分析…
阅读更多...
Spring Boot中处理同名Bean冲突的解决办法

Spring Boot中处理同名Bean冲突的解决办法

核心问题&#xff1a;在Spring Boot项目中&#xff0c;同名Bean的冲突可能导致ConflictingBeanDefinitionException异常。 解决策略&#xff1a; 更换类名&#xff1a; 当两个类未手动设置Bean名称时&#xff0c;修改其中一个类名以避免冲突。 手动设置Bean的名称&#xff1a…
阅读更多...
永恒之蓝：一场网络风暴的启示

永恒之蓝：一场网络风暴的启示

引言 在网络安全的漫长历史中&#xff0c;“永恒之蓝”&#xff08;EternalBlue&#xff09;是一个不可忽视的里程碑事件。它不仅揭示了网络世界的脆弱性&#xff0c;还促使全球范围内对网络安全的重视达到了前所未有的高度。本文将深入探讨“永恒之蓝”漏洞的起源、影响及其对…
阅读更多...
Milvus核心组件（1）- Architecture

Milvus核心组件（1）- Architecture

目录 cluster 模式 数据请求处理流程 总流程 逻辑channel 到物理channel 数据维护流程 cluster 模式 上一篇其实已经说过 standalone 模式&#xff0c;其实集群模式大同小异&#xff0c;只是在不同机子间使用Kafka或者其他消息中间件保证数据及逻辑的一致性。 Log Broker…
阅读更多...
springboot+vue 开发记录（九）后端打包部署运行

springboot+vue 开发记录（九）后端打包部署运行

本篇文章主要内容是后端项目写好了&#xff0c;怎么打包部署到服务器上运行。 文章目录 1. 在服务器上安装Docker2. 在Docker中装MySQL3. 在Docker中设置网桥&#xff0c;实现容器间的网络通信4. 修改后端配置文件5. 修改pom.xml文件6. 打包7. 编写DockerFile文件8. 上传文件到…
阅读更多...
Milvus 核心设计 （4） ---- metric及index原理详解与示例(2)

Milvus 核心设计 （4） ---- metric及index原理详解与示例(2)

目录 背景 Binary Embedding 定义与特点 常见算法 应用场景 距离丈量的方式 Jaccard Hamming 代码实现 Index BIN_FLAT BIN_IVF_FLAT Sparse embeddings 定义 应用场景 优点 实现方式 距离丈量方式 IP Index SPARSE_INVERTED_INDEX 应用场景 优势 SPAR…
阅读更多...
java多线程操作之CAS

java多线程操作之CAS

1&#xff0c;什么是CAS&#xff1f; CAS&#xff08;Compare-And-Swap&#xff09; 比较并交换&#xff0c;用于实现同步和锁机制。经常配合juc中Atomic相关类进行。Atomic相关类无法解决aba问题。 2&#xff0c;CAS核心思想是什么&#xff1f; 比较和交换。本质上就是乐观锁…
阅读更多...
计算1的数量

计算1的数量

1. 计算1的数量 题目ID&#xff1a;9809必做题100分 最新提交&#xff1a; Accepted 100 分 历史最高&#xff1a; Accepted 100 分 时间限制: 1000ms 空间限制: 524288kB 题目描述 给定一个n*m的二进制矩阵&#xff0c;请你数一数矩阵中完全被0上下左右包围的1的数…
阅读更多...
樊登读书精准表达

樊登读书精准表达

阅读建议：本书解读过程中，刘蔚涛老师展示了很多精彩图表，建议配合视频，效果更好。 书友你好，欢迎来到非凡精读馆，我是刘蔚涛。 今天给大家带来一本好书，名字叫作《精准表达》，副标题是“怎么让你的方案在最短的时间内打动人心”。这本书2004年出版，出版后在日本畅销…
阅读更多...
MySQL 日志深度解析：从查询执行到性能优化

MySQL 日志深度解析：从查询执行到性能优化

引言 MySQL 日志是数据库管理员和开发者的宝贵资源&#xff0c;它提供了查询执行的详细情况&#xff0c;帮助我们诊断问题和优化性能。本文将深入分析一个具体的 MySQL 日志条目&#xff0c;解释其含义&#xff0c;并提供针对性的优化建议。 日志信息概览 让我们先来快速了解…
阅读更多...
Perl编译器架构：前端与后端的精细分工

Perl编译器架构：前端与后端的精细分工

&#x1f527; Perl编译器架构&#xff1a;前端与后端的精细分工 Perl作为一种高级、通用的编程语言&#xff0c;其编译器的架构设计对于性能和灵活性至关重要。Perl编译器由前端和后端组成&#xff0c;它们各自承担着不同的职责。本文将深入解析Perl编译器前端和后端的区别&a…
阅读更多...
Gradio聚类

Gradio聚类

为了增加页面输出聚类后的结果并方便可视化分析聚类效果&#xff0c;下面是更新后的代码。将Gradio界面中的输出类型改为gr.outputs.HTML&#xff0c;并在返回结果时生成HTML格式的聚类结果。python import gradio as gr from transformers import AutoTokenizer, AutoModel i…
阅读更多...
绝区捌--将GPT幻觉的发生率从20%以上降低到2%以下

绝区捌--将GPT幻觉的发生率从20%以上降低到2%以下

总结&#xff1a;我们没有使用微调&#xff0c;而是结合使用提示链和预处理/后处理来将幻觉发生率降低一个数量级&#xff0c;但这确实需要对 OpenAI 进行 3-4 倍的调用。还有很大的改进空间&#xff01; 使用 GPT 等大型语言模型面临的最大挑战之一是它们倾向于捏造信息。 这…
阅读更多...
关于maven工程编译的一些问题

关于maven工程编译的一些问题

首先抛问题&#xff0c;在maven clean的时候出现下面的错误&#xff1a; 错误源代码如下&#xff1a; [ERROR] The build could not read 1 project -> [Help 1] [ERROR] [ERROR] The project com.**:**:2.0.0 (D:\JAVA\**-policy\pom.xml) has 1 error [ERROR] N…
阅读更多...
音视频开发—FFmpeg处理流数据的基本概念详解

音视频开发—FFmpeg处理流数据的基本概念详解

文章目录 多媒体文件的基本概念相关重要的结构体操作数据流的基本步骤1.解复用&#xff08;Demuxing&#xff09;2.获取流&#xff08;Stream&#xff09;3. 读取数据包&#xff08;Packet&#xff09;4. 释放资源&#xff08;Free Resources&#xff09;完整示例 多媒体文件的…
阅读更多...
【自动驾驶/机器人面试C++八股精选】专栏介绍

【自动驾驶/机器人面试C++八股精选】专栏介绍

目录 一、自动驾驶和机器人技术发展前景二、C在自动驾驶和机器人领域的地位三、专栏介绍四、订阅需知 一、自动驾驶和机器人技术发展前景 随着人工智能、机器学习、传感器技术和计算能力的进步&#xff0c;自动驾驶和机器人的技术水平不断提升&#xff0c;使得它们更加智能、可…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站