常用数据结构笔记
什么是数据结构
数据结构是计算机存储数据、组织数据的方式。
数据结构类型大致可以分为:
- 线性结构:
常见的有: 线性表(数组、队列、链表、栈、哈希表等) - 树形结构:
常见的有: 二叉树、红黑树、AVL树、B树、堆、Trie、哈夫曼树、并查集等 - 图形结构:
常见的有: 邻接矩阵、邻接表等
线性数据结构
线性表: 线性表是具有n个相同类型元素的有限序列(n>=0)
- a1是首节点，an是尾节点
- a1是a2的前驱，a2是a1的后继
数组
数组是一种顺序存储的线性表，所有元素的内存地址是连续的
int [] array = new int[]{11,22,33};
数组的缺点: 容量固定，无法动态修改数组的容量；这个时候就需要用到动态数组
动态数组(ArrayList)
动态数组的接口设计:
1
2
3
4
5
6
7
8
9
10
11
int size();// 元素的数量
boolean isEmpty();// 数组是否为空
boolean containis(E element);// 是否包含某个元素
void add(E element);// 添加元素到最后面
E get(int index);// 获取index位置对应的元素
E set(int index, E element);// 设置index位置对应的元素
void add(int index, E element);// 在index位置添加元素
E remove(int index);// 删除index位置对应的元素
int indexof(E element);// 查看元素的位置
void clear();// 清除所有元素
动态数组的缺点：
- 创建时有一个初始的内存空间，当添加新元素且内存空间不够时，会开辟一个当前数组内存空间大小的新空间。这样就会造成内存空间的大量浪费。可以通过链表来解决这一问题。
- 动态数组在尾部添加元素的复杂度是O(1), 在头部移除元素的复杂度是O(N).
链表(LinkedList)
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。
链表的接口设计:
- 链表自身必须有2个接口:
1
2
3
int size(); // 返回链表的长度(节点的数量)
E first();// 返回链表的头结点
- 链表节点的接口设计:
1
2
3
E element; // 本节点存储的节点数据
E next;// 下一个节点(指针)
- 单向链表
- 双向链表
- 循环链表
- 静态链表
栈(Stack)
队列(Queue)
队列是一种特殊的线性表，只能在头尾两端进行操作 队尾(rear): 只能从队尾添加元素，一般叫做enQuene，入队 队头(front): 只能从队头移除元素，一般叫做deQueue，出队 原则: 先进先出(First in first out, FIFO)
队列的接口设计：
1
2
3
4
5
6
int size();// 元素的数量
boolean isEmpty(); // 队列是否为空
void enQueue(E element); // 入队，队尾添加元素
void deQueue();// 出队，从队头移除元素
E front();// 获取队列头元素
void clear(); // 清空队列
队列内部可以使用基础数据结构来实现: 动态数组、链表 优先使用双向链表，因为队列就是从头尾操作元素
- 双端队列(Deque)
- 循环队列
哈希表(HashTable)
哈希表也叫做散列表(hash有”剁碎“的意思) 哈希表通过哈希函数来实现高效处理数据
添加、搜索、删除数据的流程都类似：
- 利用哈希函数生成key对应的index，时间复杂度为O(1)
- 根据index操作定位数组元素，时间复杂度为O(1)
树形数据结构
二叉树(BinaryTree)
(☆)二叉搜索树(BinarySearchTree\BST)
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称BST，又被成为二叉查找树、二叉排序树
特点:
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也是一颗二叉搜索树
二叉搜索树可以大大提高搜索数据的效率 二叉搜索树存储的元素必须具备可比较性 比如int、double等; 对于自定义类型的节点，需要指定比较方式
不允许为nil
二叉搜索树的接口设计:
1
2
3
4
5
6
7
int size(); // 元素的数量
boolean isEmpty();// 是否为空
void clear();// 清除所有元素
void add(E element);// 添加元素
void remove(E element);// 移除元素
boolean contains(E element);//是否包含该元素
注意点: 二叉搜索树没有索引的概念，因为根本用不上
平衡二叉搜索树(BalancedBinarySearchTree\BBST)
- AVL树(AVLTree)
- (☆)红黑树(RedBlackTree)
红黑树是一种自平衡的二叉搜索树，也可以叫做平衡二叉B树(Symmetric Binary B-tree)
红黑树必须满足以下5条性质:
- 节点是Red或者Black
- 根节点是Black
- 叶子节点(外部节点，空节点，null节点)都是Black
-
Red节点的子节点都是Black
Red节点的子节点都是Black
从根节点到子节点的所有路径上不能有2个连续的Red节点
- 从任意节点到叶子节点的所有路径都包含相同数量的Black节点
(☆)B树(B-Tree)
集合(TreeSet)
集合的特点:
-
不存放重复的元素
-
常用于去重
- 存放新增的IP，统计新增IP量
- 存放词汇，统计词汇量
集合的接口设计:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Set<E> {
int size();
boolean isEmpty();
void clear();
boolean contains(E element);
void add(E element);
void remove(E element);
void traversal(Visitor<E> visitor); // 遍历集合
public static abstract class Visitor<E> {
boolean stop;
abstract boolean visit(E element);
}
}
集合的内部实现可以利用: 动态数组 链表 二叉搜索树(AVL树、红黑树)
映射(TreeMap)
Map 在有些编程语言里也叫做字典(dictionary,比如Python、objective-c、Swift等) Map以key-value的形式存储数据 每个key都是唯一的
Map的接口设计:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public interface Map<K, V> {
int size();
boolean isEmpty();
void clear();
V put(K key, V value);
V get(K key);
V remove(K key);
boolean containsKey(K key);
boolean containsValue(V value);
void (Visitor<K, V> visitor);
public static abstract class Visitor<K, V> {
boolean stop;
abstract boolean visit(K key, V value);
}
}
