摘要：鏈表前端的面試中，鏈表還是經(jīng)常會(huì)被問到。這種數(shù)據(jù)結(jié)構(gòu)非常方便，提供了便利店語法來訪問它的元素。參考書籍推薦一個(gè)找組件的輪子工廠前端面試總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法一前端面試總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法二前端面試總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法三

前端的面試中，鏈表還是經(jīng)常會(huì)被問到。所以熟悉鏈表的結(jié)果以及鏈表操作的方法還是很重要的。
說道存儲(chǔ)多個(gè)元素，數(shù)組可能是最常用的數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)非常方便，提供了便利店[]語法來訪問它的元素。但是數(shù)組的缺點(diǎn)就是對(duì)元素進(jìn)行插入或者刪除操作的成本很高，需要移動(dòng)元素。
鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成。鏈表的一個(gè)好處在于，增加或刪除元素的時(shí)候不需要移動(dòng)其它元素。數(shù)組的另一個(gè)細(xì)節(jié)是可以直接訪問任何位置的任何元素，而要訪問鏈表中間的一個(gè)元素，需要從起點(diǎn)開始迭代列表直到找到所需的元素。

function LinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
    }
    var length = 0;
    var head = null;
}

append(element) -- 向鏈表尾部添加一個(gè)新的項(xiàng)
insert(position, element) -- 向鏈表的特定位置插入一個(gè)新的項(xiàng)
remove(element) -- 從鏈表中移除元素
indexOf(element) -- 返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回-1
removeAt(position) -- 從鏈表的特定位置移除一項(xiàng)
isEmpty() -- 如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0返回false
size() -- 返回鏈表包含的元素個(gè)數(shù)

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;
               //循環(huán)列表，直到最后一項(xiàng)
               while(current.next){
                   current = current.next;
               }
               //找到最后一項(xiàng)，將其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;
       }
       
 }
 

雙向鏈表和普通鏈表的區(qū)別在于，在鏈表中，一個(gè)節(jié)點(diǎn)只有鏈向下一個(gè)節(jié)點(diǎn)的鏈接，而在雙向鏈表中，鏈接是雙向的。

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

推薦一個(gè)找vue,angular組件的輪子工廠

前端面試總結(jié)--數(shù)據(jù)結(jié)構(gòu)與算法一
前端面試總結(jié)--數(shù)據(jù)結(jié)構(gòu)與算法二
前端面試總結(jié)--數(shù)據(jù)結(jié)構(gòu)與算法三