JavaScript數據結構與算法——鏈表

chunquedong 發布于2019-08-23 15:14 / 2076人閱讀

摘要：鏈表數據結構鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素咋內存中并不是連續放置的每個元素有一個存儲元素本身的節點和一個指向下一個元素的引用組成。

1.鏈表數據結構

鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素咋內存中并不是連續放置的每個元素有一個存儲元素本身的節點和一個指向下一個元素的引用組成。下圖展示了一個鏈表的結構：

鏈表的優點：
鏈表是很常用的一種數據結構，不需要初始化容量，可以任意加減元素；
添加或者刪除元素時只需要改變前后兩個元素結點的指針域指向地址即可，所以添加，刪除很快；

缺點：
因為含有大量的指針域，占用空間較大；
查找元素需要遍歷鏈表來查找，非常耗時。

適用場景：
數據量較小，需要頻繁增加，刪除操作的場景

2.創建鏈表

function LinkedList() {
    // 創建一個node類，表示將要加入的項 element表示要添加的值，next指向列表中下一個節點項的指針
    let Node = function(element) {
        this.element = element;
        this.next = null;
    }
    let length = 0;
    let head = null;
    // 下面聲明鏈表的方法
    // 1.向列表尾部添加一個新的項
    this.append = function(element) {
        let 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++;
    }
    // 2.從列表中移除元素
    this.removeAt = function(position) {
        // 檢查position是否超出鏈表范圍
        if(position > -1 && position < length) {
            let current = head,
                previous,
                index = 0;
            // 移除第一個元素
            if(position === 0 ) {
                head = current.next;
            } else {
                // 循環到指定位置，找到該位置的 previous和current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 將previous與current的下一項鏈接起來：跳過current
                previous.next = current.next;
            }    
            // 鏈表長度減一
            length--;
            // 返回被刪除項
            return current.element;
        } else {
            // 不是有效位置，返回null
            return null
        }
    }
     // 3.在任意位置插入元素
    this.insert = function(element, position) {
        //判斷是否超過鏈表范圍
        if (position >= 0 && position<= length) {
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            // 在首位插入元素
            if (position === 0 ) {
                node.next = current;
                head = node;
            } else{
                // x循環到position應該添加的位置，取出previous和current
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 在previous和current間插入
                node.next = current;
                previous.next = node;
            };    
            // 更新鏈表長度
            length++;
            return true;
        } else{
            return false;
        };
    }
    //4. 把LinkedList對象轉化成字符串
    this.toString = function() {
        let current = head,
            string = "";
        while(current) {
            string += current.element + (current.next ? "n" : "");
            current = current.next;
        }  
        return string;  
    }
    //5.鏈表中是否存在某個值
    this.indexOf = function(element) {
        let current = head,
            index = 0;
        while(current) {
            if(element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }  
        return -1; 
    } 
    //6.通過element實現remove元素
    this.remove = function(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }
    //7.isEmpty size getHead方法
    this.isEmpty = function() {
        return length === 0; 
    }
    this.size = function() {
        return length;
    }
    this.getHead = function() {
        return head;
    }    
}

云服務器 GPU云服務器鏈表算法鏈表排序算法算法 c語言鏈表算法與數據結構

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101731.html

學習JavaScript數據結構與算法（二）：鏈表

摘要：實現移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數據結構與算法二鏈表本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第四篇文章：學習JavaScript數據結構與...

lolomaco 2019-08-22 11:00 評論0 收藏0
JavaScript的數據結構與算法（四） —— 雙向鏈表

摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或...

Youngdze 2019-08-21 17:13 評論0 收藏0
《Javascript數據結構和算法》筆記-「鏈表」

摘要：鏈表數據結構與算法第五章鏈表數據結構鏈表不同與數組數組要插入或者移入一個元素的成本很高，因為所有元素都需要移動位置。 JavaScript-鏈表《Javascript數據結構與算法》第五章 5.1 鏈表數據結構鏈表不同與數組數組要插入或者移入一個元素的成本很高，因為所有元素都需要移動位置。鏈表插入或者移動一個元素時很高效，因為并不需要移動其他的元素位置。鏈表存儲元素的方式...

gclove 2019-08-26 13:22 評論0 收藏0
Javascript數據結構與算法（二）循環鏈表與有序鏈表

摘要：循環鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。以下就以如何創建棧數據結構為例。循環鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。性能上也跟雙向鏈表差不多，如果position大于length/2，那就可以從尾部開始迭代，可以減少迭代的元素。唯一的區別在于最后一個元素指向下一個元素的指針(tail.next)不是undefine，而是第一個元素（head）。接下來來看一...

YacaToy 2019-08-26 10:49 評論0 收藏0
JavaScript的數據結構與算法（三） —— 單向鏈表

摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。相對于傳統的數組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。...

李濤 2019-08-21 17:14 評論0 收藏0