此笔记是本人学习数据结构的笔记，持续更新中

一、链表

1.双向链表

优点：对于链表中一个给定的结点，可以从两个方向进行操作。在单向链表中，只有获得结点的前驱结点的指针，才能删除该结点。在双向链表中，每个结点都有一个指向前驱结点的指针，可以直接后退到前驱结点。

缺点：需要更多的空间开销。结点的插入或删除更加费时（需要更多指针的操作)。

public class DLLNode{
    private DLLNode next;
    private DLLNode previous;
    public DLLNode(int data){
        this.data=data;
    }
    public void setData(int data){
        this.data=data;
    }
    public int getData(){
        return data;
    }
    public void setNext(DLLNode next){
        this.next=next;
    }
    public DLLNode getNext(){
        return this.next;
    }
    public void setPrevious(DLLNode previous){
        this.previous=previous;
    }
    public DLLNode getPrevious(){
        return this.previous;
    }
}

1)双向链表的插入操作

双向链表的插入操作分为以下3种情况：开头插入，末尾插入，中间插入

2)在开头插入

①将新结点的后继结点指向表头结点

②将新节点的前驱结点指向Null

③将表头的前驱结点更新为新结点

3)在末尾插入一个新结点

①将新节点的后继结点指向Null

②将新节点的前驱结点指向末尾结点

③更新末尾结点的后继结点使其指向新结点

4）在中间插入新结点

先两边后中间

①新结点的后继结点指向需要插入新节点的位置结点的后继结点，新节点的前驱结点执行位置结点

②位置结点的后继结点指向新节点，位置结点的后继结点指向新结点

时间复杂度为O(n),因为最差情况下，可能需要删除链表的表尾结点。

空间复杂度为O(1),仅用于创建一个临时变量。

5）双向链表的删除

删除操作分为3种情况：删除表头的结点，删除中间的结点，删除表尾的结点

6）删除表头结点

①创建一个临时结点，它与表头指向同一个结点

②修改表头结点，使其指向下一个结点，将表头结点的前驱结点更改为Null ,之后移除临时结点。

7）删除双向链表的最后一个结点

①遍历链表，在遍历时还要保存前驱结点的地址。

②改变表尾的前驱结点的后继指针为Null

8)删除双向链表中间的一个结点

①遍历链表，一旦找到，将前驱结点的next指针指向被删除结点的下一个结点。

②更改被删除结点的后继结点的前驱指针指向被删除结点的前驱结点。

③移除被删除的当前结点

时间复杂度为O(n),因为最差情况下，可能需要删除链表的表尾结点。

空间复杂度为O(1),仅用于创建一个临时变量。

2.循环链表

循环链表没有结束标志。

1）统计循环链表的结点个数

循环链表可以通过标记为表头的结点进行访问。

int CircularListData(CLLNode headNode){
    CLLNode CLLNode=headNode;  
    while(CLLNode!=null){
        System.out.print(CLLNode.getData()+"->");  
        CLLNode=CLLNode.getNext();
        if(CLLNode==headNode)break;  
    }
}

2）在循环链表的表尾插入结点

①创建一个新结点，初始化其next指针指向改结点本身

②更新新结点的next指针为表头结点。

③更新表头的前驱结点的next指针指向新结点

3）在循环链表的表头插入结点

在循环链表中的表头前插入新结点和在表尾插入新结点的唯一区别就是在插入新结点后还需要更新指针。

4)删除循环链表中的最后一个结点

①遍历循环链表，找到表尾结点及其前驱结点

②更新表尾的前驱结点的next指针使其指向表头结点

③移除表尾结点。

5）删除循环链表的第一个结点

①遍历循环链表找到表尾结点。表尾结点是将要删除的表头结点的前驱结点。

②修改表头指针的值，使其指向后继结点。移除临时结点。

3.一种存储高效的双向链表

在双向链表常规的实现中，需要一个指向后继结点的正向指针和一个指向前驱结点的反向指针。这表明双向链表的结点由数据，一个指向后继结点的指针和一个指向前驱结点的指针构成。

1）新的结点的定义

public class ListNode{
    private int data;
    private ListNode ptrdiff;
}

ptrdiff指针字段包含后继结点的地址与前驱结点的地址的差。指针的差通过异或运算来实现。

ptrdiff=后继结点的地址^前驱结点的地址

表头结点的ptrdiff等于NULL与表头结点的后继结点的地址的异或。类似地，类似地，表尾结点的ptrdiff等于表尾结点的前驱结点的地址与Null的异或。

4.松散链表

与数组相比，链表的最大优势在于，在任何位置插入元素的时间开销为O(1).然而，在链表中查找某个元素的时间开销则是O(n).松散链表为单向链表的简单表种。

