不冒任何險，什么也不會有，什么也不是。

javascript中的鏈表結構—從鏈表中刪除元素

1.概念

　　上一個博文我們講到鏈表，其中有一個方法remove()是暫時注釋的，這個方法有點復雜，需要添加一個Previous()方法找到要刪除的元素的前一個節點，這一個博文我們來分析一下這個remove()方法。

　　從鏈表中刪除節點的時候，需要先找到這個待刪除節點的前面的節點。找到這個節點之后修改它的next屬性，使其指向待刪除節點的下一個節點，這樣就把待刪除節點給刪除了，是不是很簡單呢？但是問題來了，我們是不是要找到待刪除節點的前面一個節點呢？這樣就需要添加一個findPrevious()方法來做這件事情。

　　findPrevious()方法遍歷鏈表中的元素，檢查每一個節點的下一個節點是否存儲著待刪除數據。如果找到，返回該節點（即前面的節點），這樣就可以修改它的next屬性了。findPrevious()方法定義如下：

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

　　有了這個findPrevious()方法之后就可以考慮如何寫這個remove()方法了。代碼如下：

function remove(item){
    var preNode = this.findPrevious(item);
    if(preNode.next != null){
        preNode.next = preNode.next.next;
    }
}

該方法中有一句preNode.next = preNode.next.next;這個使用了javascript中的對象屬性，看起來有點奇怪，但是完全能說得通。

2.代碼實現

下面的是完整的代碼和測試代碼：

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

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

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;
    current.next = newNode;
}

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

function remove(item){
    var preNode = this.findPrevious(item);
    if(preNode.next != null){
        preNode.next = preNode.next.next;
    }
}

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

//測試程序
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlise", "Russellville");
cities.insert("Alma", "Carlise");
cities.display();
document.write('<br>');
cities.remove('Carlise');
cities.display();

最后的輸出結果如下：

posted @ 2016-09-19 23:33 nd 閱讀(1888) 評論(0) 收藏舉報

刷新頁面返回頂部

javascript中的鏈表結構—從鏈表中刪除元素

公告