双向链表的常用操作（非常详细）

1.双向链表
数据结构中常见的操作如下：
// 1.append(element)
// 2.inset(position,element)
// 3.get(position)
// 4.indexOf(element)
// 5.update(position)
// 6.removeAt(position)
// 7.remove(element)
// 8.isEmpty()
// 9.size()
// 10.toString()
// 11.forwardString()
// 12.backwordString()

① 首先应该建立节点

class Node{
  constructor(data){
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

② 然后建立链表函数

class doubleLinkList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
// 插入各种具体的方法...........................................
}

③ 插入的12个方法如下：
1.append(element) （尾插法）

append(data){
    var newNode = new Node(data);
    // 判断是否是第一个节点
    if (this.length===0){
      this.head = newNode;
      this.tail = newNode;
    }else {
      var current = this.head;
      // 寻找最后的节点
      while (current.next){
        current = current.next
      }
      current.next = newNode;
      newNode.prev = current;
      this.tail = newNode;
    }
    // 最后不要忘记长度加一
    this.length += 1;
  }

2.toString 将链表转化成字符串方法
3.forwardString():返回正向遍历的节点字符串形式
4.backwordString():返回反向遍历的节点字符串形式

// 2.toString 将链表转化成字符串方法
  toString(){
    return this.backwordString()
  }

// 3.forwardString():返回正向遍历的节点字符串形式
  forwardString(){
    // 从后往前遍历
    var current = this.tail;
    var resultString = "";
    while (current){
      resultString += current.data + "";
      current = current.prev;
    }
    return resultString;

  }

// 4.backwordString():返回反向遍历的节点字符串形式
  backwordString(){
    // 1.定义遍历
    var current = this.head;
    var resultString = "";
    // 2.依次向后遍历，获得每一个点
    while (current){
      resultString += current.data + "";
      current = current.next;
    }
    return resultString;
  }

5.insert任意位置插入
分为三种情况：
1.开头插入
2.尾插入
3.中间插入

insert(data,position){
    if (position <0 || position > this.length)return false
    var newNode = new Node(data)
// 1.原来的列表是否为空
    if (this.length == 0){
      this.head = newNode;
      this.tail = newNode;
    }else {
// 2.当在第一个位置
      if (position === 0){
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
// 3. 当在最后的位置
      }else if (position == this.length){
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
// 4. 当在中间的位置
      }else {
        var current = this.head;
        var index = 0;
        while (index++ < position){
          current = current.next
        }
// 5. 修改指针
        newNode.next = current;
        newNode.prev = current.prev;
        current.prev.next = newNode;
        current.prev = newNode;
      }
    }
    this.length += 1;
    return true;
  }

6. get 方法

get(position){
    if (position < 0 ||position >= this.length)return null
    if (this.length / 2 > position){
      var current = this.head;
      var index = 0;
      while (index++ < position){
        current = current.next;
      }
      return current.data;

    }else {
      var current = this.tail;
      var index = this.length - 1;
      while (index-- > position){
        current = current.prev;
      }
      return current.data;
    }
  }

7.indexOf() 正反方向一起查，加快速度

indexOf(data){
    var current1 = this.head;
    var current2 = this.tail;
    var index = 0;
    var index2 = this.length;
    while (current1 && current2){
      if (current1.data == data){
        return index
      }
      if (current2.data == data){
        return index2
      }
      current1 = current1.next;
      current2 = current2.prev;
      index += 1;
      index2 -= 1;
    }
    return false;
  }

8.update方法 , 也可以分情况前后查找

  update(newdata,position){
    if (position < 0 || position >= this.length){return false}
    var current = this.head
    var index = 0
    while (index++ < position){
      current = current.next
    }
    current.data = newdata;
    return true;
  }

9.removeAt方法

  removeAt(position){
    // 1.越界判断
    if (position < 0 || position > this.length) return false
    var current = this.head;
    if (this.length == 1){
      this.head = null;
      this.tail = null;
    }else {
      if (position == 0){
        this.head.next.prev = null;
        this.head = this.head.next;
      }else if (position == this.length){
        this.tail.prev.next = null;
        this.tail = this.tail.prev;
      }else {
        var index = 0;
        while (index++ < position){
          current = current.next;
        }
        current.prev.next =  current.next;
        current.prev.next.prev = current.prev;
      }
    }
    this.length -= 1;
    return current.data;
  }

10.remove方法

remove(data){
    var index = this.indexOf(data);
    return this.removeAt(index);
  }

12.isEmpty方法

isEmpty(){
    return this.length == 0
  }

13.size方法

size(){
    return this.length
  }

打印代码 - 放在链表函数中

// 打印出链表
  printList(){
    const nodes = []
    let current = this.head;
    while (current){
      nodes.push(current.data);
      current = current.next;
    }
    return nodes.join('-->')
  }

④ 测试代码

// 测试代码
// 测试代码
var list = new doubleLinkList();
// 1.测试加入
list.append('aaa');
list.append('bbb');
list.append('ccc');
list.append('ddd');
list.append('eee');
list.append('fff');

list.insert('ggg',6);
console.log("插入'ggg'后 打印链表 ",list.printList());

// 3.测试正反方向分别打印转换的字符串
console.log("正序",list.backwordString());
console.log("正序",list.forwardString());

// 4.获得指定位置的元素
console.log("获得位置是 4 的元素  ",list.get(4));

console.log(" ccc 的位置是 ",list.indexOf('ccc'));

list.update('jojo',2)
console.log("更新位置为 2 的元素 ",list.printList());

list.removeAt(2)
console.log("删除位置为 2 的元素 ",list.printList());

list.remove('ggg');
console.log("移除'ggg' ",list.printList());

console.log("判断是否为空",list.isEmpty());
console.log("判断大小",list.size());

image.png