在不少高级语言中，都有链表(linked list)这种数据结构。在很多情况下,我们用数组就能很好的完成工作,而且不会产生太多的差异,那么链表存在的意义是什么?链表相比于数组有什么优势或者不足吗?

什么是链表

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer).

从本质上来讲，链表与数组的确有相似之处，他们的相同点是都是线性数据结构，而它们的不同之处在于数组是一块连续的内存，而链表可以不是连续内存，链表的节点与节点之间通过指针来联系。

链表与数组

链表也有不同的形态,主要分为三种:单向链表、双向链表、循环链表。这里仅说一下单向链表。

单向链表的节点通常由两个部分构成,一个是节点储存的值val,另一个就是节点的指针next.

单向链表

链表与数组类似,也可以进行查找、插入、删除、读取等操作,但是由于链表与数组的特性不同,导致不同操作的复杂度也不同.

查找性能

单向链表的查找操作通常是这样的:

  1. 从头节点进入,开始比对节点的值,如果不同则通过指针进入下一个节点
  2. 重复上面的动作,直到找到相同的值,或者节点的指针指向null

链表的查找性能与数组一样,都是时间复杂度为O(n).

插入删除性能

链表与数组最大的不同就在于删除、插入的性能优势，由于链表是非连续的内存,所以不用像数组一样在插入、删除操作的时候需要进行大面积的成员位移，比如在a、b节点之间插入一个新节点c,链表只需要:

  1. a断开指向b的指针，将指针指向c
  2. c节点将指针指向b，完毕

这个插入操作仅仅需要移动一下指针即可，插入、删除的时间复杂度只有O(1).

链表的插入操作如下:

链表的插入

链表的删除操作如下:

链表的删除

读取性能

链表相比之下也有劣势，那就是读取操作远不如数组，数组的读取操作之所以高效，是因为它是一块连续内存，数组的读取可以通过寻址公式快速定位，而链表由于非连续内存，所以必须通过指针一个一个节点遍历.

比如,对于一个数组,我们要读取第三个成员,我们仅需要arr[2]就能快速获取成员,而链表则需要从头部节点进入,在通过指针进入后续节点才能读取.

作者：寻找海蓝96
链接：https://juejin.im/post/5d843f145188254009776ea5
来源：掘金

什么是数组

数组是一组包含有序元素的集合。数组的特点如下：

  • 元素在内存中的顺序是连续的
  • 数组里面的元素的数据类型都是一样的。就是一个数组不能存储两个类型
  • 数组的下标是整型。
char a[5]  = "hello";

数组

链接：https://www.kancloud.cn/qingyi_zyf/php/702187

UDEC/3DEC 中的数据结构

UDEC中的数据结构

UDEC中的数据结构

其中

UDEC中的变量存储在链表中，可以使用 PRINT 命令找到数据对象的地址。在大多数情况下，给定的第一个整数是地址。 UDEC中的命令允许记录（使用 HISTORY 命令）或更改（使用CHANGE 或 RESET 命令）常用的变量。也可以通过FISH访问变量以记录或更改不太常用的变量，或定义一个变量对另一个变量的依赖性（例如，UDEC中不同节理模型的直接剪切以及循环剪切模拟案例 2.4节的模型代码；或者可以参见手册第3.7.3节）。

链表索引和偏移量：

FISH程序可以访问UDEC的某些链表数据结构。指向这些数据结构的全局索引以FISH标量变量(即存储一个数字数据的变量)的形式提供（请参阅帮助文档 UDEC-Specific Scalar Variables）。 UDEC提供的一系列文件中包含各种数据块和数据块中项目的偏移量，这些文件的扩展名是“ .FIN”（Fish INclude file），它们提供偏移量和当前数值的符号名称。

“ .FIN”文件有两个作用：第一，它们记录各种数据项的含义；其次，可以从FISH函数或命令流文件中调用FIN文件。它们自动执行并定义适当的符号，这些符号前面都带有$符号，因此使用 PRINT fish 命令看不到它们。 FISH编程中可以简单地使用数字或“ .FIN”文件中提供的符号作为偏移量。最好以符号形式指定偏移量，因为在未来版本中，偏移量和文件大小虽然可能发生变化但符号名将尽可能的保留，使用提供的符号作为偏移量就大概率可以在将来版本中不用修改含有这些偏移量的FISH程序。 （Itasca在帮助文档中放话了：将尽一切努力在将来的UDEC版本中保留相同的符号名）

