- 源码地址请点击此处
线性表是最基本，也是最常用的数据结构。线性表中元素的关系是线性的，也就是说，一个元素最多和两个元素发生关系（一前一后），最少和零个元素发生关系（当线性表中只有一个数据项时）。线性表的基本结构如下图所示：
线性表
几个基本概念
关于线性表，有以下几个基本概念：
- 空表
当线性表中没有元素时，就叫做空表。 - 前驱、后继
和某个元素相邻，并处于该元素前面的元素，叫做该元素的前驱。同理，和某个元素相邻，并处于该元素后面的元素，叫做该元素的后继。
从线性表的构造中可以看出：第一个元素没有前驱，只有后继，最后一个元素没有后继，只有前驱。 - 顺序表、链表
在存储结构上，线性表可以由顺序表或者链表构成。其中，顺序表会采用连续的内存空间分配，链表可以采用不连续的内存空间分配。本文要实现的线性表，是基于顺序表（数组）的。
线性表的衍生结构
线性表的还可以衍生为栈、队列等，其中栈和队列是操作受限的线性表，同样，在物理结构上，栈和队列也可以由顺序表或者链表构成。关于栈、队列和链表，将在后面的文章进行介绍，本文主要介绍通用的线性表：List。
List 的代码实现
下面是 List 的代码实现，采用了 TypeScript 语法，基于数组实现。
接口定义
interface IList<T>{
// 获取线性表的长度
size():number;
// 清除线性表中的元素
clear():void;
// 判断线性表是否为空
isEmpty():boolean;
// 查找元素
find(ele:T,flag?:boolean):number;
// 获取线性表中的所有元素
toString():T[];
// 插入元素
insert(newEle:T,oldEle:T):T|boolean;
// 添加元素
append(ele:T):T;
// 移除元素
remove(ele:T):T|boolean;
// 将元素指针移动到线性表开头
front():void;
// 将元素指针移动到线性表结尾
end():void;
// 将元素指针前移
prev():void;
// 将元素指针后移
next():void;
// 移动元素指针到具体位置
moveTo(pos:number):void;
// 根据元素指针获取元素
peek():T;
// 是否包含某个元素
contains(ele:T):boolean;
}
接口实现
class List<T> implements IList<T>{
// 线性表长度
private _size:number = 0;
// 元素指针
private pos:number = 0;
// 存放元素
private dataStore:T[] = [];
size():number{
return this._size;
}
clear():void{
this.dataStore = [];
}
isEmpty():boolean{
// 判断线性表是否为空
return !this._size;
}
find(ele:T,flag?:boolean):number{
// flag 标识用来指定顺序查找或者逆序查找
const index:number = flag ? (
this.dataStore.indexOf(ele)
):(
this.dataStore.lastIndexOf(ele)
);
return index;
}
toString():T[]{
return this.dataStore;
}
insert(newEle:T,oldEle:T):T|boolean{
// 获取老元素的位置
const oldElePos:number = this.find(oldEle);
if(oldElePos === -1){
return false;
}else{
// 使用 JavaScript 数组的 splice 方法进行元素插入
this.dataStore.splice(oldElePos + 1,0,newEle);
// 插入成功后更新线性表长度
this._size++;
// 返回被插入的元素
return newEle;
}
}
append(ele:T):T{
// 使用 JavaScript 数组的 push 方法添加元素
this.dataStore.push(ele);
// 插入成功后更新线性表长度
this._size++;
// 返回被插入的元素
return ele;
}
remove(ele:T):T|boolean{
// 查找待移除元素的位置
// 移除元素时从后向前删除
const pos:number = this.find(ele,true);
if(pos === -1){
return false
}else{
// 通过 JavaScript 数组的 splice 方法移除元素
this.dataStore.splice(pos,1);
// 移除成功后更新线性表长度
this._size--;
// 删除元素时纠正元素指针的位置
if(this.pos > this._size - 1){
this.pos = this._size - 1;
}
// 返回被移除的元素
return ele;
};
}
front():void{
// 将线性表的元素指针置于开头
this.pos = 0;
}
end():void{
// 将线性表的元素指针置于结尾
this.pos = this._size - 1;
}
prev():void{
// 将线性表的元素指针向前移动
if(this.pos > 0){
this.pos--;
return;
}
throw new Error("已经是第一个元素了");
}
next():void{
// 将线性表的元素指针向前移动
const len:number = this._size - 1;
if(this.pos < len){
this.pos++;
return;
}
throw new Error("已经是最后一个元素了");
}
moveTo(pos:number):void{
// 将线性表的元素指针移动到指定位置
const
min:number = 0,
max:number = this._size - 1;
// 越界判断
if(pos > max || pos < min){
throw new Error("索引越界！");
}else{
this.pos = pos;
}
}
peek():T{
// 根据线性表的元素指针获取当前元素
return this.dataStore[this.pos];
}
contains(ele:T):boolean{
// 查找元素是否存在于线性表
const index:number = this.find(ele);
if(index === -1)return false;
return true;
}
}
完。
