第 115 题：写一个单向链数据结构的 JS 实现并标注复杂度

Question

逻辑上相邻的数据元素在物理上不一定相邻，可用于存储线性表、树、图等多种逻辑结构。插入、删除操作比较灵活，不必移动数据元素，只要改变结点中的指针域的值即可。

Answer 1

//链表节点
class Node {
constructor(element) {
this.element = element
this.next = null
}
}

//链表
class LinkedList {
constructor() {
this.head = null
this.length = 0
}

//追加元素
append(element) {
    const node = new Node(element)
    let current = null
    if (this.head === null) {
        this.head = node
    } else {
        current = this.head
        while (current.next) {
            current = current.next
        }
        current.next = node
    }
    this.length++
}

//任意位置插元素
insert(position, element) {
    if (position >= 0 && position <= this.length) {
        const node = new Node(element)
        let current = this.head
        let previous = null
        let index = 0
        if (position === 0) {
            this.head = node
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }
            node.next = current
            previous.next = node
        }
        this.length++
        return true
    }
    return false
}

//移除指定位置元素
removeAt(position) {
    //检查越界
    if (position > -1 && position < length) {
        let current = this.head
        let previous = null
        let index = 0
        if(position === 0){
            this.head = current.next
        }else{
            while(index++ < position){
               previous = current
               current = current.next
            }
            previous.next = current.next
        }
        this.length--
        return current.element
    }
    return null
}

//寻找元素下标
findIndex(element){
    let current = this.head
    let index = -1
    while(current){
        if (element === current.element){
            return index + 1
        }
        index++
        current = current.next
    }
    return -1
}

//删除指定文档
remove(element){
    const index = this.indexOf(element)
    return this.removeAt(index)
}

isEmpty(){
    return !this.length
}

size(){
    return this.length
}

//转为字符串
toString(){
    let current = this.head
    let string = ''
    while(current){
        string += '$(current.element)'
        current = current.next
    }
    return string
}

}

正好学习的时候照着写过，不过时间复杂度和空间复杂度我都不太懂

Answer 2

神仙题，，，看不懂咋办

Answer 3

class Node {
	constructor(value,next) {
	    this.value = value;
	    this.next = next;
	}
}
class LinkList {
  constructor(value) {
      this.head = new Node(value);
  }
  add(newVal, val) {
      const newNode = new Node(newVal);
      const curNode = this.find(val);
      newNode.next = curNode.next;
      curNode.next = newNode;
    return newNode;
  }
  // 时间复杂度O(n)
  find(value){
      let curNode = this.head;
      while(curNode.value != value && curNode) {
        curNode = curNode.next ? curNode.next : null;
      }
    return curNode;
  }
  del(val) {
    let prevNode = this.findPrev(val);
    let curNode = prevNode.next;
    prevNode.next = curNode.next;
    return curNode;
    
  }
  findPrev(val) {
    let curNode = this.head;
    while(curNode && curNode.next && curNode.next.value !== val ) {
        curNode = curNode.next ? curNode.next : null;
    }
    return curNode;
  }
  print() {
    let curNode = this.head;
    while(curNode){
      console.log(curNode.value);
      curNode = curNode.next;
    }
  }
}

const link = new LinkList('11');
link.add('22','11');
link.add('33','22');
link.del('21');
link.print();

我删除node的时候假如把head传进去，这个方法就不对了

Answer 4

class Node {
	constructor(value,next) {
	    this.value = value;
	    this.next = next;
	}
}
class LinkList {
  constructor(value) {
      this.head = new Node(value);
  }
  add(newVal, val) {
      const newNode = new Node(newVal);
      const curNode = this.find(val);
      newNode.next = curNode.next;
      curNode.next = newNode;
    return newNode;
  }
  // 时间复杂度O(n)
  find(value){
      let curNode = this.head;
      while(curNode.value != value && curNode) {
        curNode = curNode.next ? curNode.next : null;
      }
    return curNode;
  }
  del(val) {
    let prevNode = this.findPrev(val);
    let curNode = prevNode.next;
    prevNode.next = curNode.next;
    return curNode;
    
  }
  findPrev(val) {
    let curNode = this.head;
    while(curNode && curNode.next && curNode.next.value !== val ) {
        curNode = curNode.next ? curNode.next : null;
    }
    return curNode;
  }
  print() {
    let curNode = this.head;
    while(curNode){
      console.log(curNode.value);
      curNode = curNode.next;
    }
  }
}

