数据结构与算法分析之表（链表）引言一、表二、表的简单数组实现三、简单链表感谢阅读

68 阅读 0 评论 45 点赞

我是靠谱客的博主忧郁酸奶，最近开发中收集的这篇文章主要介绍数据结构与算法分析之表（链表）引言一、表二、表的简单数组实现三、简单链表感谢阅读，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

引言
一、表
二、表的简单数组实现
三、简单链表
感谢阅读

引言

数组是我们在编程时经常用到的一个东西，但是数组在使用中有一个很大的问题，那就是数组的容量是一开始就确定好了的，如果在使用中我们发现数组的容量不够用，我们的编程就会有很大阻碍，于是我们就引入了表的概念。

一、表

我们在学习编程语言是肯定学过数组，那么我们就以数组为原型来在大脑中建立表的模型。

首先有一个数组，如
$A_0，A_1，A_2，A_3，A_4，A_4，A_5......A_{N-2}，A_{N-1}$
现在我们将其称之为表，假设表就是这个样子。这时，我们说这个表的大小是N。那么当N等于0时我们将这个表称之为空表。

对于非空表（即N大于零），我们说 $A_i$ 后继 $A_{i-1}$ ，同时也称 $A_{i-1}$ 前驱 $A_i$ 。表的一个元素为 $A_0$ ，所以 $A_0$ 没有定义前驱；同样的，表的最后有个元素 $A_{N-1}$ 也没有后继。

二、表的简单数组实现

前面我们用一个数组的原型来在我们大脑中建立了一个表的模型，现在我们通过数组来实现一下这个表的模型。

在表的使用中，它的一些增、删、查、改都可以用数组来完成，所以我们就直接聊最重要的那部分，也就是数组无法完成的扩容的问题，这个时候表达的概念就被引入进来了：

int[] arr = new int[10];
...
//下面我们决定需要扩大arr
int[] newArr = new int[arr.length * 2];
for(int i = 0; i < arr.length; i++)
	newArr[i] = arr[i];
arr = newArr;

这时有人就会说了，这不还是数组吗？

对。数组只是表的一种恰当的实现，表的引入只是在数组的基础上引入了前驱、后继还有上面这种一个数组替换另一个数组在达到扩容的效果，表本质上的一些东西还是和数组很像。
但是，这时候就有个但是了，因为数组的局限性，我们添加了一些概念使数组变成表就多了自动扩容的功能。但是这些还不够，表的使用依旧不够快捷、高效、简单，于是我们对表再添加一些定义，使之变成了链表，经过一代又一代的优化升级，链表就不那么像数组，那下面我们来讲一讲链表。

三、简单链表

首先我们来画一个链表的模型：

一个链表
链表由一系列节点组成，这些节点不必在内存中相连。每一个节点均含有表元素和到包含该元素后继元的节点的链（link）。我们称之为next链。最后一个单元的next链引用null。

这时我们来比较一下数组和链表的优缺点：

①删除：
在数组中，我们要删除某个元素时，例如：1，2，3，4，5 当我们要删除“3”时，我们要把“4”、“5”都往前移一个位置，然后把原来的“5”的位置上的数删掉，当这个数组很大时，这个操作的时间复杂度就会很高

那当我们用链表时呢，我们来画一个示意图：
在这里插入图片描述
例如我们要删除 $A_2$ ，我们只要把 $A_1$ 的next链指向 $A_3$ 就行了，非常的简单快速。

②添加
同样的一个数组：1，2，3，4，5 当我们要在“2”和“3”之间添加一个元素“8”，我们需要把原来“3”的位置的数变成“8”，原来“4”的位置的数变成“3”，原来“5”的位置的数变成“4”，最后面再加一个“5”，这都打字打得手累了，非常的麻烦。

而当我们用链表时呢：
在这里插入图片描述
例如上图将 $A_8加到A_1和A_2$ 之间，只需要将 $A_1$ 的next链指向 $A_8$ ，再将 $A_8$ 的next链指向 $A_2$ 就完成了。

当然，也不是数组说数组全都是确定，比如在数组中查询某个位置的元素非常简单快捷，直接就能查到，但是链表因为没有了标号，就没法直接查某个位置的元素了。

当然这种单向的链表只能从前往后查，没有办法从后往前查，因为后面的元素没有告诉前面的的元素是什么，于是我们将单向链表又进行升级，就有了双链表，下面是双链表的模型：
在这里插入图片描述
我们发现，双链表在单链表的基础上，每个节点加了一个prev链，这个prev链指向这个元素的上一个元素的位置，这样我们就能在任意元素上去找它的上一个元素和下一个元素了。