JavaScript常用数据结构之线性表：数组和链表

线性表是最基本的数据结构，线性表是指的数据一对一的关系，其数据组织的形式是线性的，线性指的是逻辑上结构。数组和链表是最常用两个线性表，但是它们的物理结构是不同的，也就是说数组和链表在内存中的表示并不相同，数组属于顺序结构，链表属于链式结构，关于线性表的更多内容可以查看：线性表、栈和队列实现原理，这篇文章有深入的解析。

一、JavaScript线性表：数组

如上图是一个数组在内存中的表示，数组的元素地址在内存中是连续的，数组存储多个相同类型的数据。因为数组元素地址是连续的，所以这使得数组更容易结算元素的地址，可以通过一个地址（首地址）作为基本地址，通过地址的偏移值快速访问元素。

数组的索引类型：索引0，数组的第一个元素使用0标记；索引1，通常1不是数组的第一个元素；索引n，表示数组中的任意位置，范围为：0到n-1（最后一个元素不是n）。

使用数组的优点：数组允许随机访问元素，这使得访问数据更快。数组具有更好的缓存局部性，这可以在性能上产生很大的差异。

二、JavaScript链表的介绍

和数组一样，链表也是一个线性的数据结构，但是和数组不同，链表的元素不是连续储存的，如上图是链表一般的形式。

为什么使用链表呢？数组可以用于储存相同或相似数据类型的线性数据，但是数组有以下限制：

1. 数组的大小是固定的：所以我必须知道元素数量的上界，而且分配给数组的内存大小通常都等于元素数量的上界。
2. 插入或删除数组中的一个元素比较耗时，例如插入一个元素都位置i上，则在插入之前需要预先在i位置上空出位置，这需要花费O(n)的时候移动元素。

链表的大小则不是固定的，根据需要动态变化，同时链表的插入和删除非常容易，花费的时间为O(1)，但是也有以下缺点：

1. 不允许随机访问，必须进行顺序访问，所以链表不允许进行二分搜索。
2. 链表需要使用额外的空间储存指针。
3. 缓存不友好，数组元素是连续的位置，但是在链表中是不存在的。

数组的表示：一个链表通常是使用链表中的第一个结点表示，该结点称为头结点，如果链表是空的，那么该头结点的值为空的。其中每个结点包括至少两部分：

1. 数组项data
2. 指针或引用，指向下一个结点

在JavaScript中可以使用一个对象表示一个结点，下一个节点同样是使用对象表示。

三、数组和链表操作和实现源码

下面是数组和链表的常规操作：

1. add()：插入操作，在链表中时间复杂度为O(1)，数组为O(n)。
2. delete()：删除操作，数组和链表的时间复杂度分别为：O(n)、O(1)。
3. search()：遍历操作，搜索数组或链表中的一个元素。
4. contain()，检查数组或链表中是否存在某个元素。
5. reverse()，逆序遍历。

以上是数组和链表的一些基本操作，下面仅仅实现链表，其中除了实现基本的链表操作，还实现相关的栈和队列的操作，实现源码如下：

// 链表结点，双链表
function Node(key, value){
    this.key = key;
    this.value = value;
    this.next = null;
    this.prev = null;
}

// 链表
function LinkedList(){
    this.head = null;
    this.tail = null;
    this.size = 0;
}

// 链表操作

// 检查链表是否已空
LinkedList.prototype.isEmpty = function(){
    return this.size == 0;
}

// 从表头添加数据
LinkedList.prototype.pushBack = function(key, value){
    var node = new Node(key, value);
    if(this.size == 0){
        node.prev = node.next = node;
        this.head = this.tail = node;
        this.size++;
    }
    else{
        var head = this.head;
        head.prev = node;
        node.next = head;
        var tail = this.tail;
        tail.next = node;
        node.prev = tail;
        this.tail = node;
        this.size++;
    }
}

