【顺序表和链表】

文章目录

前言

顺序表和链表

1线性表

2.顺序表

3.链表

4.顺序表和链表的区别和联系

提示：以下是本篇文章正文内容，下面案例可供参考

一、线性表

1、线性表

线性表 dinear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通第以数组和链式结构的形式存储。

2、顺序表

概念及结构

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

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储。

2.动态顺序表：使用动态开辟的数组存储。

代码如下；

代码如下；

3、接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基序表根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

代码如下；

4、顺序表的问题及思考

问题；

1.中间/头部的插入删除，时间复杂度为O(N)

2.增容需罗甲请新空间，拷贝数据，释放1日空间。会有不小的消耗。

3.增容一般是呈2倍的增长，势必会有一定的空间浪秀。

例如当前容量为100.满了以后增容到200.我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考

如何解决以上问题呢？下面给出了链表的结构来看看

5、链表

链表的概念及结构

概念链表是一种物理存储结构上非连续 非顺序的存储结构，数据元素的接次席实现的。

代码如下；

顺序表

1、可动态增长的数组
2、数据在数组中存储时必须是连续的

缺点：

1、中间或者头部的插入删除很慢，需要挪动数据。时间复杂度是0(N）
2、空间不够时，增容会有一定消耗和空间浪费。

优点：

1、随机访问。
2、缓存利用率比较高。

6、移除元素

1、给你一个数组nums 和一个值val， 你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

2、不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

3、元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

7、删除排序数组中的重复项

1、给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

2、不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 0(1) 额外空间的条件下完成。

8、数组形式的整数加法

对于非负整数 × 而言，X的数组开式是每位数字按从左到右的顺序形成的数组。

例如，如果X=1231， 那么其数组形式为 [1,2.3,1]。

给定非负整数 x 的数组形式 ：，返回整敬 X 的数组形式。

9、合井两个有序数组

给你两个有序整教数组 nums1 和nums2，请你将nums2 合并到nums1中，使nums1 成为一个有序数组。

说明：

1、初始化qum$1和nums2的元素数量分别为 m和n

2、你可以假设nums1 有足够的空间（空间大小大于或等于m+n）来保存nums2中的元素

9、旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

1、尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

2、你可以使用空间复杂度为。(1) 的 原地 算法解决这个问题吗？

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了顺序链和链表的使用，而顺序链和链表提供了大量能使我们快速便捷地处理数据的方法。