信鸽网

JavaScript数据结构与算法之链表

  作者：bea

链表简介 链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。 使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。 接下来就是介绍两种常见的链表: 单向链表，双向链表在JavaScript中的实现。 单向链表 链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，

链表简介


链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。
使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
接下来就是介绍两种常见的链表: 单向链表，双向链表在JavaScript中的实现。


单向链表


链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，第一部分储存着自身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL:


JavaScipt中单向链表的实现


首先，创建一个构造函数。




/**

 * 单向链表构造函数

 */

function LinkedList() {

 /**

  * 单向链表中节点的构造函数

  * @param {Any} element 要传入链表的节点

  */

 var Node = function(element) {

  this.element = element;

  //下个节点的地址

  this.next = null;

 }



 //单向链表的长度

 var length = 0;

 //单向链表的头结点，初始化为NULL

 var head = null;

}


不难看出，单向链表构造函数比栈与队列要复杂许多。
单向链表需要有如下的方法:



  1. append(element): 添加元素到链表尾部

  2. insert(position,element): 向单向链表中某个位置插入元素

  3. indexOf(element): 寻找某个元素在单向链表中的位置

  4. remove(element): 移除给定的元素

  5. removeAt(position): 移除单向链表中某个位置的元素

  6. getHead(): 获取单向链表的头部

  7. isAmpty(): 检查单向链表是否为空，为空则返回true

  8. toString(): 将链表所有内容以字符串输出

  9. size(): 返回单向链表长度


append方法:


说明: 向单向链表尾部添加元素。
实现:




/**

 * 向单向链表尾部添加元素

 * @param {Any} element 要加入链表的节点

 */

this.append = function(element) {

 var node = new Node(element);

 var current;



 if (head == null) {

  head = node;

 } else {

  // 当前项等于链表头部元素.

  // while循环到最后一个，从而将该节点加入链表尾部。

  current = head;

  // 当next为null时，判定为false。退出循环。

  while (current.next) {

   current = current.next;

  }

  current.next = node;

 }

 length++;

};


insert方法:


说明: 向单向链表中某个位置插入元素。
实现:




/**

 * 向单向链表中插入某个元素

 * @param {Number} position 要插入的位置

 * @param {Any} element 要插入的元素

 * @return {Boolean}     插入成功返回true，失败返回false

 */

this.insert = function(position, element) {

 if (position >= 0 && position <= length) {

  var node = new Node(element);

  var current = head;

  var previous;

  var index = 0;



  if (position == 0) {

   node.next = current;

   head = node;

  } else {

   while (index++ < position) {

    previous = current;

    current = current.next;

   }



   previous.next = node;

   node.next = current;

  }



  length++;

  return true;

 } else {

  return false;

 }

};


indexOf方法:


说明：寻找某个元素在单向链表中的位置。
实现:




/**

 * 寻找某个元素在单向链表中的位置

 * @param {Any} element 要寻找的元素

 * @return {Number}     返回值>=0则代表找到相应位置

 */

this.indexOf = function(element) {

 var current = head;

 var index = -1;



 while (current) {

  if (element === current.element) {

   return index;

  }

  index++;

  current = current.next;

 }



 return -1;

};


remove方法:


说明: 移除给定的元素。
实现:




/**

 * 移除给定的元素

 * @param {Any} element 要移除的元素

 * @return {Number}     返回值>=0表示移除成功

 */

this.remove = function(element) {

 var index = this.indexOf(element);

 return this.removeAt(index);

};


removeAt方法:


说明:移除单向链表中某个位置的元素。
实现:




/**

 * 移除单向链表中某一个元素

 * @param {Number} position 要移除元素的位置

 * @return {Any}     移除成功返回被移除的元素，不成功则返回NULL

 */

this.removeAt = function(position) {

 if (position > -1 && position < length) {

  var current = head;

  var previous;

  var index = 0;



  if (position == 0) {

   // 因为之前head指向第一个元素，现在把head修改为指向第二个元素。

   // 核心概念在于链表前后全靠指针链接，而非数组一般。

   // 所以只需要改变head的元素。

   head = current.next;

  } else {

   while (index++ < position) {

    // previous指要操作元素位置之前的那个元素，current表示之后的那个元素。

    previous = current;

    current = current.next;

   }



   previous.next = current.next;

  }



  length--;



  return current.element;

 } else {

  return null;

 }

};


getHead方法:


说明:获取单向链表的头部。
实现:




