个性化阅读
专注于IT技术分析

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

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

JS链表和数组

一、JavaScript线性表:数组

JS数组图解

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

数组的索引类型:索引0,数组的第一个元素使用0标记;索引1,通常1不是数组的第一个元素;索引n,表示数组中的任意位置,范围为:0到n-1(最后一个元素不是n)。

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

二、JavaScript链表的介绍

JS链表图解

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

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

  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);
赞(0) 打赏
未经允许不得转载:srcmini » JavaScript常用数据结构之线性表:数组和链表
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