列表（List）

列表是一种抽象的数据结构概念，可基于链表和数组实现。由于其动态扩容性，灵活程度远高于链表和数组。链表本身就一个列表，可以动态扩展长度，而数组可以看作一个长度固定的列表。倘若使用数组来实现列表，长度和扩容问题显然使得实现后得列表具有较大缺陷。因此引入 动态数组Dynamic Array这个概念来实现列表。动态数组在完美继承数组的所有特点的同时，还允许在程序运行时进行动态扩容。

1. 列表的常用操作

1.1 初始化列表

在许多高级编程语言的标准库中都初始了动态数组的构造方法。我们直接调用即可，当然也可实现自己构造函数，后续会有。初始化列表通常分为“无初始值”和“有初始值”。

	fn main(){
        //无初始值
        let vec1:Vec<i32> = Vec::new();
        //有初始值
        let vec2:Vec<i32> = Vec![1,2,3,5,6];
        
	}

1.2 访问列表元素

由于列表继承数组特性，可以像访问数组元素那样通过索引在O(1)内访问任何元素。

    /* 访问元素 */
    let num: i32 = vec2[1];  // 访问索引 1 处的元素
    /* 更新元素 */
    nums[1] = 0;             // 将索引 1 处的元素更新为 0

1.3 遍历列表元素

跟数组一样，可以通过索引或者直接访问列表元素的方式来遍历列表

	let mut count = 0;
	for i in 0..vec2.len(){
        count += vec2[i]
	}
	count = 0;
	for item in &vec2{
        count += item
	}

1.4 插入和删除元素

在列表的末尾可以在O(1)时间内完成操作，其他位置插入的时间复杂度为O(n)

	vec2.push(9);
	vec2.push(11);

	//指定位置插入
	vec2.insert(3,6) // 使用insert(index,vaue),在索引index处插入value

	//清空列表
	vec2.clear()

	//删除元素
	vec2.remove(3) // remove(index),删除指定索引处的元素

1.5 排序列表

直接使用封装的API操作

	vec2.sort()

1.6 组合列表

使用extend方法将两个列表组合成一个列表，注意：拼接在尾部

	let vec3 = Vec![4,6,8];
	vec2.extend(vec3);

2. 列表的实现原理

虽然许多的高级语言都已经封装了列表的实现以及一系列的方法。但是为了更好的理解深层原理，这里着手实现一个简易列表。在动手编写代码前，应该搞清楚以下概念：

1. 初始容量：初始化列表的容量，应选择合适的容量。
2. 数量标记：实时标识列表内的元素的数量，当进行增删等操作时，相应修改该标记，并根据与初始容量的比较决定是否扩容
3. 扩容机制：若插入元素时列表容量已满，则需要进行扩容。先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。这里通过固定的倍率来创建更大的新数组。

	struct MyList{
        vec:Vec<i32>,
        capacity:usize,
        size:usize,
        rate:usize
	}
	
	impl MyList(){
        /*构造函数*/
        pub fn new(capacity:usize) -> Self{
  			let mut vec = Vec::new();
            vec.resize(capacity,0);
            Self{
                vec,
                capacity,
                size:0,
                rate:2
            }
        }
        /*获取列表容量*/
        pub fn get_capacity(&self) -> usize{
            self.capacity
        }
        /*获取列表长度*/
        pub fn get_len(&self) -> usize{
            self.size
        }
        //访问列表元素
        pub fn get_element(&self,index:usize){
            if index >= self.size{
                println!("索引越界")
            }
            return self.vec[index]
        }
        //更新元素
        pub fn update_element(&self,index,usize,value:i32){
            if index >= self.capacity{
                println!("超出索引") 
            }
            self.vec[index] = value
        }
        //删除元素
        pub fn delete_element(&self.index:usize) -> i32{
            if index >= self.size{
                panic!("超出索引")
            }
			let del:i32 = self.vec[index];
            //删除位置后的元素向前移一位
            for i in (index..self.size-1){
                self.vec[i] = self.vec[i+1]
            }
            //列表长度-1
            self.size -= 1;
            //返回被删除的元素
            del;
            
        }
        //在尾部插入元素
        pub fn add_last(&self,value:i32){
            if self.size >= self.capacity{
                 println!("容量已满,扩容");
                 self.extend_list();
            }
            let c_index = self.size
            self.vec[c_index] = value;
            self.size += 1; //元素数量+1
        }
        //在中间插入元素
         pub fn add_last(&self,index:usize,value:i32){
    		if index >= self.size{
                println!("超出索引")
             }
             if self.size == self.capacity{
                 self.extend_list()
			 }
             for i in (index+1..self.size){
                 self.vec[i] = slef.vec[i-1]
             }
             self.vec[index] = value;
             self.size += 1;
        }
        
        //扩容列表
        pub fn extend_list(&self){
			let mut new_capacity = self.capacity * self.rate;
            self.vec.resize(new_capacity,0);
            self.capacity = new_capacity;
        }
        
	}