一、线性表-数组和矩阵

数组是一种连续存储线性结构，元素类型相同，大小相等，数组是多维的，通过使用整型索引值来访问元素，数组大小不能改变。

1.1、数组的优缺点

• 存取速度快。

• 事先必须知道数组的长度。

• 插入删除元素很慢，效率很低（涉及到数组的复制，资源耗费大）。

• 空间通常是有限制的。

• 需要大块连续的内存块。

1.2、数组与矩阵相关题目

1、把数组中的 0 移到末尾

2、改变矩阵维度

二、线性表-链表

n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来。

2.1、优缺点

• 空间没有限制。

• 插入删除元素很快。

• 存取速度很慢

2.2、分类

• 单向链表：一个节点指向下一个节点

• 双向链表：一个节点有两个指针域

• 循环链表：能通过任何一个节点找到其他所有的节点，将两种（单向/双向）链表的最后一个节点指向第一个节点从而实现循环。

2.3、实现

三、线性表-哈希表（散列）

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

3.1、概念

• Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。

• Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。例如在一个简化 url 的系统中 Leetcdoe : 535. Encode and Decode TinyURL (Medium)在新窗口打开，利用 HashMap 就可以存储精简后的 url 到原始 url 的映射，使得不仅可以显示简化的 url，也可以根据简化的 url 得到原始 url 从而定位到正确的资源。

四、线性表-栈和队列

数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用。

4.1、栈-FILO

• 使用数组实现的叫静态栈

• 使用链表实现的叫动态栈

4.2、队列-FIFO

• 使用数组实现的叫静态队列

• 使用链表实现的叫动态队列

五、树-基础和Overview

5.1、树的相关概念