数据结构基本概念

相互之间存在一种或多种特定关系的数据元素集合。

(ER图：实体关系图)

数据对象中数据元素之间的关系

逻辑结构

1、集合结构

2、线性结构

3、树形结构

4、图形结构

下图：从又到左对应1-4

物理结构

1、顺序存储结构

2、链式存储结构

---

线性表

说明：线性表指的是逻辑结构、顺序表和链表指的是存储结构(也叫物理结构)。

概念：a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继，n为线性表的长度 ，若n==0时，线性表为空表

顺序存储

存储位置连续，可以很方便计算各个元素的地址

如每个元素占C个存储单元，那么有：

Loc(An) = Loc(A1)+(i-1)*C;

优缺点： 查询效率高、插入删除效率低

代表：Java中的ArrayList(底层数据结构采用的数组的方式)

链式存储

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

1、单向链表

2、双向链表

双向链表(LinkedList)由前驱、后继、数据三部分组成，并且尾部节点和头部节点未连接起来。

3、循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表

4、双向循环链表

双向循环链表是单向循环链表的每个结点中，再设置一个指向其前驱结点的指针域。(LinkedHashMap)

对于空的双向循环链表

双向循环链表插入过程，p和p->表示两个节点。

双向循环链表删除。(可参考LinkedList源码中的remove方法)

---

参考：

https://www.cnblogs.com/ysocean/p/7928988.html