数据结构基本知识

1、链表

链表是一种由节点（Node）组成的线性数据集合，每个节点通过指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。

单链表：每个节点仅指向下一个节点，最后一个节点指向空（null）。

双链表：每个节点有两个指针p，n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。

循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。

时间复杂度：

索引：O(n)

查找：O(n)

插入：O(1)

删除：O(1)

2、栈

栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。

后进先出的数据结构（Last In First Out, LIFO）

时间复杂度

索引：O(n)

查找：O(n)

插入：O(1)

删除：O(1)

3、队列

队列是一个元素集合，支持两种基本操作：enqueue 用于添加一个元素到队列，dequeue 用于删除队列中的一个元素。

先进先出的数据结构（First In First Out, FIFO）。

时间复杂度

索引：O(n)

查找：O(n)

插入：O(1)

删除：O(1)

4、树（无向的，联通的无环图）

4.1、二叉树

4.2、二叉查找树

       任何节点的值都大于等于左子树中的值，小于等于右子树的值。

      时间复杂度

索引：O(log(n))

查找：O(log(n))

插入：O(log(n))

删除：O(log(n))

4.3 、字典树、树状数组、线段树

5、堆

堆是一种基于树的满足某些特性的数据结构：整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中，父节点的键值永远大于等于所有子节点的键值，根节点的键值是最大的。最小堆中，父节点的键值永远小于等于所有子节点的键值，根节点的键值是最小的。

6、哈希

哈希常用于将任意长度的数据映射到固定长度的数据。若不同数据得到了相同的哈希值，则视为发生冲突。

解决办法：链地址法；开放地址法

7、图