跳到主要内容

双向链表

设计实现双向链表: 双向链表中的节点应该具有两个属性: val 、 next 和 prev 。val 是当前节点的值, next 是指向下一个节点的指针/引用, prev 以指示链表中的上一个节点。链表功能如下:

  • get(index): 获取链表中第 index 个节点的值。如果索引无效，则返回 -1

  • addAtHead(val): 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点

  • addAtTail(val): 将值为 val 的节点追加到链表的最后一个元素

  • addAtIndex(index,val): 在链表中的第 index 个节点之前添加值为 val 的节点 如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点

  • deleteAtIndex(index): 如果索引 index 有效，则删除链表中的第 index 个节点

实现要点​

双链表 通常采用哨兵节点用作伪头、伪尾等,伪头、伪尾通常不保存任何数据

小贴士

在双向链表的实现中，使用一个伪头部dummy head和伪尾部dummy tail标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

基本操作​

操作一、构建双链表节本结构​

  • head 哨兵伪头节点
  • tail 哨兵伪尾节点
  • length 记录链表长度

注意: 构建链表时，设置伪头节点后删除第一个节点和删除其他节点相同，不用分情况讨论；如果没有伪头节点，那么删除节点时需要讨论是否为头节点。设立伪尾节点同理，而且有利于更快的查找节点。

constructor(){
    this.head=new Node(0);
    this.tail=new Node(0);
    this.head.next=this.tail;
    this.tail.prev=this.head;
    this.length=0;
}

操作二、在链表的第一个元素之前添加一个值为 val 的节点​

addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

addAtHead(val){
    let newNode=new Node(val);
    newNode.next=this.head.next;
    this.head.next.prev=newNode;
    this.head.next=newNode;
    newNode.prev=this.head;
    this.length++;
}

操作三、将值为 val 的节点追加到链表的最后一个元素​

addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

addAtTail(val){
    let newNode=new Node(val);
    this.tail.prev.next=newNode;
    newNode.prev=this.tail.prev;
    newNode.next=this.tail;
    this.tail.prev=newNode;
    this.length++;
}

操作四、在链表中的第 index 个节点之前添加值为 val 的节点​

addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

addAtIndex(index,val){
    if(index>this.length){
        return 
    }
    if(index<0){
        index=0;
    }
    let current=this.getNode(index);
    let newNode=new Node(val);
    current.prev.next=newNode;
    newNode.prev=current.prev;
    newNode.next=current;
    current.prev=newNode;
    this.length++;
}

操作五、获取链表中第 index 个节点​

get(index)：获取链表中第 index 个节点。如果索引无效，则返回 null

getNode(index){
    let middle=Math.floor((this.length-1)/2);
    let current;
    if(index<middle){
        current=this.head;
        for(let i=0;i<=index;i++){
            current=current.next;
        }
    }else{
        current=this.tail;
        for(let i=0;i<=this.length-index-1;i++){
            current=current.prev;
        }
    }
    return current
}

操作六、获取链表中第 index 个节点值​

get(index)：获取链表中第 index 个节点的节点值。如果索引无效，则返回 -1

get(index){
    if(index<0||index>=this.length){
        return -1
    }
    let current=this.getNode(index);
    return current.val;
}

操作七、删除链表中的第 index 个节点​

deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点

deleteAtIndex(index){
    if(index<0||index>=this.length){
        return 
    }
    let current=this.getNode(index);
    current.prev.next=current.next;
    current.next.prev=current.prev;
    this.length--
}

操作八、获取链表中 val 值为 x 的节点​

getByVal(val) {
    const current = this.getNodeByVal(val);
    return current;
}

操作九、获取链表中 val 值为 x 的前一个节点​

getNodeByVal(val) {
    let current = this.head;
    while (current) {
        if (current.val === val) {
            return current;
        }
        current = current.next;
    }
}

完整代码​

class Node {
  val;
  next;
  prev;
  constructor(val) {
    this.val = val;
  }
}
class MyLinkedList {
  constructor() {
    this.head = new Node(0);
    this.tail = new Node(0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.length = 0;
  }
  addAtHead(val) {
    let newNode = new Node(val);
    newNode.next = this.head.next;
    this.head.next.prev = newNode;
    this.head.next = newNode;
    newNode.prev = this.head;
    this.length++;
  }
  addAtTail(val) {
    let newNode = new Node(val);
    this.tail.prev.next = newNode;
    newNode.prev = this.tail.prev;
    newNode.next = this.tail;
    this.tail.prev = newNode;
    this.length++;
  }
  addAtIndex(index, val) {
    if (index > this.length) {
      return;
    }
    if (index < 0) {
      index = 0;
    }
    let current = this.getNode(index);
    let newNode = new Node(val);
    current.prev.next = newNode;
    newNode.prev = current.prev;
    newNode.next = current;
    current.prev = newNode;
    this.length++;
  }
  get(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    let current = this.getNode(index);
    return current.val;
  }
  getNode(index) {
    let middle = Math.floor((this.length - 1) / 2);
    let current;
    if (index < middle) {
      current = this.head;
      for (let i = 0; i <= index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = 0; i <= this.length - index - 1; i++) {
        current = current.prev;
      }
    }
    return current;
  }
  getByVal(val) {
    const current = this.getNodeByVal(val);
    return current;
  }
  getNodeByVal(val) {
    let current = this.head;
    while (current) {
      if (current.val === val) {
        return current;
      }
      current = current.next;
    }
  }
  deleteAtIndex(index) {
    if (index < 0 || index >= this.length) {
      return;
    }
    let current = this.getNode(index);
    current.prev.next = current.next;
    current.next.prev = current.prev;
    this.length--;
  }
  show() {
    let current = this.head.next;
    let result = [];
    while (current != this.tail) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }
}