1. 引子
1.1. 为什么要学习数据结构与算法?
有人说, 数据结构与算法, 计算机网络, 与操作系统都一样, 脱离日常开发, 除了面试这辈子可能都用不到呀!
有人说, 我是做业务开发的, 只要熟练 API, 熟练框架, 熟练各种中间件, 写的代码不也能 "飞" 起来吗?
于是问题来了: 为什么还要学习数据结构与算法呢?
# 理由一:
面试的时候, 千万不要被数据结构与算法拖了后腿
# 理由二:
你真的愿意做一辈子 CRUD Boy 吗
# 理由三:
不想写出开源框架, 中间件的工程师, 不是好厨子
1.2. 如何系统化学习数据结构与算法?
我想好了, 还是需要学习数据结构与算法. 但是我有两个困惑:
1. 如何着手学习呢?
2. 有哪些内容要学习呢?
学习方法推荐:
# 学习方法
1. 从基础开始, 系统化学习
2. 多动手, 每一种数据结构与算法, 都自己用代码实现出来
3. 思路更重要: 理解实现思想, 不要背代码
4. 与日常开发结合, 对应应用场景
学习内容推荐:
数据结构与算法内容比较多, 我们本着实用原则, 学习经典的, 常用的数据结构, 与常用算法
# 学习内容:
1. 数据结构的定义
2. 算法的定义
3. 复杂度分析
4. 常用数据结构
数组, 链表, 栈, 队列
散列表, 二叉树, 堆
跳表, 图
5. 常用算法
递归, 排序, 二分查找
搜索, 哈希, 贪心, 分治
动态规划, 字符串匹配
2. 考考你
在上一篇[数据结构与算法系列四(单链表)] 中, 详细给链表下了定义, 并且比较了链表与数组. 你还记得什么是链表吗? 链表就是通过指针, 将一组零散的内存串联起来使用, 每一个零散的内存块, 我们称为节点. 实际开发常用的链表有: 单链表, 双向链表, 循环链表.
这一篇我们看一下双向链表的实现.
# 考考你:
1. 你知道什么是双向链表吗?
2. 你知道 HashMap 的实现原理吗(底层用了哪些数据结构)?
双向链表:
3. 案例
3.1. 节点封装
简述:
单链表实现, 每个节点 Node 只需要封装数据: e, 与指向下一个节点的后继指针: next. 在双向链表中, 还需要增加指向前一个节点的前驱指针: prev.
- /**
- * 节点: Node<E>
- */
- class Node<E> {
- protected E e;
- protected Node<E> prev;
- protected Node<E> next;
- public E getE() {
- return e;
- }
- public void setE(E e) {
- this.e = e;
- }
- public Node<E> getPrev() {
- return prev;
- }
- public void setPrev(Node<E> prev) {
- this.prev = prev;
- }
- public Node<E> getNext() {
- return next;
- }
- public void setNext(Node<E> next) {
- this.next = next;
- }
- }
3.2. 完整代码
简述:
实现链表小技巧, 增加一个空头节点, 简化链表代码实现复杂度. 这样有空头节点的链表实现, 称为: 带头节点链表
- package com.anan.struct.linetable;
- /**
- * 双向链表实现思路:
- * 1. 空闲一个头节点, 即头节点不存储数据
- * 2. 这样有利于简化链表的实现
- */
- public class DoubleLinkedList<E> {
- // 链表大小
- private int size;
- public int getSize() {
- return size;
- }
- // 头节点
- private Node<E> head;
- // 尾节点
- private Node<E> tail;
- public DoubleLinkedList(){
- head = new Node<E>();
- tail = head;
- size ++;
- }
- /**
- * 添加元素到链表结尾
- */
- public boolean add(E e){
- // 创建节点
- Node<E> node = new Node<E>();
- node.setE(e);
- node.setPrev(tail);
- tail.next = node;
- tail = node;
- size ++;
- return true;
- }
- /**
- * 在指定位置插入链表元素
- */
- public boolean insertPos(int pos,E e){
- // 获取位置节点
- Node<E> posNode = get(pos);
- if(posNode == null){
- return false;
- }
- // 创建新节点
- Node<E> newNode = new Node<E>();
- newNode.setE(e);
- newNode.setPrev(posNode.prev);
- newNode.setNext(posNode);
- posNode.prev.setNext(newNode);
- posNode.setPrev(newNode);
- size ++;
- return true;
- }
- /**
- * 删除链表结尾元素
- */
- public boolean remove(){
- tail = tail.prev;
- tail.next = null;
- size --;
- return false;
- }
- /**
- * 在指定位置删除链表元素
- */
- public boolean delPos(int pos){
- // 获取指定位置节点
- Node<E> node = get(pos);
- if(node == null){
- return false;
- }
- // 删除
- node.prev.setNext(node.next);
- node.next.setPrev(node.prev);
- size --;
- return true;
- }
- /**
- * 获取节点
- */
- public Node<E> get(int pos){
- // 判断位置有效性
- if(pos <1 || pos> size){
- return null;
- }
- Node<E> node = head;
- for(int i = 1; i <= pos; i++){
- node = node.next;
- }
- return node;
- }
- /**
- * 获取节点数据
- */
- public E getValue(int pos){
- // 获取节点
- Node<E> node = get(pos);
- if(node == null){
- return null;
- }else{
- return node.e;
- }
- }
- /**
- * 节点: Node<E>
- */
- class Node<E> {
- protected E e;
- protected Node<E> prev;
- protected Node<E> next;
- public E getE() {
- return e;
- }
- public void setE(E e) {
- this.e = e;
- }
- public Node<E> getPrev() {
- return prev;
- }
- public void setPrev(Node<E> prev) {
- this.prev = prev;
- }
- public Node<E> getNext() {
- return next;
- }
- public void setNext(Node<E> next) {
- this.next = next;
- }
- }
- }
3.3. 测试代码
- package com.anan.struct.linetable;
- /**
- * 测试双向链表
- */
- public class DoubleLinkedListTest {
- public static void main(String[] args) {
- // 创建链表
- DoubleLinkedList<Integer> list = new DoubleLinkedList<Integer>();
- // 添加元素
- int size = 5;
- for (int i = 0; i <size; i++) {
- list.add(i);
- }
- // 1. 初始化链表, 打印链表元素
- System.out.println("1. 初始化链表, 打印链表元素 -----------------------------------------");
- list(list);
- // 2. 指定位置插入元素
- System.out.println("2. 指定位置插入元素 -----------------------------------------");
- list.insertPos(1,666);
- list(list);
- // 3. 删除链表结尾元素
- System.out.println("3. 删除链表结尾元素 -----------------------------------------");
- list.remove();
- list(list);
- // 删除指定位置元素
- System.out.println("5. 删除指定位置元素 -----------------------------------------");
- list.delPos(3);
- list(list);
- }
- public static void list(DoubleLinkedList<Integer> list){
- System.out.println("当前链表大小, size:" + list.getSize());
- for (int i = 1; i < list.getSize(); i++) {
- System.out.println(list.getValue(i));
- }
- }
- }
测试结果:
1. 初始化链表, 打印链表元素 -----------------------------------------
当前链表大小, size:6
0
1
2
3
4
2. 指定位置插入元素 -----------------------------------------
当前链表大小, size:7
- 666
- 0
- 1
- 2
- 3
- 4
3. 删除链表结尾元素 -----------------------------------------
当前链表大小, size:6
666
0
1
2
3
5. 删除指定位置元素 -----------------------------------------
当前链表大小, size:5
- 666
- 0
- 2
- 3
- Process finished with exit code 0
4. 讨论分享
# 考考你答案:
1. 你知道什么是双向链表吗?
1.1. 双向链表在单链表的基础上, 增加了前驱指针
1.2. 有了前驱指针, 便于链表从后往前遍历查找
1.3. 双向链表, 与单链表对比, 参考下图:
2. 你知道 HashMap 的实现原理吗(底层用了哪些数据结构)?
2.1.HashMap 是 key,value 对的映射表
2.2. 它的底层基础数据结构是: 数组
2.3. 利用数组支持下标随机访问特性, 实现快速访问, 时间复杂度: O(1)
2.4. 通过散列函数 hash(key), 计算原始 key, 与数组下标 (哈希值) 的对应关系
2.5. 不同的 key, 经过 hash(key), 哈希值有可能相同
2.6. 哈希值相同的情况, 称为: 哈希冲突
2.7. 发生哈希冲突的时候, 通过链表, 或者红黑树解决哈希冲突
2.8. 在 HashMap 中, 同时应用了: 数组, 链表
单链表与双向链表:
来源: https://www.cnblogs.com/itall/p/12371533.html