線性表

定義

線性結構的特點：
除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素。
主要操作特點：
可以在任意位置插入和刪除一個數(shù)據(jù)元素。

抽象數(shù)據(jù)類型

數(shù)據(jù)集合

$[a_0,a_1,a_2,...,a_{n-1}]$

屬性

方法集合

順序表

順序存儲結構的線性表稱作順序表。

存儲結構

function List() {
    this.listSize = 0;
    this.pos = 0;
    
    this.dataStore = []; // 初始化一個空數(shù)組來保存列表元素
    this.append = append;
    this.find = find;
    this.remove = remove;
    this.toString = toString;
    this.insert = insert;
    this.clear = clear;
    this.length = length;
}

操作實現(xiàn)

1、append： 給列表添加元素

該方法給列表的下一個位置增加一個新的元素， 這個位置剛好等于變量 listSize 的值：

function append(element) {
    this.dataStore[this.listSize++] = element;
}

當新元素就位后， 變量 listSize 加 1。

2、find： 在列表中查找某一元素

find() 方法通過對數(shù)組對象 dataStore 進行迭代， 查找給定的元素。 如果找到， 就返回該元素在列表中的位置， 否則返回 -1。

function find(element) {
    for (var i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return i;
        }
    } 
    return -1;
}

3、remove： 從列表中刪除元素

remove() 方法使用 find() 方法返回的位置對數(shù)組 dataStore 進行截取。 數(shù)組改變后， 將變量 listSize 的值減 1， 以反映列表的最新長度。 如果元素刪除成功， 該方法返回 true， 否則返回 false。

function remove(element) {
    var foundPos = this.find(element);
    if (foundAt > -1) {
        this.dataStore.splice(foundPos,1);
        --this.listSize;
        return true;
    } 
    return false;
}

4、toString： 顯示列表中的元素

function toString() {
    return this.dataStore;
}

5、insert： 向列表中插入一個元素

function insert(element, after) {
    var insertPos = this.find(after);
    if (insertPos > -1) {
        this.dataStore.splice(insertPos+1, 0, element);
        ++this.listSize;
        return true;
    } 
    return false;
}

6、clear： 清空列表中所有的元素

使用 delete 操作符刪除數(shù)組 dataStore， 接著在下一行創(chuàng)建一個空數(shù)組。 最
后一行將 listSize 和 pos 的值設為 0， 表明這是一個新的空列表。

function clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = this.pos = 0;
}

7、length： 列表中有多少個元素

function length() {
    return this.listSize;
}

鏈表

單鏈表

設計的鏈表包含兩個類。
Node 類用來表示節(jié)點， LinkedList 類提供了插入節(jié)點、 刪除節(jié)點、 顯示列表元素的方法， 以及其他一些輔助方法。

結點定義：Node類

Node 類包含兩個屬性： element 用來保存節(jié)點上的數(shù)據(jù)， next 用來保存指向下一個節(jié)點的鏈接。

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

存儲結構：LinkedList類

構造函數(shù)， 鏈表只有一個屬性， 那就是使用一個 Node 對象來保存該鏈表的頭節(jié)點。

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

head 節(jié)點的 next 屬性被初始化為 null， 當有新元素插入時， next 會指向新的元素。

操作實現(xiàn)：

LList 類提供了對鏈表進行操作的方法。

1、find：遍歷鏈表， 查找給定數(shù)據(jù)

創(chuàng)建一個新節(jié)點， 并將鏈表的頭節(jié)點賦給這個新創(chuàng)建的節(jié)點。 然后在鏈表上進行循環(huán)， 如果當前節(jié)點的 element 屬性和我們要找的信息不符， 就從當前節(jié)點移動到下一個節(jié)點。 如果查找成功， 該方法返回包含該數(shù)據(jù)的節(jié)點； 否則， 返回頭結點。

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

2、insert：向鏈表中插入一個節(jié)點

向鏈表中插入新節(jié)點時， 需要明確指出要在哪個節(jié)點前面或后面插入。
這里的代碼給出的是在一個已知節(jié)點后面插入元素，因此需要找到“后面” 的節(jié)點。

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

3、length：求當前數(shù)據(jù)元素個數(shù)

function length(){
    var current = this.head;
    var listsize = 0;
    while(current.next != null){
        current = current.next;
        ++listsiez;
    }
    return listsize; 
}

4、remove：從鏈表中刪除一個節(jié)點

從鏈表中刪除節(jié)點時， 需要先找到待刪除節(jié)點前面的節(jié)點。 找到這個節(jié)點后， 修改它的next 屬性， 使其不再指向待刪除節(jié)點， 而是指向待刪除節(jié)點的下一個節(jié)點。

function remove(item){
    var prevNode = this.head;
    //找到待刪除節(jié)點前面的節(jié)點
    while (!(prevNode.next == null) && (prevNode.next.element != item)) {
        prevNode = prevNode.next;
    }   
    if (!(prevNode.next == null)) {
        prevNode.next = prevNode.next.next;
    }
}