• 欢迎访问 优知学院 请加入我们的架构交流分享群优知学院-架构师进阶
  • 坚持原创分享BAT面试+架构+CTO进阶干货!

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

Java 优知学院陈睿 1年前 (2017-11-30) 861次浏览 0个评论 扫描二维码

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

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

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

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

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

为什么要学习数据结构

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

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

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

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

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

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

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

常用的数据结构

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

链表

链表是一种由节点(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.算法导论

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

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

2.大话数据结构

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

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

3.数据结构与算法

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

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


本文标题:java架构师进阶之独孤九剑:数据结构以及书籍推荐
转载请保留页面地址:http://youzhixueyuan.com/java-programmers-data-structure-in-the-algorithm.html
喜欢 (4)
[mike.r.chen@163.com]
分享 (0)
优知学院陈睿
关于作者:
优知学院创始人,13年互联网从业经验,资深架构设计经验,曾就职于淘宝、盛大、百度、携程,历程高级研发工程师、架构师、研发经理、事业部CTO。
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址