数据结构——双向链表（双向连接的图解、双向链表的创建、操作双向链表）

目录

一、双向链表

二、双向连接的图解:

三、双向链表的创建

四、操作双向链表

一、双向链表

- 单向链表:

  - 只能从头遍历到尾或者从尾遍历到头(一般从头到尾)
  - 也就是链表相连的过程是单向的. 实现的原理是上一个链表中有一个指向下一个的引用.
  - 单向链表有一个比较明显的缺点: 
    - 我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的. 但是, 在实际开发中, 经常会遇到需要回到上一个节点的情况
    - 举个例子: 假设一个文本编辑用链表来存储文本. 每一行用一个String对象存储在链表的一个节点中. 当编辑器用户向下移动光标时, 链表直接操作到下一个节点即可. 但是当用于将光标向上移动呢? 这个时候为了回到上一个节点, 我们可能需要从first开始, 依次走到想要的节点上.

- 双向链表

  - 既可以从头遍历到尾, 又可以从尾遍历到头
  - 也就是链表相连的过程是双向的. 那么它的实现原理, 你能猜到吗?
  - 一个节点既有向前连接的引用, 也有一个向后连接的引用.
  - 双向链表可以有效的解决单向链表中提到的问题.
  - 双向链表有什么缺点呢? 
    - 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 也就是实现起来要困难一些
    - 并且相当于单向链表, 必然占用内存空间更大一些.
    - 但是这些缺点和我们使用起来的方便程度相比, 是微不足道的.

二、双向连接的图解:

三、双向链表的创建

// 创建双向链表的构造函数
function DoublyLinkedList() {
    // 创建节点构造函数
    function Node(element) {
        this.element = element
        this.next = null
        this.prev = null // 新添加的
    }
 
    // 定义属性
    this.length = 0
    this.head = null
    this.tail = null // 新添加的
 
    // 定义相关操作方法
}

- 基本思路和单向链表比较相似, 都是创建节点结构函数以及定义一些属性和方法.
- 只是Node中添加了一个this.prev属性, 该属性用于指向上一个节点.
- 另外属性中添加了一个this.tail属性, 该属性指向末尾的节点

四、操作双向链表

1、尾部追加数据

2、正向反向遍历

3、任意位置插入

4、位置移除数据

5、获取元素位置

6、根据元素删除

7、判断是否为空

 8、获取链表长度

9、获取第一个元素

10、获取最后一个元素

   class Dnode {
            constructor(data) {
                this.prev = null;
                this.data = data;
                this.next = null;
            }
        }
        class DoubleLinkList {
            constructor() {
                this.head = null;
                this.tail = null;
                this.len = 0
            }
            // 1.尾部添加节点
            append(ele) {
                let newnode = new Dnode(ele);
                // console.log(newnode);
                if (this.len == 0) { //空链表
                    this.head = newnode;
                    this.tail = newnode;
                } else {
                    newnode.prev = this.tail; //新节点.prev = 尾节点
                    this.tail.next = newnode; //尾节点.next指向新节点
                    this.tail = newnode; //将尾节点指向新节点
                }
                this.len++;
            }
            // 2.向指定位置插入元素
            insert(position, ele) {
                // 位置是否合法
                if (position < 0 || position > this.len || !Number.isInteger(position)) {
                    return false
                }
                let newnode = new Dnode(ele);
                if (position == 0) {
                    if (this.len == 0) { //空链表
                        this.head = newnode;
                        this.tail = newnode;
                    } else {
                        newnode.next = this.head; //新节点.next指向头节点
                        this.head.prev = newnode; //头节点.prev指向新节点
                        this.head = newnode; //头节点指向新节点
                    }
                    this.len++
                } else if (position == this.len) {
                    this.append(ele)
                } else {
                    let current = this.head,
                        index = 0;
                    while (index < position - 1) {
                        current = current.next;
                        index++;
                    }
                    // 1.将新节点练上去
                    newnode.prev = current;
                    newnode.next = current.next;
                    // 2.
                    current.next = newnode;
                    newnode.next.prev = newnode;
                    this.len++;
                }
            }
            // 3.移除指定位置的元素
            removeAt(position) {
                // 位置是否合法
                if (position < 0 || position > this.len - 1 || !Number.isInteger(position)) {
                    return false
                }
                if (this.len == 0) { //空链表
                    return
                } else {
                    if (position == 0) {
                        if (this.len == 1) {
                            this.head = null;
                            this.tail = null;
                        } else {
                            this.head = this.head.next;
                            this.head.prev = null;
                        }
                    } else if (position == this.len - 1) {
                        this.tail = this.tail.prev;
                        this.tail.next = null;
                    } else {
                        let current = this.head,
                            index = 0;
                        while (index < position - 1) {
                            current = current.next;
                            index++
                        }
                        current.next = current.next.next;
                        current.next.prev = current
                    }
                    this.len--
                }
            }
            // 4.查找指定元素的位置
            indexOf(ele) {
                let current = this.head,
                    index = 0;
                while (index < this.len) {
                    if (current.data == ele) {
                        return index
                    } else {
                        current = current.next;
                        index++;
                    }
                }
                return -1
            }
            // 5.移除指定元素
            remove(ele) {
                let index = this.indexOf(ele)
                this.removeAt(index)
            }
            // 6.正向遍历
            toAfterString() {
                let current = this.head,
                    index = 0,
                    res = "";
                while (index < this.len) {
                    res += "-" + current.data;
                    current = current.next;
                    index++;
                }
                return res.slice(1)
            }
            // 7.反向遍历
            toBeforeString() {
                let current = this.tail,
                    index = this.len - 1,
                    res = "";
                while (index >= 0) {
                    res += "-" + current.data;
                    current = current.prev;
                    index--;
                }
                return res.slice(1)
            }
        }
        let dlist = new DoubleLinkList();
        for (let i = 0; i < 9; i++) {
            dlist.append(i)
        }
        dlist.remove(6)
        console.log(dlist.toAfterString());
        console.log(dlist.toBeforeString());