大纲图
双向链表
Algorithms_基础数据结构(02)_链表&链表的应用案例之单向链表中梳理了 单向链表的基本操作，接下来我们继续来看下双向链表吧。
双向链表的基本结构
单向链表只有一个方向，结点只有一个后继指针next指向后面的结点。
双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？
-----> B+Tree:Mysql索引 叶子节点 双向链表
双向链表的基本操作
头插
尾插
中间部位插入
删除头部
删除尾部
删除中间位置的数据
查找
通常，双向链表同单链表一样，都仅有一个头指针。所以双链表查找指定元素的实现同单链表类似，都是从表头依次遍历表中元素，直到找到对应的元素为止。
更新
更改双链表中指定结点数据域的操作那必须要先查找到该节点，因此是在查询的基础上完成的。------>即：通过遍历找到存储有该数据元素的结点，直接更改其数据域即可。
Code
/** * @author 小工匠 * @version v1.0 * @create 2020-01-03 06:08 * @motto show me the code ,change the word * @blog https://artisan.blog.csdn.net/ * @description **/ public class ArtisanDoubleLinkedList { private ArtisanNode head; // head节点 private ArtisanNode tail; // tail节点 为了方便直接获取tail节点，省去每一次都要遍历的操作 private int size; // 链表元素数量 /** * 双向链表初始化 */ public ArtisanDoubleLinkedList() { this.head = null; this.tail = null; } /** * 头插 * @param data */ public void add2Head(Object data) { ArtisanNode node = new ArtisanNode(data); // 新的Node if (this.head == null) { // 如果head节点为null, head和tail节点均为这个新的node节点 this.tail = node; } else {// 将原来的头节点的前驱节点指向node, 将新节点的后驱节点指向head this.head.pre = node; node.next = head; } this.head = node; // 将新的节点置为head节点 size++; } /** * 尾插 （低效） * * @param data */ public void add2Tail(Object data) {// 从头部遍历，找到最后的节点，然后加到尾部 ArtisanNode node = new ArtisanNode(data); // 要加入的节点 ArtisanNode currentNode = head; if (currentNode == null){ add2Head(data); } while(currentNode !=null){ if (currentNode.next == null){ // 说明找到了当前的tail节点 currentNode.next = node ;// 将当前tail节点的next指针指向新的tail节点 node.pre = currentNode; //新的tail节点的pre指向当前tail节点节点 this.tail = node; break; }else{ currentNode = currentNode.next; } } size++; } /** * 尾插 (利用tail 无需遍历 效率更高) * * @param data */ public void add2Tail2(Object data) {// 已经设置tail了，直接用即可，效率更高 ArtisanNode node = new ArtisanNode(data); // 要加入的节点 if (this.head == null){ add2Head(data); }else { tail.next = node; node.pre = tail; tail = node; } } /** * * @param postition * @param data */ public void add2Nth(int postition ,Object data) { ArtisanNode newNode = new ArtisanNode(data); // 新的Node ArtisanNode currentNode = head; if (postition == 0 ){ // 如果是0 ，添加到头节点 add2Head(data); }else { for (int i = 1; i < postition; i++) { // 找到要插入的位置的前面的节点 currentNode = currentNode.next; } // 与后继节点建立双层逻辑关系 newNode.next = currentNode.next; currentNode.next.pre = newNode; // 与前置节点建立双层逻辑关系 currentNode.next = newNode; newNode.pre = currentNode; } size++; } /** * 根据value 查找元素 * @param data * @return */ public ArtisanNode find(Object data){ // 从头遍历 ArtisanNode currentNode = head; while(currentNode != null){ if (data.equals(currentNode.data)){ printPreAndNextInfo(currentNode); break; }else{ currentNode = currentNode.next; } } return currentNode; } /** * 删除头部节点 */ public void deleteHead(){ this.head = this.head.next; // 将当前头节点的下一个节点置为头节点 this.head.pre = null; // 将前置节点置为null size--; } /** * 删除尾部节点 */ public void deleteTail(){ ArtisanNode currentNode = this.head; ArtisanNode previousNode = null; while (currentNode != null){ if (currentNode.next == null){ currentNode.pre = null;// 最后一个节点的pre置为置为null previousNode.next = null;// 前置节点的next指针置为null this.tail = previousNode; // 将当前节点的前一个节点置为tail节点 }else { // 如果当前节点的next指针指向不为空，则把下个节点置为当前节点，继续遍历 previousNode = currentNode;// 保存上一个节点的信息 currentNode = currentNode.next; } } } /** * 删除指定位置的节点 * @param position */ public ArtisanNode deleteNth(int position){ ArtisanNode currentNode = this.head; if (position == 0 ){ deleteHead(); }else { for (int i = 1 ; i < position ; i++){// 找到要删除节点的前一个节点 currentNode = currentNode.next; } currentNode.next.next.pre = currentNode; // 将 要删除节点的后一个节点的前驱节点 指向 当前节点（要删除的节点的前一个节点） currentNode.next = currentNode.next.next; // 将 要删除节点的前一个节点的next指针指向 要删除节点的后一个节点 } size--; return currentNode.next ; // 返回删除的节点 } /** * 获取tail节点 * @return tail节点 */ public ArtisanNode getTail(){ System.out.println("tail节点的值为:" + this.tail.data ); return this.tail; } /** * 获取head节点 * @return head节点 */ public ArtisanNode getHead(){ System.out.println("head节点的值为:" + this.head.data ); return this.head; } /** * 打印链表中的数据 */ public void print() { ArtisanNode currentNode = this.head;// 从head节点开始遍历 while (currentNode != null) { // 循环，节点不为空 输出当前节点的数据 System.out.print(currentNode.data + " -> "); currentNode = currentNode.next; // 将当前节点移动到下一个节点，循环直到为null } System.out.print("null"); System.out.println(); } /** * 打印前后节点信息 * @param currentNode */ private void printPreAndNextInfo(ArtisanNode currentNode) { System.out.println("当前节点:" + currentNode.data); if (currentNode.pre != null){ System.out.println("当前节点【" + currentNode.data + "】的前驱节点:" + currentNode.pre.data); }else{ System.out.println("当前节点【"+ currentNode.data + "】为head节点"); } if (currentNode.next != null){ System.out.println("当前节点【"+ currentNode.data + "】的后继节点:" + currentNode.next.data); }else{ System.out.println("当前节点【"+ currentNode.data + "】为tail节点"); } } public static void main(String[] args) { ArtisanDoubleLinkedList doubleLinkedList = new ArtisanDoubleLinkedList(); doubleLinkedList.add2Head("artisanData96"); doubleLinkedList.add2Head("artisanData97"); doubleLinkedList.add2Head("artisanData99"); doubleLinkedList.add2Head("artisanData98"); doubleLinkedList.getTail(); doubleLinkedList.add2Tail("artisanData100"); doubleLinkedList.getTail(); doubleLinkedList.print(); doubleLinkedList.getHead(); // doubleLinkedList.add2Nth(2,"addedDataByPos"); // doubleLinkedList.add2Tail2(1); // doubleLinkedList.add2Tail2(2); // doubleLinkedList.add2Tail2(3); // doubleLinkedList.add2Tail2(4); // doubleLinkedList.print(); // // System.out.println("tail:" + doubleLinkedList.tail.data); // // doubleLinkedList.find("artisanData98"); // doubleLinkedList.deleteHead(); // doubleLinkedList.print(); // doubleLinkedList.find("artisanData99"); // System.out.println("被删除节点：" + doubleLinkedList.deleteNth(1).data); // doubleLinkedList.print(); // doubleLinkedList.find("artisanData96"); } /** * 双向链表中的节点 */ class ArtisanNode { ArtisanNode pre; // 前驱结点 Object data; // 数据 ArtisanNode next;// 后继节点 public ArtisanNode(Object data) { this.data = data; } } }
总结
重要区别：
1.数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。
2.链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
3.数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它， 导致“内存不足（out ofmemory）”。如果声明的数组过小，则可能出现不够用的情况。注意下标越界的问题。
4.动态扩容：数组需再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，使用的时候也需要考虑占用内存的问题。
