js实现links-list

链表

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的每个节点通过指针连接在一起，形成一个链式结构。链表的优点是插入和删除操作非常高效，时间复杂度为O(1)，而查找操作的时间复杂度为O(n)。链表的缺点是查找操作的时间复杂度为O(n)，而插入和删除操作的时间复杂度为O(1)。

链表的实现

链表的实现主要分为两种：单链表和双链表。单链表的每个节点只包含数据和指向下一个节点的指针，而双链表的每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针。

单链表的实现

单链表的节点

单链表的节点包含数据和指向下一个节点的指针。

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

单链表的链表

单链表的链表包含头节点和尾节点。

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

单链表的插入

单链表的插入操作分为两种：在链表头部插入(prepend头插法)和在链表尾部插入(append尾插法)。

在链表头部插入

prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    if(!this.tail){
        this.tail = newNode;
    }
    return this;
}

在链表尾部插入

append(value) {
    const newNode = new Node(value);
    if(!this.head){
        this.head = newNode;
        this.tail = newNode;
    }else{
        this.tail.next = newNode;
        this.tail = newNode;
    }
    return this;
}

在链表中插入

insert(value,index) {
    if(index < 0){
        return false;
    }
    if(index === 0){
        return this.prepend(value);
    }
    if(index === this.length){
        return this.append(value);
    }
    const newNode = new Node(value);
    const prevNode = this.get(index - 1);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    return this;
}
get(index) {
    if(index < 0 || index >= this.length){
        return null;
    }
    let current = this.head;
    let count = 0;
    while(count < index){
        current = current.next;
        count++;
    }
}