全局索引(包括主要数据组及文件名)

全局索引(包括结构单元数据组的文件名)

3DEC中的数据结构

3DEC中的数据结构

跟UDEC一样，3DEC中的变量也存储在链表中，该列表由索引（特定项的第一个存储位置例如块体或接触）和偏移量组成，这些偏移量规定了变量相对于索引的存储位置。上面示意图显示了这些不同组的链接关系。

可以使用 LIST 命令找到数据对象的索引。在大多数情况下，给定的第一个整数是索引。 3DEC中的命令允许跟踪（使用HISTORY命令）或更改（使用CHANGE或RESET命令）常用的变量。也可以通过FISH访问变量以跟踪或更改不太常用的变量，或者定义一个变量对另一个变量的依赖性。

FISH程序可以访问3DEC的某些链表数据结构。balabala一大堆，跟上面一样的。3DEC通过 fmem，imem 和 xmem 函数访问数据结构。

FIN文件使用说明

就拿UDEC中的“ BLOCK.FIN”文件说明。该文件提供对块体，角点，网格点和单元数据的访问。 文件很长，下图仅为其中对块体数据访问的文件节选

可通过 block_head 访问块体数组索引。 在此基础上，如果要访问块体角点、网格节点、单元的信息，可以分别使用 b_corner、 b_gp 和 b_zone 来实现访问。块体角点、网格节点、单元都存储在块体的链表数据结构中，这也就是为什么在遍历网格节点或者单元信息的时候，最外层循环都得是从 block-head 开始的原因。

UDEC手册中有很多例子里都调用过 .FIN 文件，下面就拿一个最简单的例子来解释一下：

上面是一个受荷地基的半模型(对称只取一半分析)，完整的命令流可以查看手册，或者下面的链接

pran.dat

我只解释一下FISH函数部分的意思

def stripload
    sum =0.0
    ib = block_head
    loop while ib # 0
        ig = b_gp(ib)
        loop while ig # 0
        if gp_y(ig) > 9.8 then
            if gp_x(ig) < 3.0 then
            ibou=gp_bou(ig) ; index of boundary corner
                if(ibou) > 0 then ; exterior boundary
                    if (imem(ibou+$KBDY)) = 4 then
                    forcey = fmem(ibou+$KBDFY) ; total y-force
                    sum = sum - forcey
                    endif
                endif
            endif
        endif
        ig = gp_next(ig)
        endloop
        ib = ib_next(ib)
    endloop
    x_p = gp_x(p_xp)
    x_m = gp_x(p_xm)
    p_load = 2.0 * sum / (x_p + x_m)
    y_disp = -gp_ydis(p_y0)
    stripload = p_load
    err = (p_load-solution)/solution
end

这个FISH函数是为了将加了速度边界的边界节点找出来，并获得这些节点上的竖向节点力。

首先获得块体索引，当块体索引不为零时，获得块体网格节点的索引，通过判断网格节点的x和y方向的坐标来定位所加速度边界的位置。在节点索引的基础上接着获取节点所在边界点的索引，判断该索引值大于零时(UDEC中外边界的索引大于零，内边界的索引小于零)再判断该边界点是否加的速度边界

$KBDY 符号偏移值代表y方向边界条件的类型。使用 imem 函数得到边界点的索引加该符号偏移值之后的值，判断如果等于4，即为速度边界的边界点，判断若为真再使用 fmem 函数得到该边界节点的y方向节点力，并进行累加求和，直到遍历所有的满足条件的边界点。

操作FIN文件直接访问了其数据结构，不当的操作可能会产生严重错误。使用这些函数之前，请务必注意“ .FIN”文件中的变量是浮点型，整数型还是索引型。另请注意，对内存内容进行无节制的改动可能会使计算机崩溃，因此，任何更改内存内容的操作都应小心进行。如果刚开始学习FISH语句不建议调用FIN文件，在使用时要务必小心。

长风破浪会有时，直挂云帆济沧海。