/**

 * 获取单向链表的头部

 * @return {Any} 单向链表的头部

 */

this.getHead = function() {

 return head;

}


isAmpty、toString、size方法


实现:




/**

 * 判断单向链表是否为空

 * @return {Boolean} 为空则返回true，不为空则返回false

 */

this.isAmpty = function() {

 return length === 0

};



/**

 * 将链表所有内容以字符串输出

 * @return {String} 要输出的字符串

 */

this.toString = function() {

 var current = head;

 var string = ';



 while (current) {

  string += current.element;

  current = current.next;

 }

 return string;

};



/**

 * 返回单向链表长度

 * @return {Number} 单向链表的长度

 */

this.size = function() {

 return length;

};


双向链表


双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。


JavaScipt中双向链表的实现


首先，依然是构造函数:




/**

 * 双向链表的构造函数

 */

function DoublyLinkedList() {

 /**

  * 双向链表中节点的构造函数

  * @param {Any} element 要传入链表的元素

  */

 var Node = function(element) {

  this.element = element;

  this.prev = null;

  this.next = null;

 }



 //双向链表的长度

 var length = 0;

 //双向链表的头结点，初始化为NULL

 var head = null;

 //双向链表的尾结点，初始化为NULL

 var tail = null;

}


双向链表需要有如下的方法:



  1. append(element): 添加元素到双向链表尾部

  2. insert(position,element): 向双向链表中某个位置插入元素

  3. removeAt(position): 移除双向链表中某个位置的元素

  4. showHead(): 获取双向链表的头部

  5. showLength(): 获取双向链表长度

  6. showTail(): 获取双向链表尾部


append方法:


说明: 添加元素到双向链表尾部
实现:




/**

 * 向链表尾部添加元素

 * @param {Any} element 要加入链表的节点

 * @return {Any}     加入链表的节点

 */

this.append = function(element) {

 var node = new Node(element);



 if (head === null) {

  head = node;

  tail = node;

 } else {

  var previous;

  var current = head;



  while (current.next) {

   current = current.next;

  }



  current.next = node;

  node.prev = current;

  tail = node;

 }



 length++;

 return node;

};


insert方法:


说明: 向双向链表中某个位置插入元素。
实现:




/**

 * 向链表中插入某个元素

 * @param {Number} position 要插入的位置

 * @return {Boolean}     插入成功返回true，失败返回false

 */

this.insert = function(position, element) {

 if (position >= 0 && position <= length) {



  var node = new Node(element);

  var index = 0;

  var previous;

  var current = head;



  if (position === 0) {



   if (head === null) {

    head = node;

    tail = node;

   } else {

    current.prev = node;

    node.next = current;

    head = node;

   }

  } else if (position === length) {



   current = tail;

   current.next = node;

   node.prev = current;

   tail = node;

  } else {



   while (index++ < position) {

    previous = current;

    current = current.next;

   }



   previous.next = node;

   node.prev = previous;

   current.prev = node;

   node.next = current;

  }



  length++;

  return true;

 } else {

  return false;

 }

};


removeAt方法:


说明:移除双向链表中某个位置的元素。
实现:




/**

 * 移除链表中某一个元素

 * @param {Number} position 要移除元素的位置

 * @return {Any}       移除成功返回被移除的元素，不成功则返回false

 */

this.removeAt = function(position) {

 if (position > -1 && position < length) {

  var current = head;

  var index = 0;

  var previous;



  if (position === 0) {

   head = current.next;



   if (length === 1) {

    tail = null;

    head.prev = null;

   }

  } else if (position === length - 1) {

   current = tail;

   tail = current.prev;

   tail.next = null;

  } else {

   while (index++ < position) {

    previous = current.prev;

    current = current.next;

   }

   previous.next = current.next;

   current.next.prev = previous;

  }



  length--;

  return current.element;

 } else {

  return false;

 }

};


showHead、showLength、showTail方法


实现:




/**

 * 获取链表的头部

 * @return {Any} 链表的头部

 */

this.showHead = function() {

 return head;

};



/**

 * 获取链表长度

 * @return {Number} 链表长度

 */

this.showLength = function() {

 return length;

};



/**

 * 获取链表尾部

 * @return {Any} 链表尾部

 */

this.showTail = function() {

 return tail;

};


感想


链表这一节，基本全部都是先按需求写代码，写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑，逻辑也很混乱。看来还是太年轻了。




有用  |  无用

猜你喜欢

您可能感兴趣的文章: