鏈表簡介
鏈表是一種常見的數據結構，也屬于線性表，但不會按線性的順序來儲存數據。而是在每一個節點中，儲存了下一個節點的指針。可以看圖理解。(有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;}不難看出，單向鏈表構造函數比棧與隊列要復雜許多。
單向鏈表需要有如下的方法:
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;}雙向鏈表需要有如下的方法:
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;};感想
鏈表這一節，基本全部都是先按需求寫代碼，寫完后再和書上對比。發現簡直被瞬間秒成渣。自己寫的很多暗坑，邏輯也很混亂。看來還是太年輕了。
新聞熱點
疑難解答
