javascript中的鏈表結構—雙向鏈表

1.概念

　　上一個文章里我們已經了解到鏈表結構，鏈表的特點是長度不固定，不用擔心插入新元素的時候新增位置的問題。插入一個元素的時候，只要找到插入點就可以了，不需要整體移動整個結構。

　　這里我們了解一下雙向鏈表的結構。盡管從鏈表中頭節點遍歷到尾節點很容易，但是反過來，從后向前遍歷就沒有那么簡單。通過給Node對象增加一個屬性，該屬性存儲指向前驅節點的鏈接，這樣就容易多了。此時祥鏈表中插入一個節點需要更多的工作，我們需要指出該節點正確的前驅和后續。但是在從鏈表中刪除節點的時候效率更高了，不需要再查找待刪除節點的前驅節點了。如下圖1演示了雙向鏈表的工作原理。

圖1

首先是要為Node類增加一個previouse屬性，這個屬性指向當前節點的前驅：

function Node(element){
    this.element = element;
    this.next = null;
    this.previous = null;
}

　　雙向鏈表的insert()方法和單項鏈表的類似，但是需要設置新節點的previouse屬性，是其指向該節點的前驅。該方法的定義如下：

function insert(newElement , item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}

　　雙向鏈表的刪除remove()方法幣單項鏈表的效率更高，因為不需要查找前驅節點了。首選需要在鏈表中找出存儲待刪除數據的節點，然后設置該節點的next屬性，使其指向待刪除節點的后續。設置該節點的后續的previouse的屬性，使其指向待刪除節點的前驅。如下圖2展示刪除節點的過程：

圖2

remove()方法的定義如下：

function remove(item){
    var currNode = this.find(item);
    if(!(currNode.next == null)){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

　　為了實現反向顯示鏈表中元素的任務，需要給鏈表增加一個工具方法，用來查找鏈表中最后一個節點。findLast()方法找出鏈表中最后一個節點，同時免除從前往后遍歷之苦。如下：

function findLast(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        currNode = currNode.next;
    }
    return currNode;
}

　　有了這個工具方法之后就，就可以很容易的寫出反向顯示雙向鏈表的元素的方法，dispReverse()方法如下所示：

function dispReverse(){
    var currNode = this.head;
    currNode = this.findLast();
    while (!(currNode.previous == null)){
        document.write(currNode.element + '&nbsp;');
        currNode = currNode.previous;
    }
}

2.代碼實現

　　雙向鏈表就上面一些特性，下面是完整的代碼實現和測試代碼：

function Node(element){
    this.element = element;
    this.next = null;
    this.previous = null;
}

function LList(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.remove = remove;
    this.findLast = findLast;
    this.dispReverse = dispReverse;
}

function dispReverse(){
    var currNode = this.head;
    currNode = this.findLast();
    while (!(currNode.previous == null)){
        document.write(currNode.element + '&nbsp;');
        currNode = currNode.previous;
    }
}

function findLast(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        currNode = currNode.next;
    }
    return currNode;
}

function remove(item){
    var currNode = this.find(item);
    if(!(currNode.next == null)){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

function display(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        document.write(currNode.next.element + '&nbsp;');
        currNode = currNode.next;
    }
}

function find(item){
    var currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

function insert(newElement , item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}


var cities = new LList();
cities.insert('Conway','head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma' , 'Carlisle');
cities.display();
document.write('<br>');
cities.remove('Carlisle');
cities.display();
document.write('<br>');
cities.dispReverse();

posted @ 2016-09-21 23:58 nd 閱讀(3947) 評論(0) 收藏舉報

刷新頁面返回頂部

javascript中的鏈表結構—雙向鏈表

公告