松散链表中的每个结点存储多个元素（简称块）。而每一个块中的所有结点由循环链表连接在一起。

松散链表主要有两个优点，一个是时间方面的问题，另一是空间方面。

首先，如果每块中的元素个数适中(例如，最多一个缓存行的大小)，那么通过改善内存局限性，能够获得显著更优的缓存性能。

其次，因为在松散链表中链接的大小仅为O(n/m),其中n等于松散链表中的元素的个数，m等于一个块中能够存储的元素个数，所以这也将节省大量的空间。当每个元素的大小较小时，效果会更加明显。

二、栈

1.什么是栈？

栈是一种用于存储数据的简单数据结构。数据入栈的次序是栈的关键。在现实生活中栈可以形象的比如成一堆盘子。

• 定义：栈是一个有序的线性表，只能在表的一端（栈顶）执行插入和删除操作。最后插入的元素将第一个被删除。所以栈也称为后进先出或先进后出线性表。
• 改变栈的操作：入栈（push）表示插入元素，出栈（pop）表示删除元素。
• 下溢：对一个空栈执行出栈操作
• 溢出：对一个满栈执行入栈操作，下溢和溢出都是异常。

2.栈抽象数据类型

1）栈的主要操作

void push(int data) //将data数据插入栈
int pop() //删除并返回最后一个插入栈的元素

2）栈的辅助操作

int top() //返回最后一个插入栈的元素，但不删除
int size() //返回存储在栈中元素的个数
int isEmpty() //判断栈中是否有元素
int isStackFull() //判断栈中是否存满元素

3.异常

在执行操作时发生的错误称为异常。当操作不能执行时，会“抛出”异常。在栈抽象数据类型中，pop操作和top操作在栈空时是不能执行的。

4.应用

5.实现

1）基于简单数组的实现方法。

2）基于动态数组的实现方法。

3）基于链表的实现方法。

三、数组

一种线性的存储结构，对存储的结构只做查找和修改操作

1、优点

• 访问高效：利用下标访问元素，如果数组容量较大时，可以直接根据第一个元素的地址和下标，来计算出访问元素的地址。

2、缺点

• 插入低效，解决方法：如果不考虑数组的元素顺序，可以将K位置的元素放到最后，将插入的元素放到K位置。
• 删除低效，解决方法：在数组容量有剩余时，进行假删除，当容量不足时，进行真的删除操作。

3、复杂度震荡（动态数组中才会产生）

当我们的数组容量满的时候，再次添加一个元素，会触发扩容机制，然后再将这个元素删除，又会触发缩减容量的机制。缩减容量过程会消耗资源。

解决：size==capacity/4是，才将capacity减半。

四、队列

像栈一样，队列也是一种线性表，它的特性是先进先出，插入在一端，删除在另一端，就像排队一样，刚来的人入队要排在队尾，每次出队的都是队首的人。

1、特点

• 先进先出
• 队尾添加元素，队首删除元素

五、散列表

1、定义

散列表又叫哈希表或Hash表。

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

2、散列函数

本质为一个函数，我们把它定义为hash（key），key就是元素的键值，通过hash函数得到的值就是散列值。

散列函数可以自己设计，需要遵循一些规则。

• 得到的散列值是一个非负整数
• 两个相同的键，通过散列函数技术出的散列值也相同
• 两个不同的键，计算出的散列值不同

因为现实世界的key是无限的，散列值是经过一定的规则将key进行运算，然后得到的，冲突是无法避免的。

3、哈希冲突解决方法

①开放寻址法

一旦遇到哈希冲突，就重新探索一个空闲位置，然后插入。

a线性探测

当我们往散列表中插入数据时，经过散列函数发现位置已经被占用了，我们就从当前位置开始，依次往后查找，直到找到空闲位置为止。

比如一个散列表的大小为 10，一个数据经过散列函数之后，到了下标为 8 的位置，但是发现这个位置已经有数据了，那么就依次往后遍历，如果到了尾部，还是没有找到空闲位置，那么就再从头开始找，直到找到空闲位置。

b二次探索

二次探索，和线性探索原理一样，先行探索每次的步长为 1 ，探索的下标依次为 hash(key)+0，hash(key)+1，hash(key)+2…，二次探索每次的步长变为原来的二次方，所以每次探索的下边为 hash(key)+0，hash(key)+12，hash(key)+22。

c双重散列

原来我们使用一个散列函数，双重散列，我们使用多个散列函数，我们先用第一个散列函数，如果计算得到的位置已经被占用，就使用第二个散列函数，以此类推，直到找到空闲时的位置。

链表法

