/**************************************************************************
 *
 * @Author       : LYB
 * @Date         : 2021-02-21 18:58:41
 * @LastEditors  : LYB
 * @LastEditTime : 2021-02-21 18:58:59
 * @FilePath     : \code\ArrayList\array_list.h
 * @Description  : 该文件定义为线性链表相关的实现
 * 线性链表的特性：
 *      1、在内存中的存放地址是连续的
 *  优点：
 *      1、由于地址的连续性，所以CPU的pc指针寻址的地址空间的范围不会太大，所以随机访问链表的速度非常快，遍历的速度非常快，释放空间也比较快
 *  缺点：
 *      2、也正是地址的连续性，所以当每次随机插入的时候都要进行链表剩余空间的检查，如果空间不够，然后又要重新分配内存，
 *      如果随机插入的位置后面有元素，需要把该位置的元素都要依次往后挪一位，然后在当前位置进行插入，所以这样就造成速度非常慢
 *
 **************************************************************************/
#ifndef _ARRAY_LIST_H_
#define _ARRAY_LIST_H_
#ifdef __cplusplus
extern "C"
{
#endif
// 链表初始化大小
#define ARRAY_LIST_INIT_SIZE 100
// 链表存满每次增加的大小
#define ARRAY_LIST_INCREASE_SIZE 200
// 定义节点
typedef struct array_node {
    void *data; //数据域
} array_node_t;
// 定义链表结构
typedef struct array_list {
    array_node_t *node;     //数据域
    unsigned long length;   //链表的当前长度
    unsigned long size;     //链表的整体大小
} array_list_t;
/**
 * 功能：初始化链表
 * 返回值：如果成功，则返回链表的地址，如果失败返回NULL
 */
array_list_t *array_list_init();
/**
 * @description:
 * @param:
 * @return：成功返回0，失败返回-1
 */
/**
 * 功能：随机插入链表
 * 参数：
 *    pList：链表地址
 *    pData：插入的数据节点
 *    index：要插入的位置，如果为0，则默认从链表的开始处插入，如果为-1，则默认从链表的最后插入
 * 返回值：成功返回0，失败返回-1
 */
int array_list_insert(array_list_t *pList, void *pData, long index);
/**
 * 功能：从某个位置取出元素
 * 参数：
 *    pList：链表地址
 *    index：位置
 * 返回值：返回数据体指针
 */
void *array_list_getat(array_list_t *pList, unsigned long index);
/**
 * 功能：通过索引删除元素，删除元素只是将data域置为NULL，并不会释放data指针，由调用者释放
 * 参数：
 *    pList：链表地址
 *    index：位置
 */
void array_list_removeat(array_list_t *pList, unsigned long index);
/**
 * 功能：清空链表
 * 参数：
 *  pList：链表地址
 */
void array_list_clear(array_list_t *pList);
/**
 * 功能：释放链表空间
 * 参数：
 *  pList：链表地址
 */
void array_list_free(array_list_t *pList);
/**
 * 功能：Array测试
 */
void array_list_test();
#ifdef __cplusplus
} /* end of the 'extern "C"' block */
#endif
#endif

#include "string.h"
#include "stdio.h"
#include "stdbool.h"
#include "array_list.h"
array_list_t *array_list_init()
{
    int i = 0;
    array_list_t *list = (array_list_t *)malloc(sizeof(array_list_t));
    if (NULL == list) {
        return NULL;
    }
    list->node = (array_node_t *)malloc(sizeof(array_node_t) * ARRAY_LIST_INIT_SIZE);
    if (NULL == list->node) {
        return NULL;
    }
    for (i = 0; i < ARRAY_LIST_INIT_SIZE; i++) {
        list->node[i].data = 0;
    }
    list->length = 0;
    list->size = ARRAY_LIST_INIT_SIZE;
    return list;
}
/**
 * @description:
 * @param:
 * @return：成功返回0，失败返回-1
 */
/**
 * 功能：随机插入链表
 * 参数：
 *    list：链表地址
 *    data：插入的数据节点
 *    index：要插入的位置，如果为0，则默认从链表的开始处插入，如果为-1，则默认从链表的最后插入
 * 返回值：成功返回0，失败返回-1
 */
int array_list_insert(array_list_t *list, void *data, long index)
{
    int relloc_size = 0;
    int i = 0;
    if (NULL == list) {
        return -1;
    }
    if (index < -1 || (index > list->length && index != -1)) {
        return -1;
    }
    if (list->length == list->size -1) {
        relloc_size = list->size + ARRAY_LIST_INCREASE_SIZE;
        list->node = (array_node_t *)relloc(sizeof(array_node_t) * relloc_size);
        if (NULL == list->node) {
            return -1;
        }
        for (i = list->length; i < relloc_size; i++) {
            list->node[i].data = 0;
        }
        list->size = relloc_size;
    }
    if (0 == index) {                   /* 从list头部插入数据 */
        for (i = list->length; i > 0; i--) {
            list->node[i].data = list->node[i - 1].data;
        }
        list->node[0].data = data;
    } else if (-1 == index) {           /* 从list尾部插入数据 */
        list->node[list->length].data = data;
    } else {                            /* 从list的index位置插入数据 */ 
        for (i = list->length; i > index; i++) {
            list->node[i] = list->node[i - 1];
        }
        list->node[index].data = data;
    }
    list->length++;
    return 0;
}
/**
 * 功能：从某个位置取出元素
 * 参数：
 *    list：链表地址
 *    index：位置
 * 返回值：返回数据体指针
 */
void *array_list_getat(array_list_t *list, unsigned long index)
{
    void *data = NULL;
    if (NULL == list) {
        return;
    }
    if (index < 0 || index > list->length) {
        return;
    }
    data = list->node[index - 1].data;
    return data;
}
/**
 * 功能：通过索引删除元素，删除元素只是将data域置为NULL，并不会释放data指针，由调用者释放
 * 参数：
 *    list：链表地址
 *    index：位置
 */
void array_list_removeat(array_list_t *list, unsigned long index)
{
    int i = 0;
    if (NULL == list) {
        return;
    }
    if (index < 0 || index > list->length) {
        return;
    }
    /* index之后的node全部前移一位 */
    for (i = index; i < list->length; i++) {
        list->node[i] = list->node[i + 1];
    }
    /* 最后一个node数据置为NULL */
    list->node[list->length - 1].data =NULL;
    /* list长度自减1 */
    list->length--;
    return;
}
/**
 * 功能：清空链表
 * 参数：
 *  list：链表地址
 */
void array_list_clear(array_list_t *list)
{
    int i = 0;
    if (NULL == list) {
        return;
    }
    for (i = 0; i < list->length; i++) {
        list->node[i].data = NULL;
    }
    list->length = 0;
    return;
}
/**
 * 功能：释放链表空间
 * 参数：
 *  list：链表地址
 */
void array_list_free(array_list_t *list)
{
    if (NULL == list) {
        return;
    }
    if (NULL != list->node) {
        free(list->node);
        list->node = NULL;
    }
    if (NULL != list) {
        free(list);
        list = NULL;
    }
    return;
}
/**
 * 功能：Array测试
 */
void array_list_test()
{
}