文章 答疑

如何理解并掌握 Java 数据结构

Jack和大家一起来重温《Java数据结构》经典之作。

第一部分:Java数据结构

要理解Java数据结构,必须能清楚何为数据结构?

数据结构:

  1. Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。
  2. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。
  3. 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构。

一、Java数据结构之:线性数据结构

线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。

1:一维数组

在Java里面常用的util有:String [],int [],ArrayList,Vector,CopyOnWriteArrayList等。及可以同过一维数组[]自己实现不同逻辑结构的Util类。而ArrayList封装了一些[]的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的,方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。(PS:如果不懂出门右拐看另一篇chat)。

数组这种数据结构典型的操作方法,是根据下标进行操作的,所以insert的的时候可以根据下标插入到具体的某个位置,但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新,删除效率也比较低,而查询效率非常高,查询效率时间复杂度是1。

2: 线性表

线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的,链表的每一个节点都知道上一个节点、或者下一个节点是谁,通常用Node表示。常见的有顺序链表(LinkedList、Linked***),单项链表(里面只有Node类),双向链表(两个Node类),循环链表(多个Node类)等。

操作方法:插入效率比较高,插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了,如果实现的不好,需要整个链路找下去才能找到应该找的元素。所以常见的方法有:add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

常见的Uitil有:LinkedList,LinkedMap等,而这两个JDK底层也做了N多优化,可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

3: 栈Stack

栈,最主要的是要实现先进后出,后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈,pop()出栈。

java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。

4:队列

队列,队列是一种特殊的线性数据结构,队列只能允许在队头,队尾进行添加和查询等相关操作。队列又有单项有序队列,双向队列,阻塞队列等。

Queue这种数据结构注定了基本操作方法有:add(E e)加入队列,remove(),poll()等方法。

队列在Java语言环境中是使用频率相当高的数据结构,所有其实现的类也很多来满足不同场景。

queue

使用场景也非常多,如线程池,mq,连接池等。

5:串

串:也称字符串,是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。

KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。

二、Java数据结构之:非线性数据结构

非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash).

1:多维数组

一维数组前面咱也提到了,多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类,而java里面tree和图底层的native方法用了多维数组来储存。

2:集合

由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

Collection

3:树

树形结构,作者觉

2018年1月10日,周三晚上8点30分,曾经先后在驴妈妈、携程、要买车公司担任过 Java 高级工程师、架构师、开发主管、技术经理等职务,在电商公司工作期间,负责过 PC 站和后端服务的平台架构、实现和升级的张振华带来了主题为《如何理解并掌握 Java 数据结构》的交流。以下是主持人天怡整理的问答实录,记录了作者和读者间问答的精彩时刻。


内容提要:

  • 关于面试的几个问题出题面试候选人,在数据结构和算法这块,请问会出哪些题,着重哪些点?如果要准备面试,虽然短期内刷 leetcode 可以积累一些思路,但过些时间就模糊了,怎么在平时工作中训练,长期内都能掌握?工作中平时比较多的是写基本的 CURD 业务,关于数据结构的算法用的比较少,但是面试中又比较爱面试,怎么找到这个平衡?笔试或面试中图这类数据结构的一般考点是什么?面试的话是更重视算法和数据结构基础,还是相关业务的项目经验或者框架使用经验和框架原理?
  • 关于冒泡排序和选择排序,我曾经搜索过网络上很多文章,发现大部分都是错的,自己做文章筛选的成本很高,还可能被误导。因此能不能请给出更多的参考链接?
  • 能否请结合一个例子讲解一下工作中用数据结构解决的问题?
  • 请问有更详细的讲解 Java 数据结构和算法的资料或者书籍推荐吗?
  • 有关二叉平衡树的意义,可以稍微详细讲一下吗?
  • 工作中哪些地方会用到数据结构?
  • 完全二叉树是否可以理解为 D-1 层最右子树没有右叶子的二叉树?
  • 关于树的知识记得有前序、中序、后序遍历算法。文中没有提及,可以讲一下吗?以及这些遍历在实际生产中如何使用?
  • 请问老师 B+ 树和 B- 树怎么理解?

问:关于面试的几个问题出题面试候选人,在数据结构和算法这块,请问会出哪些题,着重哪些点?如果要准备面试,虽然短期内刷 leetcode 可以积累一些思路,但过些时间就模糊了,怎么在平时工作中训练,长期内都能掌握?工作中平时比较多的是写基本的 CURD 业务,关于数据结构的算法用的比较少,但是面试中又比较爱面试,怎么找到这个平衡?笔试或面试中图这类数据结构的一般考点是什么?面试的话是更重视算法和数据结构基础,还是相关业务的项目经验或者框架使用经验和框架原理?

答:我把问题中的5个问题分成两类。一类是面试题大概有些哪些以及如何准备面试?

  1. 首先我建议准备面试的这些人,把文章通读一遍,

收藏 收藏
分享
购买文章 ¥9.99