Java : Data-Structures

数据结构与算法

• 从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

• 从狭义上讲，是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。

复杂度分析

数组

• 实现一个支持动态扩容的数组
• 实现两个有序数组合并为一个有序数组

链表

• 单链表增删改查
• 单链表反转
• 两个有序的链表合并
• 删除链表倒数第 k 个结点
• 求链表的中间结点

栈

• 数组实现栈
• 链表实现栈

队列

• 数组实现队列
• 链表实现队列
• 数组实现循环队列

递归

排序

• 冒泡排序，插入排序，选择排序 ------ O(n^2)
• 归并排序，快速排序 ，堆排序 ------ O(nlogn)
• 桶排序，计数排序，基数排序 ------ O(n)

查找

哈希

二叉树

堆

• 堆排序

图

• 广度优先搜索(BFS)----最短路径
• 深度优先搜索(DFS)