[数据结构学习笔记4] 链表

链表（Linked Lists）

和数组类似，链表也是用来存放一组数据。和数组不一样的是，链表存储不需要连续的内存位置，一个链表由很多节点组成，节点与节点间通过一个next 指针关联。

图示：

链表操作：

查找一个值：

通过链表的next 指针一直往下跳直到：

1. 找到了想要的值；

2. 到达最后一个节点了。

添加节点：

1. 添加在末尾：将末尾节点的next指针指向新加节点；

2. 添加在中间（如C, D 中间）：将C的next 指针指向新节点，将新节点的next指向D。

删除节点：

1. 删除的是尾部节点：将尾部前一个节点的next置空；

2. 删除的是中间节点：将删除节点的前一个节点的next指向删除节点的next，将删除节点的next置空。

删除节点会被垃圾回收清除。

时间复杂度

链表的变种：

1. 最常见的，也是上面讨论的，单向链表；

2. 双向链表，可以往两个方向遍历；

3. 环形链表，末尾next指向头节点；

4. 跨度链表，next指向后续节点有不同的步数，基本的是1步，可以有多层如2步，3步等。这种链表可以加快遍历。

代码实现，javascript

包含下面的实现：创建一个新的链表；往头部加一个节点；往尾部加一个节点；在某节点前加一个节点；在某节点后加一个节点；查看链表是否包含某个值；移除第一个节点；移除最后一个节点；移除某个特定的节点；将链表转化为数组；获得链表的长度。

class LinkedListNode {
  constructor (data, next = null) {
        this.data = data;
        this.next = next;              
    }  
}

class LinkedList {
  constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;  
    }  

addFirst(data) {
  const newNode = new LinkedListNode(data, this.head);
  this.head = newNode;
  if (!this.tail) {
        this.tail = newNode;
    }  
  this.size++;  
}

addLast(data) {
  const newNode = new LinkedListNode(data);

  if (!this.head) {
     this.head = newNode;
     this.tail = newNode;
  } else {
     this.tail.next = newNode;
     this.tail = newNode;
  }  
  this.size++;
}

addBefore(beforeData, data) {
   const newNode = new LinkedListNode(data);
   if (this.size === 0)
    {
       this.head = newNode;
       this.size ++;
       return;
    }
    if (this.head.data === beforeData) {
       newNode.next = this.head;
       this.head = newNode;
       this.size ++;
       return;
    }
     let current = this.head.next;
     let prev = this.head;
     while (current) {
        if (current.data === beforeData) {
           newNode.next = current;
           prev.next = newNode;
           this.size ++;
           return;
        }
        prev = current;
        current = current.next;
     }
     throw new Error(`Node with data '${beforeData}' not found in list.`);
}

addAfter(afterData, data) {
    const newNode = new LinkedListNode(data);

     if (this.size === 0) {
        this.head = newNode;
        this.size ++;
         return;
     }

      let current = this.head;
      while (current) {
          if (current.data === afterData) {
             newNode.next = current.next;
             current.next = newNode;
             this.size ++;
              return;
          }
          current = current.next;
      }

      throw new Error(`Node with data '${afterData}' not found in the list.`);
}

contains(data) {
　　let current = this.head;
    while (current) {
        if (current.data === data)
            return true;
        current = current.next;
    }
    return false;
}

removeFirst() {
　　if (!this.head) {
       throw new Error('List is empty.');
    }
    this.head = this.head.next;
    if (!this.head) {
       this.tail = null;
    }
     this.size --;

}

removeLast() {
　　if (!this.tail)
       throw new Error('List is empty');

    if (this.head === this.tail) {
        this.head = null;
        this.tail = null;
        this.size --;
        return;
     }
     let current = this.head;
     let prev = null;
     while (current.next) {
         prev = current;
         current = current.next;
     }
     prev.next = null;
     this.tail = prev;
     this.size --;
}

remove(data) {
　　if (this.size === 0) {
       throw new Error("List is empty.");
    }

     if (this.head.data === data) {
        this.head = this.head.next;
        this.size --;
         return;
     }

      let current = this.head;
      while (current.next) {
          if (current.next.data === data) {
              current.next = current.next.next;
              this.size --;
               return;
          }
          current = current.next;
      }
      throw new Error(`Node with data '${data}' not found in list.`);
}

toArray() {
　　const arr = [];
    let current = this.head;
    while (current) {
        arr.push(current.data);
        current = current.next;
    }
    return arr;
}

getLength() {
　　return this.size;
}

}

 测试上面的方法：

let letters = new LinkedList();

letters.addLast("A");
letters.addLast("B");
letters.addLast("C");
letters.addLast("D");
letters.addLast("E");

console.log(letters.toArray()); // [‘A’, 'B', 'C', 'D', 'E']

letters.addFirst("AA");
letters.addLast("Z");

letters.remove("C");
letters.removeFirst();
letters.removeLast();

letters.addAfter("D", "Q");