数据结构与算法系列五（双向链表）
有人说，数据结构与算法，计算机网络，与操作系统都一样，脱离日常开发，除了面试这辈子可能都用不到呀！
有人说，我是做业务开发的，只要熟练API，熟练框架，熟练各种中间件，写的代码不也能“飞”起来吗？
于是问题来了：为什么还要学习数据结构与算法呢？
#理由一：
面试的时候，千万不要被数据结构与算法拖了后腿
#理由二：
你真的愿意做一辈子CRUD Boy吗
#理由三：
不想写出开源框架，中间件的工程师，不是好厨子
我想好了，还是需要学习数据结构与算法。但是我有两个困惑：
1.如何着手学习呢？
2.有哪些内容要学习呢？
学习方法推荐：
#学习方法
1.从基础开始，系统化学习
2.多动手，每一种数据结构与算法，都自己用代码实现出来
3.思路更重要：理解实现思想，不要背代码
4.与日常开发结合，对应应用场景
学习内容推荐：
数据结构与算法内容比较多，我们本着实用原则，学习经典的、常用的数据结构、与常用算法
#学习内容：
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
数组、链表、栈、队列
散列表、二叉树、堆
跳表、图
5.常用算法
递归、排序、二分查找
搜索、哈希、贪心、分治
动态规划、字符串匹配
在上一篇【数据结构与算法系列四(单链表)】中，详细给链表下了定义，并且比较了链表与数组。你还记得什么是链表吗？链表就是通过指针，将一组零散的内存串联起来使用，每一个零散的内存块，我们称为节点。实际开发常用的链表有：单链表、双向链表、循环链表。
这一篇我们看一下双向链表的实现。
#考考你：
1.你知道什么是双向链表吗？
2.你知道HashMap的实现原理吗（底层用了哪些数据结构）？
双向链表：
简述：
单链表实现，每个节点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; } }
简述：
实现链表小技巧，增加一个空头节点，简化链表代码实现复杂度。这样有空头节点的链表实现，称为：带头节点链表
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; } } }
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
#考考你答案：
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中，同时应用了：数组、链表
单链表与双向链表：
版权声明：本文为itall原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。