什么是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
