我们经常会在程序中需要将一组数据元素作为整体管理和使用,作为变量或者参数。并且这一组数据中包含的数据元素是可以变化的(如增加或删除数据元素)。
对于这样的一组数据,我们可以看出一个序列,用数据元素在序列中的位置和顺序,表示某种有实际意义的信息或表示数据之间的关系。
这样的一组序列元素的组织形式,我们将其成为为线性表。一个线性表表示某一类元素的集合,同时记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一,应用广泛,并经常被作为更复杂的数据结构的实现基础。
根据线性表的实现方式,分为两种实现模型:

顺序表: 将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。
链表: 将元素存放在通过链接构造起来的一系列存储块中。

1. 顺序表

1.1 基本形式

图a表示的顺序表,每个元素所占的存储单元大小是固定的,元素的下标就是其逻辑地址,数据元素连续存储。存储每个元素的实际内存地址(即元素的物理地址)可以通过存储区的起始地址(即e0的物理地址Loc(e0))加上逻辑地址(即下标)与存储单元大小(c)的乘积计算而得:
Loc(ei) = Loc(e0) + c * i
所以,我们访问指定元素时不需要从头遍历,通过下标可以很方便的获取到对应的地址,其时间复杂度为O(1)。
着在多数编程语言中,都提供着这种顺序表的实现,如 C/C++、OC中的基本数组等。

很多时候,我们存储的元素大小并不统一,则需要采用图b这样的元素外置的形式,将实际的数据元素另外存储,然后将其地址信息存储到顺序表中,顺序表中各单元位置保存着对应元素的地址信息(指针)。由于每个地址信息所需要的存储量相同,我们可以通过上面的公式,计算出元素指针所在的存储地址,然后顺着指针找到数据元素。
图b这样的顺序表也被称为对实际数据的索引,是最简单的索引结构。
这种顺序表也几乎所有高级语言都提供着实现,如C++中的vector,OC中的NSArray,Swift中的Array,Python中的List,JS总的Array,Java中的List,Go中的数组。

1.2 顺序表操作

1.2.1 增加元素

  • 图a,在顺序表尾端增加元素,不需要修改原顺序表数据区块,时间复杂度为O(1)
  • 图b,在顺序表中指定位置插入元素,不要求保持后续元素为原有的顺序(即不保序)。先将要插入的位置存储的数据存储到顺序表尾端,然后再将此位置存入新的插入元素,时间复杂度为O(1),但是这种操作并不常见。可以这样理解,有一群人站成了一队,然后又来了个人,看到甲所在位置不错,把甲赶到了最后,然后自己站到了甲的位置。
  • 图c,在顺序表中指定位置插入元素,要求保持后续元素为原有的顺序(即保序)。从要插入的位置开始,所有的元素往后移一个单元,然后再将这个元素插入到指定位置,时间复杂度为O(n)。可以这样理解,有一群人站成了一队,然后又来了个人,看到甲所在位置不错,硬挤到了甲站的位置,把所有人都往后挤了一位。(当然这种人更容易被打死)

1.2.1 删除元素

  • 图a,删除尾端的元素,时间复杂度为O(1)。
  • 图b,不保序的元素删除(不常见),时间复杂度为O(1)。可以这样理解,有一群人站成了一队,然后中间走了个人,这是最后一个人看到走了一个人,那不就要空一个位置了啊,就跑过去了。
  • 图c,保序的元素删除,时间复杂度为O(n)。可以这样理解,有一群人站成了一队,然后中间走了个人,后边的所有人就自觉向前进一步。

2. 链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,所以使用起来并不是很灵活。
链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

2.1 链表定义

链表是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。

2.2 单向链表

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置
  • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

接下来我将使用各种语言对链表何其操作进行实现

微信 OR 支付宝 扫描二维码
给复仇者码农 打个赏吧  
微信打赏   支付宝打赏  
金额随意 快来“打”我呀~

发表评论