const link = new LinkList('11');
link.add('22','11');
link.add('33','22');
link.del('22');
link.print();

Answer 5

class ListNode {
    constructor(val) {
        this.val = val
        this.next = null
    }
}

class LinkedList {
    head = null
    tail = null
    size = 0

    // 时间复杂度O(n)
    get = index => {
        if (index < 0) return -1
        let node = this.head
        for (let i = 0; i < index; i++) {
            if (!node) return -1
            node = node.next
        }
        return node ? node.val : -1
    }

    // 时间复杂度O(1)
    addAtHead = val => {
        const node = new ListNode(val)
        if (!this.head) {
            this.head = this.tail = node
        } else {
            node.next = this.head
            this.head = node
        }
        this.size++
    }

    // 时间复杂度O(1)
    addAtTail = val => {
        const node = new ListNode(val)
        if (!this.tail) {
            this.head = this.tail = node
        } else {
            this.tail.next = node
            this.tail = node
        }
        this.size++
    }

    // 时间复杂度O(n)
    addAtIndex = (index, val) => {
        const node = new ListNode(val)
        if (index > this.size) return
        if (index === this.size) return this.addAtTail(val)
        if (index <= 0) return this.addAtHead(val)
        let head = this.head
        for (let i = 1; i < index; i++) {
            if (!head) return
            head = head.next
        }
        node.next = head.next
        head.next = node
        this.size++
    }

    // 时间复杂度O(n)
    deleteAtIndex = index => {
        let head = this.head
        if (!head || index >= this.size || index < 0) return
        if (index === 0) {
            if (this.size === 1) {
                this.head = this.tail = null
            } else {
                this.head = this.head.next
            }
            this.size--
            return
        }
        for (let i = 1; i < index; i++) {
            if (!head) return
            head = head.next
        }
        if (!head) return
        if (head.next) {
            if (head.next === this.tail) {
                this.tail = head
                head.next = null
            } else {
                head.next = head.next.next
            }
        } else {
            this.head = this.tail = null
        }
        this.size--
    }
}

Answer 6

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

class SinglyLinkedList {

    #firstNode;

    constructor() {
        this.#firstNode = null;
    }

    get firstNode() {
        return this.#firstNode;
    }

    insertAfter(node, newNode) {
        if (!newNode) return;

        if (node) {
            newNode.next = node.next;
            node.next = newNode;
        }
        else {
            newNode.next = this.#firstNode;
            this.#firstNode = newNode;
        }
    }

    insertBeginning(newNode) {
        this.insertAfter(null, newNode);
    }

    removeAfter(node) {
        if (node) {
            node.next = node.next.next;
        }
        else if (this.#firstNode) {
            this.#firstNode = this.#firstNode.next;
        }
    }

    removeBeginning() {
        this.removeAfter(null);
    }
}

var list = new SinglyLinkedList();
list.insertBeginning(new Node("a"));
list.insertAfter(list.firstNode, new Node("d"));
list.insertAfter(list.firstNode, new Node("c"));
list.insertAfter(list.firstNode, new Node("b"));

var currentNode = list.firstNode;
while (currentNode) {
    console.log(currentNode.data);
    currentNode = currentNode.next;
}

list.removeBeginning(); // Remove 'a'
list.removeAfter(list.firstNode); // Remove 'c' after 'b'

var currentNode = list.firstNode;
while (currentNode) {
    console.log(currentNode.data);
    currentNode = currentNode.next;
}

Answer 7

问题来了，在哪学数据结构相关知识

Answer 8

详解

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

  find(value) {
    let curNode = this.head
    while (curNode.value !== value) {
      curNode = curNode.next
    }
    return curNode
  }

  findPrev(value) {
    let curNode = this.head
    while (curNode.next!==null && curNode.next.value !== value) {
      curNode = curNode.next
    }
    return curNode
  }

  insert(newValue, value) {
    const newNode = new Node(newValue)
    const curNode = this.find(value)
    newNode.next = curNode.next
    curNode.next = newNode
  }

  delete(value) {
    const preNode = this.findPrev(value)
    const curNode = preNode.next
    preNode.next = preNode.next.next
    return curNode
  }
}

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