数据结构与算法的关系算法和架构有什么区别( 二 )

文章插图
3.2 链表链表（linked list）是一种在物理上非连续、非顺序的数据结构。由若干节点（node）所组成。
单向链表的每一个节点又包含两部分。一部分是存放数据的变量data 。另一部分是指向下一个节点的指针next 。

文章插图
双向链表比单向链表稍微复杂一些。它的每一个节点除了拥有data和next指针。还拥有指向前置节点的prev指针。

文章插图
如果说数组在内存中的存放方式是顺序存放。那么链表在内存中的存放方式则是随机存放。

文章插图
3.3 栈和队列栈（stack）是一种线性数据结构。它就像一个上图所示的放入乒乓球的圆筒容器。栈中的元素只能先入后出（First In Last Out 。简称FILO）。最早进入的元素存放的位置叫作栈底（bottom）。最后进入的元素存放的位置叫作栈顶（top）。
栈这种数据结构既可以用数组来实现。也完全可以用链表来实现。

文章插图
队列（queue）是一种线性数据结构。它的特征和行驶车辆的单行隧道很差不多一样。不同于栈的先入后出。队列中的元素只能先入先出（First In First Out 。简称FIFO）。队列的出口端叫作队头（front）。队列的入口端叫作队尾（rear）。

文章插图
3.4 散列表散列表也叫作哈希表（hash table）。这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key 。就可以高效查找到它所匹配的Value 。期间复杂度接近于O(1) 。

文章插图
由于数组的长度是有限的。当插入的Entry越来越多时。不同的Key通过哈希函数获得的下标有可能是相同的。这种情况。就叫作哈希冲突。
解决哈希冲突的方法主要有两种。一种是开放寻址法。一种是链表法。
开放寻址法的原理很简单。当一个Key通过哈希函数获得对应的数组下标已经被占用时。咱们可以“另谋高就” 。寻找下一个空档位置。
这就是开放寻址法的基本思路。当然。在接触哈希冲突时。寻址方式有很多种。并不一定只是简单地寻找目前元素的后一个元素。这里只是举一个简单的示例而已。在Java中。ThreadLocal所使用的就是开放寻址法。
下一步。重点讲一下解决哈希冲突的另一种方法——链表法。这种方法被应用在了Java的集合类HashMap当中。
HashMap数组的每一个元素不仅是一个Entry对象。还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时。只要插入到对应的链表中即可。

文章插图
3.5 树树和图就是典型的非线性数据结构。我们第一个步讲一讲树的知识。
树（tree）是n（n≥0）个节点的有限集。当n=0时。称为空树。在任意一个非空树中。有如下特点。
有且仅有一个特定的称为根的节点。当n>1时。其余节点可分为m（m>0）个互不相交的有限集。每一个集合本身又是一个树。并称为根的子树。

文章插图
二叉树
二叉树（binary tree）是树的一种特殊形式。二叉。顾名思义。这种树的每个节点最多有2个儿童节点。注意。这里是最多有2个。也很有可能只有1个。或者没有儿童节点。

文章插图
二叉树节点的两个儿童节点。一个被称为左儿童（left chi ld）。一个被称为右儿童（right chi ld）。这两个儿童节点的顺序是固定的。就像人的左手就是左手。右手就是右手。不能够颠倒或混淆。此外。二叉树还有两种特殊形式。一个叫作满二叉树。另一个叫作完全二叉树。
二叉树存放结构
链式存放结构。数组。

文章插图

文章插图
3.6 小结什么是数组？数组是由有限个相同类型的变量所组成的有序集合。它的物理存放方式是顺序存放。访问方式是随机访问。利用下标查找数组元素的期间复杂度是O(1) 。中间插入、删除数组元素的期间复杂度是O(n) 。

数据结构与算法的关系 算法和架构有什么区别( 二 )

数据结构与算法的关系算法和架构有什么区别( 二 )