JavaScript的數據結構與算法（四） —— 雙向鏈表

Youngdze 發布于2019-08-21 17:13 / 526人閱讀

摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。

鏈表

鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或者刪除元素的時候不需要移動其他元素。
使用鏈表結構可以克服數組需要預先知道數據大小的缺點(C語言的數組需要預先定義長度)，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。

數組和鏈表的一個不同在于數組可以直接訪問任何位置的元素，而想要訪問鏈表中的一個元素，需要從起點開始迭代列表。

鏈表又包括：單向鏈表和雙向鏈表；

雙向鏈表

雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個節點的鏈接。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。

讓我們來簡單實現一個雙向鏈表類，并包含如下功能：

append(element): 添加元素到鏈表尾部

insert(position,element): 向雙向鏈表中某個位置插入元素

removeAt(position): 移除雙向鏈表中某個位置的元素

getHead(): 獲取雙向鏈表的頭部

getTail(): 獲取雙向鏈表的尾部

isEmpty(): 檢查雙向鏈表是否為空，為空則返回true

size(): 返回雙向鏈表長度

代碼如下：

   function DoublyLinkedList() {
    /**
     * 雙向鏈表中節點的構造函數
     * 
     * @param {any} element 要插入鏈表的元素
     */
    var Node = function (element) {
        this.element = element;
        this.next = null;
        this.prev = null;
    }

    // 雙向鏈表的長度
    var length = 0;
    // 雙向鏈表的頭結點，默認為null
    var head = null;
    // 雙向鏈表的尾結點，默認為null
    var tail = null;
    
    /**
     * 添加元素到雙向鏈表的尾部
     * 
     * @param {any} element 要插入的元素
     */
    this.append = function (element) {
        var node = new Node(element),
            current = head;

        if (head === null) {
            head = node
            tail = node
        } else {
            while (current.next) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;
            tail = node;
        }
        length++;
        return true;
    }


    /**
     * 向雙向鏈表中某個位置插入元素
     * 
     * @param {any} position 要插入的位置
     * @param {any} element 要插入的元素
     * @returns 插入成功或失敗
     */
    this.insert = function (position, element) {
        var node = new Node(element),
            current = head,
            previous,
            index = 0;
        // 限制邊界
        if (position < 0 && position >= length) {
            return false;
        }

        if (position === 0) {
            // 在鏈表的頭部插入元素
            node.next = head
            head.prev = node
            head = node
        } else if (position === length) {
            // 在鏈表的尾部插入元素
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        } else {
            // 在鏈表的中間插入元素
            while (index++ < position) {
                previous = current
                current = current.next;
            }
            // 綁定前一個節點和插入節點的關系
            previous.next = node;
            node.prev = previous;
            // 綁定后一個節點和插入節點的關系
            node.next = current;
            current.prev = node;
        }
        length++;
        return true;
    }

    /**
     * 移除雙向鏈表中某個位置的元素
     * 
     * @param {any} position 要移除元素的位置
     * @returns 移除成功，返回移除的元素
     */
    this.removeAt = function (position) {
        var previous,
            current = head,
            index = 0;
         // 限制邊界
         if (position < 0 && position >= length) {
            return false;
        }

        if (position === 0) {
            // 移除鏈表的頭部
            head = current.next;
            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;
    }

    this.getHead = function () {
        return head.element;
    }

    this.isEmpty = function () {
        return length === 0
    }

    this.getTail = function () {
        
        return tail.element;
    }

    this.size = function () {
        return length
    }
}

云服務器 GPU云服務器雙向鏈表 java雙向鏈表描述的數據結構與算法鏈表算法

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

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

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

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

lolomaco 2019-08-22 11:00 評論0 收藏0
javascript數據結構與算法（一）單向鏈表與雙向鏈表

摘要：創建雙向鏈表創建節點繼承添加前繼指針初始化雙向鏈表對鏈表最后一個元素進行引用插入操作尾插法任意位置添加元素刪除操作刪除特定位置的元素查詢操作查詢元素的位置查詢尾部元素修改操作清空雙向鏈表雙向鏈表對象轉為字符串線性表（List）：零個或者多個數據元素的有限序列。線性表是一個序列，具有一對一的關系，而不能具備一對多的關系。線性表要求有限性，數據類型也要相同。本文參考的主要是大話數據結構...

William_Sang 2019-08-26 10:48 評論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 數據結構與算法之美 - 線性表（數組、棧、隊列、鏈表）

摘要：每個線性表上的數據最多只有前和后兩個方向。數組鏈表隊列棧等就是線性表結構。非線性表數據之間并不是簡單的前后關系。不包含任何元素的棧稱為空棧。移除棧頂的元素，同時返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言基礎知識就像是一座大樓的地基，它決定了我們的技術高度。我們應該多掌握一些可移值的...

kaka 2019-08-23 18:25 評論0 收藏0