Skip to content

Latest commit

 

History

History
321 lines (308 loc) · 7.8 KB

05.md

File metadata and controls

321 lines (308 loc) · 7.8 KB

链表

链表是什么

  1. 链表是一个由节点组成的集合，节点有一个指针指向它的后继
  2. 链表元素靠相互关系进行引用
  3. 链表需要一个头节点作为接入点
  4. 链表的尾元素指向一个 null 节点

链表种类

  • 单向链表
{
  function Node(item) {
    this.element = item;
    this.next = null;
  }

  function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
  }
  // 查找节点
  let find = function(item) {
    var currentNode = this.head;
    while (currentNode.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let insert = function(nItem, oItem) {
    var oldNode = this.find(oItem);
    var newNode = new Node(nItem);
    newNode.next = oldNode.next;
    oldNode.next = newNode;
  };
  let display = function() {
    var currentNode = this.head;
    var result = "";
    while (currentNode.next !== null) {
      result += "," + currentNode.next.element;
      currentNode = currentNode.next;
    }
    console.log(result);
  };
  let findPrevious = function(item) {
    var currentNode = this.head;
    while (currentNode.next !== null && currentNode.next.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let remove = function(item) {
    var previousNode = this.findPrevious(item);
    if (previousNode.next !== null) {
      previousNode.next = previousNode.next.next;
    }
  };
  var list = new LList();
  list.insert(1, "head");
  list.insert(2, 1);
  list.insert(3, 2);
  list.insert(4, 3);
  list.display();
  list.remove(2);
  list.display();
  console.log(list.findPrevious(4));
  console.log(list.find(4));
}
  • 双向链表
{
  function Node(item) {
    this.element = item;
    this.next = null;
    this.previous = null;
  }
  function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.findLast = findLast;
    this.display = display;
    this.displayReverse = displayReverse;
  }
  let find = function(item) {
    var currentNode = this.head;
    while (currentNode.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let insert = function(nItem, oItem) {
    var newNode = new Node(nItem);
    var oldNode = this.find(oItem);
    newNode.next = oldNode.next;
    newNode.previous = oldNode;
    oldNode.next = newNode;
  };
  let remove = function(item) {
    var currentNode = this.find(item);
    if (currentNode.next !== null) {
      currentNode.previous.next = currentNode.next;
      currentNode.next.previous = currentNode.previous;
      currentNode.previous = null;
      currentNode.next = null;
    }
  };
  let findLast = function() {
    var currentNode = this.head;
    while (currentNode.next !== null) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let display = function() {
    var currentNode = this.head;
    var result = "";
    while (currentNode.next !== null) {
      result += "," + currentNode.next.element;
      currentNode = currentNode.next;
    }
    console.log(result);
  };
  let displayReverse = function() {
    var currentNode = this.findLast();
    var result = "";
    while (currentNode.previous !== null) {
      result += "," + currentNode.element;
      currentNode = currentNode.previous;
    }
    console.log(result);
  };
  var list = new LList();
  list.insert(11, "head");
  list.insert(22, 11);
  list.insert(33, 22);
  list.insert(44, 33);
  list.display();
  list.remove(22);
  list.display();
  list.displayReverse();
  console.log(list.findLast());
  console.log(list.find(11));
}
  • 循环链表
{
  function Node(item) {
    this.element = item;
    this.next = null;
  }

  function LList() {
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
  }
  // 查找节点
  let find = function(item) {
    var currentNode = this.head;
    while (currentNode.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let insert = function(nItem, oItem) {
    var oldNode = this.find(oItem);
    var newNode = new Node(nItem);
    newNode.next = oldNode.next === null ? this.head : oldNode.next;
    oldNode.next = newNode;
  };
  let display = function() {
    var currentNode = this.head;
    var result = "";
    while (currentNode.next !== null && currentNode.next.element !== "head") {
      result += "," + currentNode.next.element;
      currentNode = currentNode.next;
    }
    console.log(result);
  };
  let findPrevious = function(item) {
    var currentNode = this.head;
    while (currentNode.next !== null && currentNode.next.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let remove = function(item) {
    var previousNode = this.findPrevious(item);
    if (previousNode.next !== null && previousNode.next.element !== "head") {
      previousNode.next = previousNode.next.next;
    }
  };
  var list = new LList();
  list.insert(1, "head");
  list.insert(2, 1);
  list.insert(3, 2);
  list.insert(4, 3);
  list.display();
  console.log(list.find(4));
  list.remove(4);
  console.log(list.find(3));
  console.log(list.findPrevious(3));
}
  • 双向链表的前移与后移
{
  function Node(item) {
    this.element = item;
    this.next = null;
    this.previous = null;
  }
  function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.findLast = findLast;
    this.display = display;
    this.displayReverse = displayReverse;
    this.currentNode = this.head;
    this.advance = advance;
    this.back = back;
    this.show = show;
  }
  let find = function(item) {
    var currentNode = this.head;
    while (currentNode.element !== item) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let insert = function(nItem, oItem) {
    var newNode = new Node(nItem);
    var oldNode = this.find(oItem);
    newNode.next = oldNode.next;
    newNode.previous = oldNode;
    oldNode.next = newNode;
  };
  let remove = function(item) {
    var currentNode = this.find(item);
    if (currentNode.next !== null) {
      currentNode.previous.next = currentNode.next;
      currentNode.next.previous = currentNode.previous;
      currentNode.previous = null;
      currentNode.next = null;
    }
  };
  let findLast = function() {
    var currentNode = this.head;
    while (currentNode.next !== null) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };
  let display = function() {
    var currentNode = this.head;
    var result = "";
    while (currentNode.next !== null) {
      result += "," + currentNode.next.element;
      currentNode = currentNode.next;
    }
    console.log(result);
  };
  let displayReverse = function() {
    var currentNode = this.findLast();
    var result = "";
    while (currentNode.previous !== null) {
      result += "," + currentNode.element;
      currentNode = currentNode.previous;
    }
    console.log(result);
  };
  let advance = function(n) {
    while (n > 0 && this.currentNode.next !== null) {
      this.currentNode = this.currentNode.next;
      n--;
    }
  };
  let back = function(n) {
    while (n > 0 && this.currentNode.previous.element !== "head") {
      this.currentNode = this.currentNode.previous;
      n--;
    }
  };
  let show = function() {
    console.log(this.currentNode);
  };
  let list = new LList();
  list.insert(111, "head");
  list.insert(222, 111);
  list.insert(333, 222);
  list.insert(444, 333);
  list.advance(5);
  list.show();
  list.back(2);
  list.show();
  list.display();
}