链表的定义和操作

普通链表

// 普通链表
    class linkList {
      constructor() {
        this.head = null;
        this.length = 0;
        this.findTail = () => {
          // 找到尾部的位置
          if(!this.head) {
            return null
          } else {
            let current = this.head;
            while(current.next) {
              current = current.next
            }
            return current;
          }
        };
        this.checkRange = (index) => {
          // 检查索引是否是合法的
          if(typeof index !== 'number' || index < 0 || index >= this.length) {
            throw new RangeError();
          }
        };
        this.findCurrent = (index) => {
          // 获取索引指定的位置
          let i = 0;
          let current = this.head;
          while(i !== index) {
            current = current.next;
            i++;
          }
          return current;
        }
      }
      // 获取item O(n)
      getItem(index) {
        // 检查index是否合法
        this.checkRange(index);
        const current = this.findCurrent(index);
        return current.value
      }
      // 设置item O(n)
      setItem(index, value) {
        // 检查index是否合法
        this.checkRange(index);
        const current = this.findCurrent(index);
        current.value = value;
      }
      // 添加数据 O(n)
      append(value) {
        let tail = this.findTail();
        if(!tail) {
          // 如果没有尾巴 说明只有一个头
          this.head = {
            value,
            next: null
          }
        } else {
          // 不是第一次添加
          let node = {value, next: null};
          tail.next = node;
        }
        this.length++;
      }
      // 插入 O(n)
      insert(index, value) {
        if(typeof index !== 'number' || index < 0 || index > this.length) {
          throw new RangeError();
        }
        // 需要创建一个新头
        if (index === 0) {
          const oldHead = this.head;
          this.head = { value, next: oldHead};
        } else {
          // 需要打散，获取插入指定位置的前一个
          const prev = this.findCurrent(index - 1);
          const oldCurrent = prev.next;
          // 创建新的数据 链接之前的
          const current = { value, next: oldCurrent};
          prev.next = current;
        }
        this.length++;
      }
      // 删除 O(n)
      delete(index) {
        this.checkRange(index);
        // 去掉老的头
        if(this.head) {
          if (index === 0) {
            this.head = this.head.next;
          } else {
            // 获取删除指定位置的前一个
            const prev = this.findCurrent(index - 1);
            if (!prev) return;
            const current = prev.next;
            if (!current) return;
            prev.next = current.next;
          }
          this.length--;
        }
      }
      // 查找 无序的 O(n)
      search(value) {
        let current = this.head;
        let i = 0;
        while(i < this.length) {
          if(!current) return -1;
          if(current.value === value) return i;
          current = current.next;
          i++;
        }
        // 如果没有找到 返回 -1
        return -1;
      }
    }
    let list = new linkList();
    list.append(1);
    list.append(3);
    list.append(5);
    list.append(8);
    list.append(10);
    console.log(list.search(5));
    console.log(list);

双向链表
优势：添加O(1)和 前删后删 O(1)

//  一般链表效率都很差， 优化 双向链表
    class HTLinkList{
      constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
      }
      // 算法复杂度 O(1)
      append(value) {
        // 如果有尾巴
        if(this.tail) {
          this.tail.next = {value, next: null, prev: this.tail};
          this.tail = this.tail.next;
        } else {
          // 如果没有 头和尾巴 都是一致的
          this.head = this.tail = {value, next: null, pre: null};
        }
        this.length++;
      }
      // 算法复杂度 O(1)
      pop() {
        let value;
        if(this.tail) {
          value = this.tail.value;
          // 如果前后都是 null
          if(!this.tail.next && !this.tail.prev) {
            this.length = 0;
            this.head = this.tail = null;
          } else {
            this.tail.prev.next = null;
            this.tail = this.tail.prev;
          }
        } 
        this.length--;
        return value;
      }
    }
  let list = new HTLinkList();
    list.append(1);
    list.append(3);
    list.append(5);
    // 后删
    console.log(list.pop());
    console.log(list.pop());
    console.log(list);

循环链表

缓存链表