数组、链表、栈和队列、散列表是基础数据结构，几乎所有的高级开发语言都会涉及到这些数据结构，一些更复杂的数据结构也是基于基础数据结构的扩展。
基础数据结构是数据存储的基础理论，有必要彻底理解它。
数据存储结构可以分为 物理结构 和 逻辑结构。
物理结构又分为 线性结构 和 非线性结构
- 线性结构：如 顺序表，栈，队列，
- 非线性结构：如 图，树。
逻辑结构又分为 顺序存储结构 和 链式存储结构
- 顺序存储结构：如 数组。
- 链式存储结构：如 链表。
注意：某些复杂的数据结构是可以基于不同的数据结构类型来实现的，如 二叉树，是一种逻辑结构，也可以依托于物理上的数组或链表来实现。
数组
概念
数组（Array）：是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。
数组在内存中是 顺序存储，在内存中是占用一块块连续的内存空间，数组元素之间紧密排列，即不能打乱元素排列顺序，也不能跳过某个存储单元进行存储。
操作
读取元素
由于数组在内存中顺序存储，只要给出一个数组下标，就可以读取到应用的数组元数。数组下标从 0 开始，给出的数组下标必须在数组的长度范围之内，否则出现数组越界。
更新元素
把数组中某一个元数的值替换为一个新值。直接根据数组下标，赋给该元数新值。
插入元素
尾部插入：尾部插入最简单，直接在尾部追加。
中间插入：稍许复杂，需要把插入位置的元素及后面的元素向后移动，为插入元素腾出空间。
超范围插入：因数组的容量在创建时就确定的，如果需要超范围插入，就涉及数给扩容，通常是创建一个新数给，为旧数组的 2 倍，在把旧数组中的元素全部复制到新数组。
删除元素
根据元素下标删除，实际是把要删除的元素的后面元素向前挪动 1 位，覆盖要删除的元素。若没有顺序要求，可将最后一个元素赋值给要删除的元素的位置，这就无须进行大量的元素移动。
优势和劣势
- 优势：高效的访问性能，只需给出下标，就可找到对应的元素。
- 劣势：体现在插入和删除元素方面。因数组元素是连续紧密存储在内存在，插入、删除操作会导致大量元素被迫移动，影响效率。
通常来说，数组适合读操作多，写操作少的场景。
链表
链表（Linked list）：是一种在物理上 非连续、非顺序的数据结构，由若干节点（node）所组成。
链表在内存中的存储方式是 随机存储，这样可以有效地利用零散的碎片空间。
单向链表
单向链表 的每一个节点又包含两部分，一部分是存放数据的变量 data，另一部分是指向下一个节点的指针 next 。通过指针把数据完整地链接起来。
第 1 个节点被称为头节点，最后 1 个节点被称为尾节点，尾节点的 next 指针指向空。
单向链表只能一级一级，单线传递查找。
双向链表
双向链表 比单向链表稍微复杂一些，每一个节除了拥有 data 和 next 指针，还多了指向前置节点的 prev 指针。
基本操作
查找节点
只能从头节点开始，根据节点的 next 指针向后一个一个节点逐一查找。
更新节点
先查找节点，把旧数据替换成新数据即可。
插入节点
尾部插入：最简单，把最后一个节点的 next 针指指向新插入的节点即可。
头部插入：把新节点的 next 指针指向原先的头节点，把新节点变为链表的头节点。
中间插入：插入位置的前置节点的 next 指针指向插入的新节点，新节点的 next 指针指向前置节点的 next 指针原先指向的节点。
删除元素
尾部删除：最简单，把倒数第 2 个节点的 next 指针指向空即可。
头部删除：把链表的头节点设为原头节点的的 next 指针即可。
中间删除：把要删除节点的前置节点的 next 指针，指向要删除节点的下一个节点即可。
链表实现
package com.datastructure.linkedlist;
public class MyLinkedList1 {
//头节点指针
private Node head;
//尾节点指针
private Node last;
//链表实际长度
private int size;
/**
* 插入节点
*
* @param data
* @param index
*/
public void insert(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node insertNode = new Node(data);
if (size == 0) {
//空链表新增第一个
head = insertNode;
last = insertNode;
} else if (index == 0) {
//插入头部
insertNode.next = head;
head = insertNode;
} else if (index == size) {
//插入尾部
last.next = insertNode;
last = insertNode;
} else {
//插入中间
//找到前置节点
Node prevNode = get(index - 1);
//找到后置节点
Node nextNode = prevNode.next;
//前置节点next指针指向新插入的节点
prevNode.next = insertNode;
//新插入的节点的next指针指向原后置节点
insertNode.next = nextNode;
}
size++;
}
/**
* 删除节点
*
* @param index
* @return
*/
public Node remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表的范围");
}
Node removeNode = null;
if (index == 0) {
//删除头节点
removeNode = head;
head = head.next;
} else if (index == size - 1) {
//删除尾节点
Node prevNode = get(index - 1);
removeNode = prevNode;
//前置节点变为尾节点
last = prevNode;
//尾节点的next变为null
prevNode.next = null;
} else {
//删除中间节点
//获取前置节点
Node prevNode = get(index - 1);
//根据前置节点获取下下个节点(要删除的节点的下一个节点)
Node nextNode = prevNode.next.next;
removeNode = prevNode.next;
prevNode.next = nextNode;
}
size--;
return removeNode;
}
/**
* 链表查找元素
*
* @param index
* @return
*/
private Node get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node temp = head;
for (int i = 0; i < index; i++) {
//逐一查找
temp = temp.next;
}
return temp;
}
/**
* 输出链表
*/
public void output() {
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
public static void main(String[] args) {
MyLinkedList1 myLinkedList1 = new MyLinkedList1();
myLinkedList1.insert(3, 0);
myLinkedList1.insert(7, 1);
myLinkedList1.insert(4, 2);
//插入尾节点
myLinkedList1.insert(2, 3);
//插入头节点
myLinkedList1.insert(6, 0);
//插入中间节点
myLinkedList1.insert(8, 2);
myLinkedList1.output();
System.out.println("--------------------------");
//移除头节点
myLinkedList1.remove(0);
//移除中间节点
myLinkedList1.remove(3);
myLinkedList1.output();
}
}
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
循环链表
循环链表 即尾节点的 next 指针指向 头节点，如果是双向循环链表，则头节点的 prev 指针指向属节点。
数组VS链表
数组 的优势在于能够快速定位元素，对于读操作多，写操作少的场景来说比较合适。
链表 的优势在于能够灵活地进行插入和删除操作，如需要在链表尾部频繁执行插入、删除操作，则链表更合适。
| 时间 / 空间复杂度比较 | 查找 | 更新 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | Ο(1) | Ο(1) | Ο(n) | Ο(n) |
| 链表 | Ο(n) | Ο(1) | Ο(1) | Ο(1) |
哈希表
哈希表也称为 散列表（Hash Table），提供键（Key） 和值（Value）映射关系。只要给出 key ，就可以高效查找到映射的 Value，时间复杂度接近于 Ο(1) 。
哈希函数
哈希表 在本质上也是一个数组，通过 哈希函数 将数组下标转换为 Key 值。
不同的语言中，哈希函数 的实现方式不一样，下面以 Java 中的 HashMap 为例进行分析。
Java 中的每一个对像都有属于自己的 hashcode ，hashcode 是个整型变量，是区分不同对象的重要档识。
整型变量转化成数组下标，最简单的转化方式是按照数组长度进行取模运算。而 JDK 中的哈希函数是利用位运算的方式来优化性能。
取模运算，例如一个长度为 8 的数组，key 为 001121，转换为数组下标 index = hashcode("001121") % Array.length = 1420036703 / 8 = 7。
基本操作
写操作（put）
写操作就是在散列表中插入新的键值对。以 HashMap 为例。
a. 实际是通过哈希函数，把 key 转化成数组下标。
b. 如果数组该下标对应的位置没有元素，就把这个元素存入到该位置。
c. 数组长度是有限的，当插入的元素越来越多时，不同的 Key 通过哈希函数获取的下标有可能相同，这种情况就出现了 哈希冲突。
哈希冲突是无法避免的，但然要想办法解决，主要有两种方法：一种是开放 寻址法，一种是 链表法。
开放寻址法
当一个 Key 通过 哈希函数 获得对应的数组下标已被占用时，则寻找下一个空的位置。这只是开放寻址法的基本思路。
寻址方式有很多种，如 线性探测再散列，二次探测再散列、双重散列等方法，使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，总能找到空的散列地址。可参考 数据结构：哈希表以及哈希冲突的解决方案 博文。
在 Java 中，
ThreadLocal所使用的就是开放寻址法。链表法
Java 的 HashMap 使用此方法。
HashMap 数组中的每一个元素不仅是一个
Entry对象，还是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需插入到对应的链表中即可。备注： JDK 8 和以前的版本有较大的不同。当多个 Entry 被 Hash 到同一个数组下标的位置时，为了提升插入和查找的效率，HashMap 会把 Entry 的链表转化为
红黑树这种数据结构。
读操作（get）
通过给定的 Key ，在散列表中查找对应的 Value。
a. 通过哈希函数，将 key 转换成数组下标。
b. 若直接找到则返回，若没有找到，则顺着该 Entry 的链表往下找到与 Key 对应的元素。
扩容（resize）
数组存在扩容，散列表是基于数组的，也同样涉及扩容的问题。
当散列表中多次插入元素达到一定饱和度时， Key 映射位置发生冲突的概率会逐渐提高。当大量元素拥挤在相同的数组下标位置，会形成很长的链表，对后续的插入和查表操作的情能有很大的影响。
这时，散列表就需要扩展它的长度，即需要进行 扩容 。
JDK 中的散列表实现类 HashMap 的扩容有两个因素：
- Capacity：即 HashMap 的当前长度。
- LoadFactory：即 HashMap 负载因子，默认值为
0.75f。
扩容 是创建一个新的 Entry 空数组，长度为原数组的 2 倍。重新 Hash，遍历原 Entry 数组，把所有 Entry 重新 Hash 到新数组中。重新 Hash 是因为扩大长度后， Hash 规则也随之改变。
经过扩容，原来拥挤的散列表重新变得稀疏，原有的 Entry 也重新得到了尽可能均匀的分配。
其它参考
注意：本文归作者所有，未经作者允许，不得转载
