04.链表.md

4. 链表

链表是一种动态的数据结构，这就意味着我们可以从中任意添加和移除元素，他也可以按需扩容。

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点(表头)开始迭代列表直到找到所需的元素。

单向链表

function Node(element){
  this.element = element;
  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;
}
function find(item){
  var currNode = this.head;
  while(currNode.element != item){
    currNode = currNode.next;
  }
  return currNode;
}
function insert(newElement, item){
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
}
function display(){
  var currNode = this.head;
  while(currNode.next != null){
    console.log(currNode.next.element);
    currNode=currNode.next;
  }
}
function findPrevious(item){
  var currNode = this.head;
  while ((currNode.next!=null)&&(currNode.next.element!=item)) {
    currNode = currNode.next;
  }
  return currNode;
}
function remove(item){
  var preNode = this.findPrevious(item);
  var currNode = this.find(item);
  if(preNode.next!=null){
    preNode.next = currNode.next;
    currNode.next = null;
  }
}
var cities = new LList();
cities.insert('first','head');
cities.insert('second','first');
cities.insert('third','second');
cities.display();
console.log(cities.find('third'));
console.log("=====================");
// cities.remove('second');
// cities.display();

双向链表

function Node(element,next,pre){
  this.element = element;
  this.next = null;
  this.pre = null;
}
function LList(){
  this.head = new Node('head');
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.remove = remove;
  this.displReverse = displReverse;
  this.findLast = findLast;
}
function find(item){
  var currNode = this.head;
  while (currNode.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}
function insert(newElement, item){
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  newNode.pre = currNode;
  currNode.next = newNode;
  if(newNode.next == null){
    newNode.next.pre = newNode;
  }
}
function display(){
  var currNode = this.head;
  while(currNode.next != null){
    console.log(currNode.next.element);
    currNode=currNode.next;
  }
}
function remove(item){
  var currNode = this.find(item);
  if(currNode.next != null){
    currNode.pre.next = currNode.next;
    currNode.next.pre = currNode.pre;
    currNode.next = null;
    currNode.pre = null;
  }else{
    currNode.pre.next = null;
    currNode.pre = null;
  }
}
function findLast(){
  var currNode = this.head;
  while (!(currNode.next == null)) {
    currNode = currNode.next;
  }
  return currNode;
}
function displReverse(){
  var currNode = this.findLast();
  while (!(currNode.pre==null)) {
    console.log(currNode.element);
    currNode = currNode.pre;
  }
}

try{
  var cities = new LList();
  cities.insert('first','head');
  cities.insert('second','first');
  cities.insert('third','second');
  cities.remove('second');
  cities.display();
  cities.displReverse();
}catch(err){
  console.log(err);
}