js 双向链表 02

get实现 – 获取对应位置元素

思路和单链表一摸一样！

代码

// 7 get方法 -- 效率不高，可以采用平分，毕竟有一个尾结点！
DoublyLinkedList.prototype.get = function(position){
    
  if(position < 0 || position >= this.length) return null;
  let current = this.head;
  let index = 0;
  while(index++ < position){
    
    current = current.next;
  }
  return current.data;
}

这里平分的代码菜鸟就不写了，思路就是把position和length/2进行比较，大于就用tail，小于就用head！

indexOf实现 – 判断是否含有元素

这个也和单链表思路一摸一样！

代码

DoublyLinkedList.prototype.indexOf = function(data){
    
  let current = this.head;
  let index = 0;
  while(current){
    
    if(current.data === data){
    
      return index;
    }
    current = current.next;
    index++;
  }
  return -1;
}

update实现 – 更改某一位置的值

这里菜鸟使用的是平分的思路，上面get没用平分写出来的读者，可以借鉴一下这里！

代码

// 9 update方法
DoublyLinkedList.prototype.update = function(position,data){
    
  if(position < 0 || position >= this.length) return false;
  if(position < this.length/2){
    
    let current = this.head;
    let index = 0;
    while(index++ < position){
    
      current = current.next;
    }
    current.data = data;
  }else{
    
    let current2 = this.tail;
    // 注意：index等于length-1，因为length是长度，而下标是从0开始，所以index最大只能是length-1
    let index = this.length - 1;
    while(index-- > position){
    
      current2 = current2.prev;
    }
    current2.data = data;
  }
  return true;
}

removeAt实现 – 移除某位置的元素

这里情况有点多，eg：

1. 只有一个节点
2. 移除的是第二个节点
3. 移除的是最后一个节点
4. 移除中间节点

2、3之所以有，是因为要改变head、tail的指向！

菜鸟一开始自己写代码没有考虑到这么多情况，然后就是看视频的时候想到了，就用自己的思路加上视频的情况写了。

代码

// 11 removeAt1 视频方法
DoublyLinkedList.prototype.removeAt1 = function(position){
    
  if(position < 0 || position >= this.length) return false;
  // 判断是否只有一个节点
  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 - 1){
     // 判断删除的是否是最后一个节点
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    }else{
    
      // 平分思路
      if(position < this.length/2){
    
        let current = this.head;
        let index = 0;
        while(index++ < position - 1){
    
          current = current.next;
        }
        current.next.neaxt.prev = current;
        current.next = current.next.next;
      }else{
    
        let current = this.tail;
        let index = this.length - 1;
        while(index-- > position+1){
    
          current = current.prev;
        }
        current.prev.prev.next = current;
        current.prev =current.prev.prev;
      }
    }
  }

  this.length -= 1;
  return true;
}

菜鸟这里和视频思路不一样，保存的是要删除的节点的前一个或后一个，而不是删除的节点本身，所以返回不了值，但是感觉视频的更好（保存删除的节点），因为双向链表不像单向链表，需要保存两个节点信息，因为其既可以访问前节点也可以访问后节点！

视频代码

remove实现 – 移除某值

这里直接调用两个方法就行，菜鸟就不写了

其它方法

总结

其实不难发现，单向链表和双向链表的难点都在于 insert 和 removeAt 方法，只要搞明白这两个方法的一些特殊情况，其实写起来也不是特别困难了；双向链表的其它操作真的和单向链表没什么很大的区别，有的甚至因为有了tail指针而更加简单！