【数据结构（二）】一一一一双向链表

大家好，欢迎来到IT知识分享网。

【数据结构之链表（二）】一一一一双向链表

1、🌓前言

首先抛出几个问题，这也是本文双向链表的思路脉络：

1. 1️⃣ 为什么有了单向链表还要使用双向链表呢？
2. 2️⃣ 双向链表对比单向链表的优缺点如何呢？
3. 3️⃣ 双向链表是怎么实现的呢?

2、🍊 为什么有了单向链表还要使用双向链表呢？

​ “假设一个文本编辑器用链表来存储文本。屏幕上的每一行文字作为一个String对象存储在链结点中。当编辑器用户乡下移动光标时，程序移到下一个链结点操纵或显示新的一行。但是如果用户向上移动光标会发生什么呢？在普通的链表中，需要current变量（或起同等作用的其它变量）调回到表头，再一步一步地向后走到新的当前链结点，这样效率非常低。”

单向链表在前文讲过：【数据结构链表（一）】一一一一单向链表

单向链表：每一次向上移动都会重新通过current变量去从头调用，是不是效率很低？那么为什么我们不直接在链表中使用包含preview的升级版链表结构呢？

问题就可以解决了：

​ 双向链表

首先定义一下他的内部节点信息

这里相比于原来的单向节点多了一个 pre指向前一个节点，

就如同 before.node.next 相互指向 after.node.previous，如下图

代码如下：

/ * 内部构造节点类 * * @param <T> */ private class Node<T> { 
     private T data; private Node next; // 只想下一个节点的引用 private Node pre; // 指向之前一个节点的引用 public Node(T data) { 
     this.data = data; } } 

理清了上述线的关系，双向链表的构造就会让你游刃有余了。

2、🍌 双向链表对比单向链表的优缺点如何呢？

一、指代不同

1、双向链表：也叫双链表，是链表的一种，每个数据结点中都有两个指针（prev,next），分别指向直接后继和直接前驱。

2、单向链表：是链表的一种，其特点是链表的链接方向是单向(next)的，对链表的访问要通过顺序读取从头部开始。

二、优点不同

1、双向链表：从双向链表中的任意一个结点开始，都可以很方便地访问前驱结点和后继结点。

2、单向链表：单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小，结点的访问方便，可以通过循环或者递归的方法访问到任意数据。

三、缺点不同

1、双向链表：增加删除节点复杂，需要多分配一个指针存储空间。

2、单向链表：结点的删除非常方便，不需要像线性结构那样移动剩下的数据，但是平均的访问效率低于线性表。

3、🍅 双向链表是怎么实现的呢?

话不多说直接看代码了兄弟姐妹们

package com.dataStructure; / * @author xiaoCoder * @version 1.0 * @description: TODO 双向链表 * @date 2021/7/30 11:16 */ public class DoublyLinkedList<T> { 
    public static void main(String[] args) { 
    DoublyLinkedList<Object> doublyLinkedList = new DoublyLinkedList<>(); System.out.println("--------Add node to DoublyLinkedList------------"); doublyLinkedList.add("111"); doublyLinkedList.add("222"); doublyLinkedList.add("333"); doublyLinkedList.add("444"); doublyLinkedList.printList(); System.out.println("--------Delete a node as \"222\" data from this DoublyLinkedList------------"); doublyLinkedList.remove("222"); doublyLinkedList.printList(); System.out.println("--------Add a node as \"333After\" after the node as \"333\"------------"); doublyLinkedList.addAfter("333", "333After"); doublyLinkedList.printList(); System.out.println("--------Add a node as \"111Before\" before the node as \"111\" ------------"); doublyLinkedList.addBefore("111", "111Before"); doublyLinkedList.printList(); } / * 内部构造节点类 * * @param <T> */ private class Node<T> { 
    private T data; private Node next; // 只想下一个节点的引用 private Node pre; // 指向之前一个节点的引用 public Node(T data) { 
    this.data = data; } } private Node<T> head; // 模拟头节点 private Node<T> last; // 模拟尾部节点 private Node<T> other; // 暂定一个临时节点，用作指针节点 private int count; // 节点长度 / * Whether the linked list is empty * * @return */ public boolean isEmpty() { 
    return count == 0; } / * Ordinary add, add to the end of the linked list * * @param data */ public void add(T data) { 
    if (isEmpty()) { 
   // 链表为空创建一个新节点 head = new Node<>(data); last = head; } else { 
    other = new Node<>(data); other.pre = last; last.next = other; last = other; } count++; } / * delete the specified data * * @param data */ public void remove(T data) { 
    other = head; while (other != null) { 
    if (other.data.equals(data)) { 
    other.pre.next = other.next; count--; } other = other.next; } } / * test print data */ public void printList() { 
    other = head; for (int i = 0; i < count; i++) { 
    System.out.print(other.data + " "); other = other.next; } System.out.println("\n"); } / * Add node after selected element * * @param data * @param insertData */ public void addAfter(T data, T insertData) { 
    other = head; // 找到元素的位置 while (other != null) { 
    if (other.data.equals(data)) { 
    Node<T> t = new Node<>(insertData); t.pre = other; t.next = other.next; other.next = t; if (t.next == null) { 
    last = null; } count++; } other = other.next; } } / * Add node before selected element; * * @param data * @param insertData */ public void addBefore(T data, T insertData) { 
    other = head; while (other != null) { 
    // 找到元素的位置 if (other.data.equals(data)) { 
    Node<T> t = new Node<>(insertData); t.next = other; t.pre = other.pre; other.pre = t; if (t.pre == null) { 
    // 在头节点之前插入 head = t; } count++; } other = other.next; } } } re; other.pre = t; if (t.pre == null) { 
    // 在头节点之前插入 head = t; } count++; } other = other.next; } } }