关于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  }}