資訊專欄INFORMATION COLUMN
摘要：鏈表前端的面試中，鏈表還是經常會被問到。這種數據結構非常方便，提供了便利店語法來訪問它的元素。參考書籍推薦一個找組件的輪子工廠前端面試總結數據結構與算法一前端面試總結數據結構與算法二前端面試總結數據結構與算法三
鏈表
前端的面試中，鏈表還是經常會被問到。所以熟悉鏈表的結果以及鏈表操作的方法還是很重要的。
說道存儲多個元素，數組可能是最常用的數據結構。這種數據結構非常方便，提供了便利店[]語法來訪問它的元素。但是數組的缺點就是對元素進行插入或者刪除操作的成本很高，需要移動元素。
鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用組成。鏈表的一個好處在于，增加或刪除元素的時候不需要移動其它元素。數組的另一個細節是可以直接訪問任何位置的任何元素，而要訪問鏈表中間的一個元素，需要從起點開始迭代列表直到找到所需的元素。
function LinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
}
鏈表的方法
append(element) -- 向鏈表尾部添加一個新的項
insert(position, element) -- 向鏈表的特定位置插入一個新的項
remove(element) -- 從鏈表中移除元素
indexOf(element) -- 返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回-1
removeAt(position) -- 從鏈表的特定位置移除一項
isEmpty() -- 如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0返回false
size() -- 返回鏈表包含的元素個數
function LinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
this.append = function(element){
var node = new Node(element),current;
if(head === null){
head = node;
} else {
current = head;
//循環列表，直到最后一項
while(current.next){
current = current.next;
}
//找到最后一項，將其next賦值為node
current.next = node;
}
length++;
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if(position === 0){
head = current.next;
} else {
while(index++ < pisition){
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
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;
}
previous.next =node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
this.indexOf = function(element){
var current = head, index = 0;
while(current){
if(element === current.element){
return index;
}
index++;
current = current.next;
}
return -1;
};
this.remove = function(element){
var index = this.indexOf(element);
return this.removeAt(index);
}
this.isEmpty = function(){
return length === 0;
}
this.size = function(){
return length;
}
this.getHead = function(){
return head;
}
}
雙向鏈表
雙向鏈表和普通鏈表的區別在于，在鏈表中，一個節點只有鏈向下一個節點的鏈接，而在雙向鏈表中，鏈接是雙向的。
function DoublyLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0;
var head = null;
var tail = null;
this.insert = function(position, element){
if(position >= 0 && position <= length){
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
if(!head){
head = node;
tail = node;
} else {
node.next = current;
current.previous = node;
head = node;
}
} else if(position === length){
current = tail;
current.next = node;
node.previous = current;
tail = node;
} else {
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
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;
if(length === 1){
tail = null;
} else {
head.prev = null;
}
} else if(position === length-1){
current = tail;
tail = current.prev;
tail.next = null;
} else {
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return null;
}
}
}
參考書籍：Learning Javascript Data Structures and Algorithms
推薦一個找vue,angular組件的輪子工廠
前端面試總結--數據結構與算法一
前端面試總結--數據結構與算法二
前端面試總結--數據結構與算法三
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/88499.html
摘要：結構的實例的方法，用于對每個成員執行某種操作，沒有返回值。參考和數據結構推薦一個找組件的輪子工廠前端面試總結數據結構與算法一前端面試總結數據結構與算法二前端面試總結數據結構與算法三前端面試總結數據結構與算法四 集合 集合是由一組無序且唯一的項組成。這個數據結構使用了與有限集合相同的數學概念。 創建一個集合 function Set(){ var items = {}; } ...
摘要：不過幸運的是所有面試的公司都給了，在這里總結下經驗吧。這里推薦下我當時看的一篇的面經，木易楊老師寫的大廠高級前端面試題匯總。 前言 本人畢業一年，最近陸續面試了頭條、瓜子、360、猿輔導、中信銀行、老虎等公司，由于最近比較寒冬而且招1-3年的并不多，再加上自己對公司規模和位置有一定要求，所以最后合適的也就這幾家了。不過幸運的是所有面試的公司都給了offer，在這里總結下經驗吧。掘金：h...
閱讀 2505·2023-04-25 19:31
閱讀 2239·2021-11-04 16:11
閱讀 2805·2021-10-08 10:05
閱讀 1515·2021-09-30 09:48
閱讀 2315·2019-08-30 15:56
閱讀 2406·2019-08-30 15:56
閱讀 2174·2019-08-30 15:53
閱讀 2268·2019-08-30 15:44
