目录

什么是List

实现

数据结构：

实现功能：

C++代码

        方法声明及部分实现

        核心实现

        扩容

        指定位置插入元素

        删除指定位置的元素

测试

        代码

        输出

---

什么是List

  List是一种常见的数据结构，用于存储一系列有序的元素。它允许存储、访问、添加、删除和修改元素，可以根据需要动态调整大小。

以下是List的一些常见特点和用途：

• List中的元素按照它们被添加的顺序进行存储，并可以根据索引进行访问。
• List可以包含任意类型的元素，如整数、字符串、自定义对象等。
• List通常支持重复元素，即同一个元素可以出现多次。
• List一般提供了丰富的内置方法，如添加元素、删除元素、获取元素、修改元素、查找元素、排序等。
• List可以用于实现栈（Stack）和队列（Queue）等其他数据结构。（后续会讲栈（Stack）和队列（Queue））。
• List还可以用于存储和处理大量数据，并提供高效的元素访问和操作。

实现

数据结构：

        T* data : 动态数组

        int siz:数组元素的个数

        int capacity:数组实际大小

实现功能：

        1、末尾添加元素：push(T t)

        2、指定位置添加元素：push(int index, T t)

        3、修改指定位置元素：set(int index, T t)

        4、获取指定位置的元素：get(int index)

        5、删除指定位置元素：remove(int index)

        6、扩容：expand_capacity()

        7、打印list：print_list()

C++代码

        方法声明及部分实现

/**
 * 数组实现list
 */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>

#ifndef LIST_ARRAY_LIST_H
#define LIST_ARRAY_LIST_H

const int EXPAND_CAPACITY = 50; // 每次扩容大小
const int MAX_CAPACITY = INT_MAX; // 最大容量

template<typename T>
class ArrayList {
public:

    /**数组末尾添加元素
     * @brief push
     * @param t
     */
    void push(T t) {
        expand_capacity();
        data[siz] = t;
        siz++;
    }

    // 指定位置添加元素
    void push(int index, T t);

    inline int size() const { return siz; } // 获取list大小

    // 获取指定位置的元素
    T get(int index) {
        if (index < siz && index > 0) return data[index];
    }

    // index位置元素设置为t
    T set(int index, T t) {
        if (index < siz && index > 0) {
            T old_v = data[index];
            data[index] = t;
            return old_v;
        }
    }

    T remove(int index);

    ArrayList() {
        data = (T *) malloc(sizeof(T) * capacity);
    }

    // 析构
    ~ArrayList() {
        delete data;
    }

    // 打印list
    void print_list(){
        for(int i = 0; i < siz; i++){
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }
private:
    T *data; // 数据
    int siz = 0; // 元素个数
    int capacity = 10; // 数组容量

    // 扩容
    void expand_capacity();
};

#endif //LIST_ARRAY_LIST_H

        核心实现

        扩容

        实现思路：当siz>=capacity时，给data扩容并重新分配内存。malloc函数分配内存，memcpy拷贝数组。

/**
 * 扩容
 * push操作时扩容
 * @tparam T
 */
template<typename T>
void ArrayList<T>::expand_capacity() {
    if (siz >= capacity) {
        capacity += EXPAND_CAPACITY;
        if (capacity >= MAX_CAPACITY) {
            capacity = MAX_CAPACITY;
        }
        T *t = (T *) malloc(sizeof(T) * capacity);
        memcpy(t, data, sizeof(T) * siz);
        delete data;
        data = t;
    }
}

        指定位置插入元素

        实现思路：先执行扩容操作，如果index大于等于siz直接从list最后添加元素。如果从中间插入，先把index后的元素后移，再在index位置插入t。siz ++

/**
 * 从index位置插入元素t
 * @tparam T
 * @param index
 * @param t
 */
template<typename T>
void ArrayList<T>::push(int index, T t) {
    expand_capacity();
    if (index >= siz) {
        push(t);
    } else {
        for (int i = siz - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = t;
        siz++;
    }
}

        删除指定位置的元素

        实现：直接把index后的所有元素前移一位，siz = siz -1

/**
 * 删除指定位置的元素
 * @tparam T
 * @param index
 * @return
 */
template<typename T>
T ArrayList<T>::remove(int index) {

    T res = data[index];

    for(int i = index; i < siz - 1; i++){
        data[i] = data[i+1];
    }
    siz --;
    return res;
}

测试

        代码

#include "array_list.h"

int main() {
    ArrayList<int> arrayList;
    arrayList.push(12); // 添加元素
    arrayList.push(1,23);
    arrayList.push(5,33);
    arrayList.push(1,102);
    arrayList.print_list();
    arrayList.remove(0); // 删除元素
    arrayList.print_list();

    arrayList.set(2,44);
    arrayList.print_list();

    std::cout << arrayList.get(2) << std::endl;
    return 0;
}

        输出

12 102 23 33 
102 23 33 
102 23 44 
44