鏈表

語雀入口

　https://www.yuque.com/along-n3gko/ezt5z9

介紹

　　要存盤多個元素，一般都會選擇陣列，但是這種資料結構有一個缺點：一般陣列的大小都是固定的，從陣列的起點或中間插入或移除元素成本有點高，這時候就可以選擇鏈表，

鏈表存盤有序的元素集合，但不同于陣列，鏈表的元素在記憶體中不是連續放置的，每個元素由一個存盤元素本身的節點個指向下一個元素的參考組成，

　　相對于傳統的陣列，鏈表的一個好處在于，添加或移除元素的時候不需要移動其他元素，然 而，鏈表需要使用指標，因此實作鏈表時需要額外注意，陣列的另一個細節是可以直接訪問任何 位置的任何元素，而要想訪問鏈表中間的一個元素，需要從起點（表頭）開始迭代串列直到找到所需的元素，

創建鏈表

 1 function LinkedList() { 
 2  let Node = function(element){ // Node輔助類,要加入串列的項，element要加入的值，next表示指向串列下一個節點 
 3         this.element = element; 
 4         this.next = null; 
 5  }; 
 6  let length = 0; // 存盤串列項數量
 7  let head = null; // 存盤第一個節點的參考，存到變數head中， 
 8  this.append = function(element){}; //向串列項尾部添加新的項
 9  this.insert = function(position, element){}; //向串列指定位置插入新的項
10  this.removeAt = function(position){}; //從串列特定位置移除一項
11  this.remove = function(element){}; //從串列中移除一項
12  this.indexOf = function(element){}; //回傳元素在串列的索引,沒有則回傳-1
13  this.isEmpty = function() {}; //如果鏈表中不包含任何元素，回傳true，如果鏈表長度大于0，則回傳false
14  this.size = function() {}; //回傳鏈表的長度
15  this.getHead = function(){}; 
16  this.toString = function(){}; //輸入鏈表元素值
17  this.print = function(){}; 
18 }

向鏈表尾部添加元素

　　兩種場景：串列為空，添加的是第一個元素；串列不為空，向其追加元素

 1 this.append = function (element) {
 2     let node = new Node(element), //傳入element值，作為Node項 
 3         current; //{2} 
 4     if (head === null) { //串列中第一個節點為空時，此時head指向node
 5         head = node;
 6     } else {
 7         current = head;
 8         //回圈串列，直到找到最后一項
 9         while (current.next) {
10             current = current.next;
11         }
12         //找到最后一項，將其next賦為node，建立鏈接
13         current.next = node;
14     }
15     length++; //更新串列的長度
16 };

從鏈表中移除元素

　　兩種場景：移除第一個元素；移除第一個以外的元素，

 1 this.removeAt = function (position) {
 2     //檢查越界值
 3     if (position > -1 && position < length) {
 4         let current = head,
 5             previous,
 6             index = 0;
 7         //移除第一項
 8         if (position === 0) {
 9             head = current.next;
10         } else {
11             while (index++ < position) {
12                 previous = current;
13                 current = current.next;
14             }
15             //將previous與current的下一項鏈接起來：跳過current，從而移除它
16             previous.next = current.next;
17         }
18         length--;
19         return current.element;
20     } else {
21         return null;
22     }
23 };

在任意位置插入元素

 1 this.insert = function (position, element) {
 2     //檢查越界值
 3     if (position >= 0 && position <= length) { 
 4         let node = new Node(element),
 5             current = head,
 6             previous,
 7             index = 0;
 8         if (position === 0) { //在第一個位置添加
 9             node.next = current;  
10             head = node;
11         } else {
12             while (index++ < position) {
13                 previous = current;
14                 current = current.next;
15             }
16             node.next = current; 
17             previous.next = node;
18         }
19         length++; //更新串列的長度
20         return true;
21     } else {
22         return false; 
23     }
24 };

toString方法

1 this.toString = function () {
2     let current = head,
3         string = '';  
4     while (current) {
5         string += current.element + (current.next ? 'n' : ''); 
6         current = current.next; 
7     }
8     return string;
9 };

indexOf方法

 1 this.indexOf = function (element) {
 2     let current = head,
 3         index = -1;
 4     while (current) {
 5         if (element === current.element) {
 6             return index; 
 7         }
 8         index++; 
 9         current = current.next; 
10     }
11     return -1;
12 };

isEmpoty方法

1 this.isEmpty = function() { 
2         return length === 0; 
3 };

size方法

1 this.size = function() { 
2         return length; 
3 };

getHead方法

1 this.getHead = function(){ 
2         return head; 
3 };

標籤：JavaScript

上一篇：佇列

下一篇：字典