本文主要介紹了JavaScript資料結構之單鍊錶、循環鍊錶，詳細的介紹了JavaScript如何實現單鍊錶、循環鍊錶，有興趣的可以了解一下，希望能幫助到大家。
進入正題，關於鍊錶的資料結構知識，這裡簡單介紹下：
鍊錶是一種物理儲存單元上非線性、非連續性的資料結構（它在資料邏輯上是線性的），它的每個節點由兩個域組成：資料域和指標域。資料域中儲存實際數據，指標域則儲存指標訊息，指向鍊錶中的下一個元素或上一個元素。正是由於指標的存在，鍊錶的儲存在物理單元是非連續性的。
鍊錶的優點和缺點同樣明顯。和線性表相比，鍊錶在新增和刪除節點上的效率更高，因為其只需要修改指標資訊即可完成操作，而不是像線性表（陣列）那樣需要移動元素。同樣的，鍊錶的長度在理論上也是無限的（在記憶體容量範圍內），並且可以動態變化長度，相比線性表優勢很大。 對應的，由於線性表無法隨機存取節點，只能透過指標順著鍊錶進行遍歷查詢來訪問，故其存取資料元素的效率比較低。
下面是JS部分
這裡面封裝了的常用方法及描述：
##方法 | 描述 |
append(element) | 新增結點element |
##insert(position,element)
| 向位置position處插入結點element |
|
removeAt(position)
| 依照索引值position刪除結點 |
|
#remove(element)
| 搜尋並刪除給定結點element |
|
remove()
| 刪除鍊錶中最後一個結點 |
|
indexOf(element)
| 找出並傳回給定結點element的索引值 |
|
isEmpty()
| 判斷鍊錶是否為空 |
|
size()
| # 取得鍊錶長度 |
| ##toString()
轉換為字串輸出 |
| getHead()
#取得頭結點 |
| getTail()
取得尾結點 |
|
對於各常用方法的演算法描述在這裡就不寫了，相信大家都可以輕易讀懂並理解，畢竟都是非常基礎的知識了。
單鍊錶：
function LinkedList(){
/*节点定义*/
var Node = function(element){
this.element = element; //存放节点内容
this.next = null; //指针
}
var length = 0, //存放链表长度
head = null; //头指针
this.append = function(element){
var node = new Node(element),
current; //操作所用指针
if (!head){
head = node;
}else {
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
length++;
return true;
};
this.insert = function(position, element){
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
node.next = current;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
};
length--;
return current.element;
}else{
return null;
}
};
this.remove = function(element){
var current = head,
previous;
if(element === current.element){
head = current.next;
length--;
return true;
}
previous = current;
current = current.next;
while(current){
if(element === current.element){
previous.next = current.next;
length--;
return true;
}else{
previous = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if(length < 1){
return false;
}
var current = head,
previous;
if(length == 1){
head = null;
length--;
return current.element;
}
while(current.next !== null){
previous = current;
current = current.next;
}
previous.next = null;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current){
if(element === current.element){
return index;
}
index++;
current = current.next;
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '';
while(current){
string += current.element;
current = current.next;
}
return string;
};
this.getHead = function(){
return head;
}
}登入後複製
循環鍊錶：在單鍊錶的基礎上，將尾節點的指標指向頭結點，就構成了一個循環鍊錶。環形鍊錶從任一個節點開始，都可以遍歷整個鍊錶。
function CircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0,
head = null;
this.append = function(element){
var node = new Node(element),
current;
if (!head) {
head = node;
node.next = head;
}else{
current = head;
while(current.next !== head){
current = current.next;
}
current.next = node;
node.next = head;
};
length++;
return true;
};
this.insert = function(position, element){
if(position > -1 && position < length){
var node = new Node(element),
index = 0,
current = head,
previous;
if (position === 0) {
node.next = head;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
};
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
};
length--;
return current.element;
}else{
return null;
}
};
this.remove = function (element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck == 0){
head = current.next;
length--;
return true;
}else{
previous.next = current.next;
length--;
return true;
}
}else{
previous = current;
current = current.next;
indexCheck++;
}
}
return false;
};
this.remove = function(){
if(length === 0){
return false;
}
var current = head,
previous,
indexCheck = 0;
if(length === 1){
head = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index < length){
if(current.element === element){
return index;
}else{
index++;
current = current.next;
}
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '',
indexCheck = 0;
while(current && indexCheck < length){
string += current.element;
current = current.next;
indexCheck++;
}
return string;
};
}登入後複製
使用方法：
#在類別外部擴充方法：
相關推薦：
JavaScript資料結構中雙向鍊錶的使用定義的範例
JavaScript資料結構中優先佇列與循環佇列
JavaScript資料結構之二元查找樹的定義與表示方法詳解
以上是JavaScript資料結構之單鍊錶與循環鍊錶實例分享的詳細內容。更多資訊請關注PHP中文網其他相關文章！
