数据结构篇——列表

发表于 | 分类于

列表是一种最自然的数据组织方式

列表适用的场景

  • 对元素的存储顺序没有要求
  • 不需要查找或者排序
  • 即数据结构比较简单的时候

下面是用JavaScript实现的一个列表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
function List(){
    this.listSize = 0;
    this.pos = 0;
    this.length = length
    this.dataStore = [];
    this.clear = clear;
    this.find = find;
    this.toString = toString;
    this.insert = insert;
    this.append = append;
    this.remove = remove;
    this.front = front;
    this.end = end;
    this.prev = prev;
    this.next = next;
    this.currPos = currPos;
    this.moveTo = moveTo;
    this.getElement = getElement;
    this.contains = contains;
}
// 给列表添加元素
function append(element){
    // 先返回原来的listSize作为新元素的索引，在自增1
    this.dataStore[this.listSize++] = element;
}

// 删除列表元素
// 要删除首先要找到删除对象
function find(element){
    for(let i = 0; i < this.dataStore.length; i++){
        if(this.dataStore[i] == element){
            return i;
        }
        return -1;
    }
}

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

function length(){
    return this.listSize;
}

function toString(){
    return this.dataStore;
}

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

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

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];
}

// 测试代码
let names = new List();
names.append('a');
names.append('b');
names.append('c');
names.append('d');
names.append('e');
names.front();
console.log(names.getElement());
names.next();
names.next();
names.prev();
console.log(names.getElement());

// 使用迭代器访问列表
// 从前往后遍历
for(names.front(); names.currPos() < names.length(); names.next()){
    console.log(names.getElement())
}

// 从后往前遍历
for (names.end(); names.currPos() >= 0; names.prev()) {
    console.log(names.getElement())
}