// 从表尾添加数据
LinkedList.prototype.pushFront = function(key, value){
    var node = new Node(key, value);
    if(this.size == 0){
        node.prev = node.next = node;
        this.head = this.tail = node;
        this.size++;
    }
    else{
        var head = this.head;
        var tail = this.tail;
        head.prev = node;
        node.next = head;
        tail.next = node;
        node.prev = tail;
        this.head = node;
        this.size++;
    }
}

// 从表尾删除一个数据
LinkedList.prototype.popBack = function(){
    if(this.size == 0)
        return null;
    var tail = this.tail;
    var head = this.head;
    tail.prev.next = head;
    head.prev = tail.prev;
    this.tail = tail.prev;
    this.size--;
    var value = tail.value;
    tail = null;
    return value;
}

// 从表头删除一个数据
LinkedList.prototype.popFront = function(){
    if(this.size == 0)
        return null;
    var head = this.head;
    var tail = this.tail;
    tail.next = head.next;
    head.next.prev = tail;
    this.head = head.next;
    this.size--;
    var value = head.value;
    head = null;
    return value;
}

// 根据特定的数据key删除数据
LinkedList.prototype.delete = function(key){
    if(this.size == 0)
        return;
    var node = this.head;
    do{
        if(node.key = key){
            var prev = node.prev;
            var next = node.next;
            prev.next = next;
            next.prev = prev;
            if(node == this.head)
                this.head = next;
            if(node == this.tail);
                this.tail = prev;
            node = null;
            this.size--;
            return;
        }
        node = node.next;
    }while(node != this.head);
}

// 使用深度优先DFS搜索数据
LinkedList.prototype.find = function(node, key){
    if(!node)
        return null;
    if(node.key == key)
        return node.value;
    else
        return this.find(node.next, key);
}

// 根据key搜索指定数据
LinkedList.prototype.search = function(key){
    if(this.size == 0)
        return null;
    this.tail.next = null;
    var value = this.find(this.head, key);
    this.tail.next = this.head;
    return value;
}

// 检查链表是否包含指定key的元素
LinkedList.prototype.contain = function(key){
    if(this.size == 0)
        return false;
    return this.search(key) != null;
}

// 顺序遍历并输出链表
LinkedList.prototype.traverse = function(){
    if(this.size == 0)
        return;
    var node = this.head;
    var content = "";
    do{
        content += node.key + " ";
        node = node.next;
    }while(node != this.head);
    console.log(content);
}

// 逆序遍历输出链表
LinkedList.prototype.reverse = function(){
    if(this.size == 0)
        return;
    var node = this.tail;
    var content = "";
    do{
        content += node.key + " ";
        node = node.prev;
    }while(node != this.tail);
    console.log(content);
}

// 1、一般链表操作
var u1 = {"key": 12, "name": "JavaScript"};
var u2 = {"key": 20, "name": "C++"};
var u3 = {"key": 30, "name": "Python"};
var list = new LinkedList();
list.pushFront(u1.key, u1);
list.pushFront(u2.key, u2);
list.pushFront(u3.key, u3);
list.traverse();
list.reverse();
console.log("list contains 20: " + list.contain(20));
console.log("list contains 40: " + list.contain(40));
list.delete(30);
console.log("list contains 30: " + list.contain(30));
list.traverse();

console.log();

// 2、模拟栈
var stack = new LinkedList();
stack.pushFront(u1.key, u1);
stack.pushFront(u2.key, u2);
stack.pushFront(u3.key, u3);
var value;
var str = "";
while(!stack.isEmpty()){
    value = stack.popFront();
    str += value.key + " ";
}
console.log(str);

console.log();

// 3、模拟队列
var queue = new LinkedList();
queue.pushBack(u1.key, u1);
queue.pushBack(u2.key, u2);
queue.pushBack(u3.key, u3);
value = null;
str = "";
while(!queue.isEmpty()){
    value = queue.popFront();
    str += value.key + " ";
}
console.log(str);