JavaScript数据结构笔记-单向链表、双向链表

单向链表

单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址，单向链表只可向一个方向遍历。

// 单项链表节点
class LinkedListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
// 单向链表
class LinkedList {
  constructor() {
    this.head = new LinkedListNode("head");
    this.size = 0;
  }
  // 向链表尾添加一个元素
  append = (val) => {
    let newItem = new LinkedListNode(val);
    let lastNode = this.findByIndex(this.size);
    if (lastNode !== null) {
      lastNode.next = newItem;
      this.size ++;
    } else {
      console.error(`<${val}>添加失败`);
    }
    this.print();
  }
  // 删除一个指定节点
  remove = (val) => { 
    let preNode = this.findPreNode(val);
    if (preNode !== null && preNode.next !== null) {
      preNode.next = preNode.next.next;
      this.size --;
    } else {
      console.error(`<${val}>删除失败`);
    }
    this.print();
  }
  // 删除一个指定位置的节点
  removeByIndex = (index) => {
    let indexNode = this.findByIndex(index - 1);
    if(indexNode != null && indexNode.next != null) {
      indexNode.next = indexNode.next.next;
      this.size --;
    } else {
      console.error(`删除位于${index}处节点失败`);
    }
    this.print();
  }
  // 在指定节点后插入一个元素
  insert = (val, newVal) => {
    let node = this.find(val);
    let newNode = new LinkedListNode(newVal);
    if(node.next == null) {
      node.next = newNode;
    } else {
      let temp = node.next;
      node.next = newNode;
      newNode.next = temp;
    }
    this.size++;
    this.print();
  }
  // 在指定位置后一个位置插入一个元素
  insertByIndex = (index, newVal) => {
    let node = this.findByIndex(index);
    let newNode = new LinkedListNode(newVal);
    if(node.next == null) {
      node.next = newNode;
    } else {
      let temp = node.next;
      node.next = newNode;
      newNode.next = temp;
    }
    this.size++;
    this.print();
  }
  // 查找等于某值的节点
  find = (val) => {
    let currentNode = this.head;
    while(currentNode != null && currentNode.val != val) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }
  // 查找位于某位置的节点
  findByIndex = (index) => {
    if (index > this.size) {
      return null;
    }
    let currentNode = this.head;
    for(let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }
  // 查找等于某值的前驱节点  
  findPreNode = (val) => {
    let currentNode = this.head;
    while(currentNode != null && currentNode.next !== null && currentNode.next.val != val) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }
  // 清空链表
  clear = () => {
    this.head.next = null;
    this.print();
  }
  // 链表大小
  size = () => {
    return this.size;
  }
  // 打印
  print = () => {
    let currentNode = this.head;
    let printString = '';
    while(currentNode != null) {
      printString = printString + '-->' + currentNode.val;
      currentNode = currentNode.next;
    }
    console.log(printString);
  }
}

function testLinkedList() {
  const myLinkedList = new LinkedList();
  myLinkedList.append("节点1");
  myLinkedList.append("节点2");
  myLinkedList.append("节点3");
  myLinkedList.append("节点4");
  myLinkedList.append("节点5");
  myLinkedList.append("节点6");

  myLinkedList.remove("节点5");
  myLinkedList.remove("节点6");
  myLinkedList.remove("节点6");

  myLinkedList.removeByIndex(2);

  myLinkedList.insert("节点1", "新节点2");
  myLinkedList.insert("节点4", "新节点4");

  myLinkedList.insertByIndex(3, "新节点3");

  myLinkedList.clear();
}

-->head-->节点1
-->head-->节点1-->节点2
-->head-->节点1-->节点2-->节点3
-->head-->节点1-->节点2-->节点3-->节点4
-->head-->节点1-->节点2-->节点3-->节点4-->节点5
-->head-->节点1-->节点2-->节点3-->节点4-->节点5-->节点6
-->head-->节点1-->节点2-->节点3-->节点4-->节点6
-->head-->节点1-->节点2-->节点3-->节点4
<节点6>删除失败
-->head-->节点1-->节点2-->节点3-->节点4
-->head-->节点1-->节点3-->节点4
-->head-->节点1-->新节点2-->节点3-->节点4
-->head-->节点1-->新节点2-->节点3-->节点4-->新节点4
-->head-->节点1-->新节点2-->节点3-->新节点3-->节点4-->新节点4
-->head

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针。所以在双向链表中的结点都有两个指针域：一个指向直接后继，一个指向直接前驱。

// 双向链表节点
class DoublyLinkedListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.pre = null;
  }
}
// 双向链表
class DoublyLinkedList {
  constructor() {
    this.head = new DoublyLinkedListNode("head");
    this.size = 0;
  }

  append = (val) => {
    let lastNode = this.findByIndex(this.size);
    if(lastNode != null) {
      let newNode = new DoublyLinkedListNode(val);
      lastNode.next = newNode;
      newNode.pre = lastNode;

      this.size++;
      this.print();
    } else {
      console.error(`<${val}>添加失败`);
    }
  }

  insert = (val, newVal) => {
    let valNode = this.findByVal(val);
    if (valNode != null) {
      let newNode = new DoublyLinkedListNode(newVal);
      let tempNode = valNode.next;
      if(tempNode != null) {
        tempNode.pre= newNode;
      } 

      valNode.next = newNode;
      newNode.pre = valNode;
      newNode.next = tempNode;

      this.size++;
      this.print();
    } else {
      console.error(`该链表不存在<${val}>节点`);
    }
  }

  remove = (val) => {
    let node = this.findByVal(val);
    if (node != null) {
      if(node.next != null) {
        let preNode = node.pre;
        let nextNode = node.next;
        preNode.next = nextNode;
        nextNode.pre = preNode;

        node.pre = null;
        node.next = null;
      } else {
        let preNode = node.pre;
        preNode.next = null;
        node.pre = null;
      }
      this.size--;
      this.print();
    } else {
      console.error(`该链表不存在<${val}>节点`);
    }
  }

  findByVal = (val) => {
    let currentNode = this.head;
    while(currentNode.val != val) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  // 查找位于某位置的节点
  findByIndex = (index) => {
    if (index > this.size) {
      return null;
    }
    let currentNode = this.head;
    for(let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  print = () => {
    let currentNode = this.head;
    let printString = '';
    while(currentNode != null) {
      printString = printString + '-->' + currentNode.val;
      currentNode = currentNode.next;
    }
    console.log(printString);
  }
}

// 测试双向链表
function testDoublyLinkedList() {
  let myDoubyLinkedList = new DoublyLinkedList();
  myDoubyLinkedList.append("双向节点1");
  myDoubyLinkedList.append("双向节点2");
  myDoubyLinkedList.append("双向节点3");

  myDoubyLinkedList.insert("双向节点1", "插入节点1");
  myDoubyLinkedList.insert("双向节点3", "插入节点3");

  myDoubyLinkedList.remove("双向节点2");
  myDoubyLinkedList.remove("插入节点3");
}

-->head-->双向节点1
-->head-->双向节点1-->双向节点2
-->head-->双向节点1-->双向节点2-->双向节点3
-->head-->双向节点1-->插入节点1-->双向节点2-->双向节点3
-->head-->双向节点1-->插入节点1-->双向节点2-->双向节点3-->插入节点3
-->head-->双向节点1-->插入节点1-->双向节点3-->插入节点3
-->head-->双向节点1-->插入节点1-->双向节点3