java架构师进阶之独孤九剑：数据结构以及书籍推荐_java数据结构书籍

这是整个java架构师连载系列，分为9大步骤，我们现在还在第一个步骤：程序设计和开发->数据结构与算法。

“

如果说 Java 是自动档轿车，C 就是手动档吉普。数据结构呢？是变速箱的工作原理，

你完全可以不知道变速箱怎样工作，就把自动档的车子从 A 开到 B，而且未必就比懂得的人慢。写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。如果你对这两件事都不感兴趣也就罢了，数据结构懂得用就好。但若你此生在编程领域还有点更高的追求，数据结构是绕不开的课题。

不想学好基础的程序员很难进阶到架构师。

为什么要学习数据结构

学习数据结构，并不仅仅是学习其中现成的那些队列，堆栈，二叉树，图等经典结构， 也不仅仅是学习其中的那些快速排序、冒泡排序等算法。

更重要的是你要学习一种思想：如何把现实问题转化为计算机语言的表示。

当你用着java里面的容器类很爽的时候，你有没有想过，怎么ArrayList就像一个无限扩充的数组，也好像链表之类的。好用吗？好用，这就是数据结构的用处，只不过你在不知不觉中使用了。

校招会发现大公司考的就是这类的题目，刚开始不会考你java的线程，容器，多态什么的特性，考的就是你的基础，你的这些基础扎实，学其他不是问题。

用于现实世界的存储，我们使用的工具和建模。每种数据结构有自己的优点和缺点，想想如果Google的数据用的是数组的存储，我们还能方便地查询到所需要的数据吗。

而算法，在这么多的数据中如何做到最快的插入，查找，删除，也是在追求更快。

常用的数据结构

链表

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

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

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

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

时间复杂度：

索引：O（n）

查找：O（n）

插入：O（1）

删除：O（1）

栈

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

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

时间复杂度

索引：O（n）

查找：O（n）

插入：O（1）

删除：O（1）

队列

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

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

时间复杂度

索引：O（n）

查找：O（n）

插入：O（1）

删除：O（1）

树

树是无向、联通的无环图。

二叉树

二叉树是一个树形数据结构，每个节点最多可以有两个子节点，称为左子节点和右子节点。

满二叉树（Full Tree）：二叉树中的每个节点有 0 或者 2 个子节点。

完美二叉树（Perfect Binary）：二叉树中的每个节点有两个子节点，并且所有的叶子节点的深度是一样的。

完全二叉树：二叉树中除最后一层外其他各层的节点数均达到最大值，最后一层的节点都连续集中在最左边。

二叉查找树

二叉查找树（BST）是一种二叉树。其任何节点的值都大于等于左子树中的值，小于等于右子树中的值。

时间复杂度

索引：O（log（n））

查找：O（log（n））

插入：O（log（n））

删除：O（log（n））

数据结构和算法书籍推荐

1.算法导论

这本书深入浅出，全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣，并保持了数学严谨性。本书的设计目标全面，适用于多种用途。涵盖的内容有：算法在计算中的作用，概率分析和随机算法的介绍。书中专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。此书还介绍了对强连通子图算法正确性的证明，对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

2.大话数据结构

通篇以一种趣味方式来叙述，大量引用了各种各样的生活知识来类比，并充分运用图形语言来体现抽象内容，对数据结构所涉及到的一些经典算法做到逐行分析、多算法比较。与市场上的同类数据结构图书相比，本书内容趣味易读，算法讲解细致深刻，是一本非常适合自学的读物。

3.数据结构与算法

本书是国外数据结构与算法分析方面的经典教材，使用卓越的Java编程语言作为实现工具讨论了数据结构（组织大量数据的方法）和算法分析（对算法运行时间的估计）。 随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也不断增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。

---