JavaScript数据结构 —— 列表List

2022-03-19 16:28:53

2.1 —— List的简述

列表是一组有序的数据，每个列表中的数据项称为元素。

列表拥有描述元素位置的属性，列表有前有后（front和end）。

使用next()方法可以从当前元素移动到下一个元素，使用next（） 可以从当前元素移动到下一个元素，使用prev()方法可以移动到当前元素的前一个元素，还可以使用moveTo(n)方法直接移动到指定位置

2.1 —— List的方法

定义的属性有：

listSize : 列表的元素个数

pos：列表的当前位置

定义的方法有:

getElement(): 返回当前位置的元素

insert(): 在现有元素后插入新元素

append()：在列表的尾部添加新元素

remove(): 从列表中删除元素

length(): 返回列表中元素的个数

clear(): 清空列表

contains(): 判断元素是否存在列表中

移动元素：

front(): 将列表的当前位置移动到第一个元素

end(): 将列表的当前位置移动到最后一个元素

prev(): 将当前位置后移一位

next(): 将当前位置前移一位

currPos(): 返回列表的当前位置

moveTo(): 将当前位置移动到指定位置

2.3 —— List的实现

使用数组实现一个列表，并初始化属性值

function List() {
    this.listSize = 0; //记录列表元素的个数
    this.pos = 0; //记录列表的位置
    this.dataStore = []; //存储列表元素
}

append(element) 添加元素

给列表尾部添加新元素的方法与栈的压栈方法一样；

将记录元素个数的listSize加1，从而获取到存储元素的位置；再将元素添加到这个位置；

function append(element) {
    //让列表的长度加1，再将元素填充到新增的位置
    this.dataStore[this.listSize++] = element;
}

find(element) 查找元素

首先遍历列表，如果要查找的元素存在列表中，则返回该元素的位置，未找到则返回-1

function find(element) {
    //遍历列表
    for (let i = 0; i < this.dataStore.length; ++i) {
        //判断列表中是否有该元素，存在则返回索引i
        if (this.dataStore[i] == element) {
            return i;
        };
    };
    //不存在返回-1
    return -1;
};

remove(element) 删除元素

先调用find方法，查找元素的位置，如果存在返回true，不存在则会返回false;

如果存在，使用js数组操作方法splice删除当前元素，splice方法接收两个参数，即要删除的元素的索引和要删除的个数；

删除元素后，要将列表的长度减1；

function remove(element) {
    //调用定义的find方法查找元素
    let fountAt = this.find(element);
    //元素存在
    if (fountAt > -1) {
        //删除索引对应的值
        this.dataStore.splice(fountAt, 1);
        //列表少了一个元素，减1
        --this.listSize;
        //操作成功返回true
        return true;
    };
    //找不到元素返回false
    return false;
};

length() 查询列表中有多少元素

该方法返回列表中的元素，直接返回listSize的值

function length() {
    return this.listSize;
}

insert(element, after) 向列表中插入元素

该方法是将目标元素插入到指定元素的后面，它接收两个参数，即目标元素element和指定元素after；

实现：先使用定义的find方法找到after的位置，然后使用splice方法在该位置的后一位插入目标元素;

splice方法传入三个参数，目标值的位置，要删除的数量，要插入的值（第二个参数为0表示删除0个，不删除元素）;

操作成功返回true, 未找到指定元素则返回false

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

clear() 清空列表

删除列表，初始化数据

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

contains(element) 判断元素是否存在列表中

与find方法类似，也可直接使用find方法查找，找到返回true，不存在返回false

function contains(element) {
	for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return true;
        };
    };
    return false;
};

迭代器：移动列表中的元素

创建手动迭代列表的一些方法，可以不用关心数据的内部存储方法，以实现对列表的遍历。

//移动到最前面
function front() {
    this.pos = 0;
};
//移动到最后面
function end() {
    this.pos = this.listSize - 1;
};
//往后移一位
function prev() {
    if (this.pos > 0) {
        --this.pos;
    };
};
//往前移一位
function next() {
    if (this.pos < this.listSize-1) {
        ++this.pos;
    };
};
//返回列表当前的位置
function currPos() {
    return this.pos;
};
//移动到指定的位置
function moveTo(position) {
    this.pos = position;
};
//返回当前元素的位置
function getElement() {
    return this.dataStore[this.pos];
};

下一章：队列Queue...

码农公寓

相关文章