关于javascript:js实现链表类

链表与数组

数组是一串有序的排列

而链表中不能间接以下标为索引取值

链表类的实现

1、定义一个类，自带属性要有长度和头部

class LinkList {constructor() {
      this.length = 0
      this.head = null
    }
}

2、须要有个查找办法，前面增删改也会须要用到

getElementAt(position) {
    // 做个校验提高效率
    if (position < 0 || position >= this.length) 
      return null
    
    let current = this.head
    for (let i = 0; i < position ; i++) {
      // 赋值为下一个节点
      current = current.next
    }
    // 循环完结，找到指标节点返回
    return current
}

3、新增节点的办法

这里须要个辅助类 — 节点类

class Node {constructor(element) {
      this.element = element
      this.next = null
    }
}

新增办法

append(element) {let node = new Node(element)
    // 如果是空链表
    if (this.head === null) {this.head = node} else {
      // 找到最初一个元素
      let current = this.getElementAt(this.length - 1)
      current.next = node
    }
    this.length++
}

3、插入方法

insert(position, element) {if (position < 0 || position > this.length)
      return false
    let node = new Node(element)
    if (position === 0) {
      node.next = this.head
      this.head = node
    } else {
      // 找到上一个的地位
      let previous = this.getElementAt(position - 1)
      // 1 -> 3 =>> 2 -> 3
      node.next = previous.next
      // 1 -> 2
      previous.next = node
      // 1 -> 2 -> 3
    }
    this.length++
    return true
}

4、移除办法

removeAt(position) {if (position < 0 || position > this.length) 
      return false
    let current = this.head
    if (position === 0) {this.head = current.next} else {
      // 找到索引值上一个
      let previous = this.getElementAt(positoin - 1)
      // 找到索引值, 2
      current = previous.next
      // 索引值的上一个间接指向索引值的下一个，也就是跳过索引值
      // 1 -> 2 -> 3 =>> 1 -> 3
      previous.next = current.next
    }
    this.length--
    return current.element
}

5、依据值查找索引

indexOf(element) {
    let current = this.head
    for(let i = 0; i < this.length; i++) {if (current.element === element)
        return i
      current = current.next
    }
    return -1
}

残缺代码

class LinkList {constructor() {
    this.length = 0;
    this.head = null; // 能够用作链表是否为空的判断
  }
  getElementAt(position) {if (position < 0 || position >= this.length) return null;
    let current = this.head;
    for (let i = 0; i < position; i++) {current = current.next;}
    return current;
  }

  append(element) {let node = new Node(element);
    if (this.head == null) {this.head = node;} else {let current = this.getElementAt(this.length - 1);
      current.next = node;
    }
    this.length++;
  } 

  insert(position, element) {if (position < 0 || position > this.length) return false;
    let node = new Node(element);
    if (position === 0) {
      node.next = this.head;
      this.head = node;
    } else {let previous = this.getElementAt(position - 1);
      node.next = previous.next;
      previous.next = node;
    }

    this.length++;
    return true;
  }

  removeAt(position) {if (position < 0 || position > this.length) return false;
    let current = this.head;
    if (position === 0) {this.head = current.next;} else {let previous = this.getElementAt(position - 1);
      current = previous.next;
      previous.next = current.next;
    }
    this.length--;
    return current.element;
  } 

  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.length; i++) {if (current.element === element) return i;
      current = current.next;
    }

    return -1;
  }

}

class Node {constructor(element) {
    this.element = element
    this.next = null
  }
}