数据结构与算法之链表

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

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

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

单向链表

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);
}

作者:@lsxlsxxslxsl