5分钟图解数据结构之链表！

什么是链表？

链表分类：单链表、双链表、双向链表、循环链表。

• 单链表：链表是物理存储单元上非连续的、非顺序的存储结构。链表节点有两部分：节点数据域和节点指针域（指向下一个节点）。

  

  // 单链表节点结构
  class LinkNode{
      constructor(val,next){
        this.value = val;
        this.next = next;// 指向后一个节点指针域
      }
  }
  

• 双链表：既可以从头遍历到尾，也可以从尾巴遍历到头。也就是既有向前连接的引用，也有一个向后连接的引用。双向链表的结构：节点的数据域和节点的指针域。

  

  // 双链表节点结构
  class LinkNode{
      constructor(val,prev,next){
        this.prev = prev;// 指向前一个节点指针域
        this.value = val;
        this.next = next;// 指向后一个节点指针域
      }
  }
  

• 以单链表为例子实现链表的增删查改：

• 初始化节点：创建一个虚拟头节点。

为什么需要添加size链表长度、链表头head、链表的尾巴tail？都是为了后面方便处理链表的长度边界情况的分析，以及对链表的尾部处理。

var MyLinkedList = function() {
   this.size = 0;
   this.tail = null;
   this.head = null;
};

• 获取节点：先创建一个虚拟空节点，从开头遍历链表获取当前节点，为什么传的是index索引，传索引为了后面while遍历链表时，index代表循环的次数，也就是遍历index次改变指针域，直到找到当前节点为止，通俗地，我们也可以把index当作链表索引。

MyLinkedList.prototype.getNode = function(index) {
      if(index<0||index>=this.size) return null;
   let curNode = new LinkNode(0, this.head);
   while(index-->=0){
       curNode = curNode.next;
   }
   return curNode;
};

• 添加节点：创建一个节点，从链表头或链表中或链表尾添加节点。

MyLinkedList.prototype.addAtHead = function(val) {
   const node = new LinkNode(val,this.head);
   this.head = node;
   this.size++;
   if(!this.tail){
       this.tail = node;
   }
};

MyLinkedList.prototype.addAtTail = function(val) {
   const node = new LinkNode(val,null);
   this.size++;
   if(this.tail){
       this.tail.next = node;
       this.tail = node;
       return;
   }
   this.head = node;// 当链表为空时
   this.tail = node;// 当链表为空时
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
  if(index>this.size) return;
  if(index<=0){
    this.addAtHead(val);
    return;
  }else if(index===this.size){
    this.addAtTail(val);
    return;
  }
  const node = this.getNode(index-1);
  node.next = new LinkNode(val,node.next);
  this.size++;
};

• 删除节点：删除链表头或链表中或链表尾节点。当删除链表头元素地时候，直接更新head地指针域指向。当删除链表尾或链表中的节点时，直接更新tail的前一个节点指针域指向。

MyLinkedList.prototype.deleteAtIndex = function(index) {
   if(index<0||index>=this.size) return;
   if(index===0){
       this.head = this.head.next;
       if(index===this.size-1){
           this.tail = this.head;
       }
       this.size--;
       return;
   }
   const preNode = this.getNode(index-1);;
   preNode.next = preNode.next.next;
   if(index===this.size-1){
     this.tail = preNode;
   }
   this.size--;
};

参考资料

「代码随想录」带你搞定链表！707. 设计链表：【链表基础题目】详解