关于数据结构:线性表数组和链表

概要

线性表是一种线性构造，它是具备雷同类型的 n(n≥0)个数据元素组成的无限序列。本文先介绍线性表的几个根本组成部分：数组、单向链表、双向链表；随后给出双向链表的 Java 语言的实现。

文章转载自：https://www.cnblogs.com/skywa…

数组

数组 是一种最罕用的线性数据结构，外面寄存的元素的类型是一样的，并且有序的。

数组的特点是：数据是间断的；随机访问速度快。

对于 Java 而言，Collection 汇合中提供了 ArrayList 和 Vector 用于数组这种数据结构的实现。

单向链表

单向链表 (单链表) 是链表的一种，它由节点组成，每个节点都蕴含下一个节点的指针。

单链表的示意图如下：

表头为空，表头的后继节点是 ” 节点 10″(数据为 10 的节点)，” 节点 10″ 的后继节点是 ” 节点 20″(数据为 10 的节点)，…

单链表删除节点

删除 ” 节点 30″
删除之前：” 节点 20″ 的后继节点为 ” 节点 30″，而 ” 节点 30″ 的后继节点为 ” 节点 40″。
删除之后：” 节点 20″ 的后继节点为 ” 节点 40″。

单链表增加节点

在 ” 节点 10″ 与 ” 节点 20″ 之间增加 ” 节点 15″
增加之前 ：” 节点 10″ 的后继节点为 ” 节点 20″。
增加之后：” 节点 10″ 的后继节点为 ” 节点 15″，而 ” 节点 15″ 的后继节点为 ” 节点 20″。

单链表的特点是：节点的链接方向是单向的；绝对于数组来说，单链表的的随机访问速度较慢，然而单链表删除 / 增加数据的效率很高。

双向链表

双向链表 (双链表) 是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点。个别咱们都结构双向循环链表。

双链表的示意图如下：

表头为空，表头的后继节点为 ” 节点 10″(数据为 10 的节点)；” 节点 10″ 的后继节点是 ” 节点 20″(数据为 10 的节点)，” 节点 20″ 的前继节点是 ” 节点 10″；” 节点 20″ 的后继节点是 ” 节点 30″，” 节点 30″ 的前继节点是 ” 节点 20″；…；开端节点的后继节点是表头。

双链表删除节点

删除 ” 节点 30″
删除之前 ：” 节点 20″ 的后继节点为 ” 节点 30″，” 节点 30″ 的前继节点为 ” 节点 20″。” 节点 30″ 的后继节点为 ” 节点 40″，” 节点 40″ 的前继节点为 ” 节点 30″。
删除之后：” 节点 20″ 的后继节点为 ” 节点 40″，” 节点 40″ 的前继节点为 ” 节点 20″。

双链表增加节点

在 ” 节点 10″ 与 ” 节点 20″ 之间增加 ” 节点 15″
增加之前 ：” 节点 10″ 的后继节点为 ” 节点 20″，” 节点 20″ 的前继节点为 ” 节点 10″。
增加之后：” 节点 10″ 的后继节点为 ” 节点 15″，” 节点 15″ 的前继节点为 ” 节点 10″。” 节点 15″ 的后继节点为 ” 节点 20″，” 节点 20″ 的前继节点为 ” 节点 15″。