线性表

定义

线性结构的特点：
除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素。
主要操作特点：
可以在任意位置插入和删除一个数据元素。

抽象数据类型

数据集合

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

属性

方法集合

顺序表

顺序存储结构的线性表称作顺序表。

存储结构

function List() {
    this.listSize = 0;
    this.pos = 0;
    
    this.dataStore = []; // 初始化一个空数组来保存列表元素
    this.append = append;
    this.find = find;
    this.remove = remove;
    this.toString = toString;
    this.insert = insert;
    this.clear = clear;
    this.length = length;
}

操作实现

1、append： 给列表添加元素

该方法给列表的下一个位置增加一个新的元素， 这个位置刚好等于变量 listSize 的值：

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

当新元素就位后， 变量 listSize 加 1。

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

find() 方法通过对数组对象 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() 方法返回的位置对数组 dataStore 进行截取。 数组改变后， 将变量 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 操作符删除数组 dataStore， 接着在下一行创建一个空数组。 最
后一行将 listSize 和 pos 的值设为 0， 表明这是一个新的空列表。

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

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

function length() {
    return this.listSize;
}

链表

单链表

设计的链表包含两个类。
Node 类用来表示节点， LinkedList 类提供了插入节点、 删除节点、 显示列表元素的方法， 以及其他一些辅助方法。

结点定义：Node类

Node 类包含两个属性： element 用来保存节点上的数据， next 用来保存指向下一个节点的链接。

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

存储结构：LinkedList类

构造函数， 链表只有一个属性， 那就是使用一个 Node 对象来保存该链表的头节点。

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

head 节点的 next 属性被初始化为 null， 当有新元素插入时， next 会指向新的元素。

操作实现：

LList 类提供了对链表进行操作的方法。

1、find：遍历链表， 查找给定数据

创建一个新节点， 并将链表的头节点赋给这个新创建的节点。 然后在链表上进行循环， 如果当前节点的 element 属性和我们要找的信息不符， 就从当前节点移动到下一个节点。 如果查找成功， 该方法返回包含该数据的节点； 否则， 返回头结点。

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

2、insert：向链表中插入一个节点

向链表中插入新节点时， 需要明确指出要在哪个节点前面或后面插入。
这里的代码给出的是在一个已知节点后面插入元素，因此需要找到“后面” 的节点。

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

3、length：求当前数据元素个数

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

4、remove：从链表中删除一个节点

从链表中删除节点时， 需要先找到待删除节点前面的节点。 找到这个节点后， 修改它的next 属性， 使其不再指向待删除节点， 而是指向待删除节点的下一个节点。

function remove(item){
    var prevNode = this.head;
    //找到待删除节点前面的节点
    while (!(prevNode.next == null) && (prevNode.next.element != item)) {
        prevNode = prevNode.next;
    }   
    if (!(prevNode.next == null)) {
        prevNode.next = prevNode.next.next;
    }
}