链表法是一种更为常用的解决散列冲突的方法，比开放寻址法更加简单。在散列表中每个下标位置对应一个链表，所有经过散列函数得到的散列值相同的元素，我们都放到对应下标位置的链表中。

插入元素时，经过散列函数得到散列值，然后插入到对应下标位置的链表中即可，时间复杂度为 O(1)。查找和删除同样的对对应位置的链表进行操作，对应的时间复杂度和链表的长度有关系，也就是 O(n)。

六、跳表

1、定义

跳表又叫跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-86GI41Lg-1626588706368)(…/…/.local/Image/image-20210714113550999.png)]

一张跳跃列表的示意图。每个带有箭头的框表示一个指针，而每行是一个稀疏子序列的链表；底部的编号框表示有序的数据列表。查找从顶部最稀疏的子序列向下进行，直至需要查找的元素在该层两个相邻的元素中间。

跳表相当于在链表的基础上，建立多层索引，来提高查找速度。

比如查找15，从第一级索引开始遍历，找到14，17，最后往下，一共遍历了7个结点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9EwS8s9f-1626588706370)(…/…/.local/Image/image-20210714114150209.png)]

如果从第二级索引开始找，一共遍历了6个结点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-orjrZnLD-1626588706372)(…/…/.local/Image/image-20210714114200191.png)]

七、树

1、基本概念

树状图是一种数据结构，它是由n个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一颗倒挂的树，也就是说它是根朝上的，而叶朝下的。

它具有以下的特点：每个特点有零个或多个子结点；没有父节点的结点称为根结点；每一个非根节点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

树结构是非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

2、树的种类

无序树

树的任意结点的子结点没有顺序关系

有序树

树的任意结点的子节点有顺序关系

二叉树

树的任意结点至多包含两颗子树。

二叉树的遍历是指但从二叉树的根节点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次，且紧被访问一次。

二叉树的访问次序可以分为四种：前序遍历 中序遍历 后序遍历 层次遍历

满二叉树

叶子结点都在同一层并且除叶子节点外的所有结点都有两个子结点。

完全二叉树

对于一颗二叉树，假设其深度为d（d>1)。除第d层外的所有结点构成满二叉树，且第d层所有结点从左向右连续地紧密排列， 这样的二叉树被称为完全二叉树；最下层的结点都集中在该层最左边的若干位置上。

完满二叉树、

除了叶子结点外，都有两个子结点

八、图

1、基本概念

有向图：每条边都有方向

• 有向完全图：在有向图中有n个顶点，将具有n（n-1）条边的有向图称为有向完全图。图中任意两个顶点都有两条边相连。

无向图：每条边都没有方向

• 无向完全图： 在无向图中有n个顶点，将具有n（n-1）/2条边的无向图称为无向完全图。图中任意两个顶点都有一条边相连。

连通

在无向图中，若从顶点V到顶点W有路径存在，则称V和W是连通的。

连通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

连通分量

无向图中的极大连通子图称为连通分量。

强连通

在有向图中，若从顶点V到顶点W和从顶点V之间都有路径，则称这个两个顶点是强连通的。

强连通图

若图中任何一对顶点都是强连通的，则称为此图为强连通图。

强连通分量

有向图中的极大连通子图称为有向图的强连通分量。

顶点的度

以该顶点为一个端点的边的数目。

顶点的入度

在有向图中，入度是以顶点V为终点的有向边的数目。

顶点的出度

在有向图中，出度是以顶点V为起点的有向边的数目。

有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

2、图的遍历

深度优先搜索

广度优先搜索

3、图的基本应用

九、堆

1、定义

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构，所以堆也叫做二叉堆。

2、特点

• 父节点的键值总是大于或等于任何一个子结点的键值。
• 每个结点的左子树和又子树都是一个二叉堆。
• 当父节点的键值总是大于或等于任何一个子结点的键值时为最大堆。当父节点的键值总是小于或等于任何一个子结点的键值时为最小堆。最大堆和最小堆都是。堆数据结构的重点。堆排序中使用特别的多。

十、字典树

字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串，所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的3个基本性质：

• 根节点不包含字符，除根结点外每个结点都只包含一个字符。
• 从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。
• 父节点的键值总是大于或等于任何一个子结点的键值。
• 每个结点的左子树和又子树都是一个二叉堆。
• 当父节点的键值总是大于或等于任何一个子结点的键值时为最大堆。当父节点的键值总是小于或等于任何一个子结点的键值时为最小堆。最大堆和最小堆都是。堆数据结构的重点。堆排序中使用特别的多。

十、字典树

字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串，所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的3个基本性质：

• 根节点不包含字符，除根结点外每个结点都只包含一个字符。
• 从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。