用C语言写一段用数组的链表代码

由于“数组的链表”一词理解起来有些困难，这里我提供两个数组相关的链表代码。

1. 数组实现的链表

这种链表的实现方式是使用一个指针数组和一个可用位置的指针来表示链表。节点的数据存放在数组中，通过数组下标来访问。链表的头节点指针指向第一个可用位置的指针，链表的尾节点指针指向最后一个非可用位置的指针。

#define MAX_NODE 100

int data[MAX_NODE];
int next[MAX_NODE];
int head;
int tail;
int free_pos;

void init() {
    for (int i = 0; i < MAX_NODE; i++) {
        next[i] = i + 1;
    }
    next[MAX_NODE - 1] = -1;
    free_pos = 0;
    head = -1;
    tail = -1;
}

int allocate_node() {
    if (free_pos == -1) {
        return -1;  // 标记无可用节点
    }
    int pos = free_pos;
    free_pos = next[pos];
    return pos;
}

void free_node(int pos) {
    next[pos] = free_pos;
    free_pos = pos;
}

void insert(int val) {
    int pos = allocate_node();
    if (pos == -1) {
        return;  // 链表已满
    }
    data[pos] = val;
    next[pos] = -1;
    if (head == -1) {
        head = pos;
    } else {
        next[tail] = pos;
    }
    tail = pos;
}

void remove(int val) {
    int curr = head;
    int prev = -1;
    while (curr != -1 && data[curr] != val) {
        prev = curr;
        curr = next[curr];
    }
    if (curr == -1) {
        return;  // 没有找到值为val的节点
    }
    if (prev == -1) {
        head = next[curr];
    } else {
        next[prev] = next[curr];
    }
    free_node(curr);
}

void show() {
    int curr = head;
    while (curr != -1) {
        printf("%d ", data[curr]);
        curr = next[curr];
    }
    printf("\n");
}

2. 动态数组实现的链表

这种链表的实现方式是使用动态数组，数组中的元素是节点指针，每个节点指针指向一个节点。链表的头节点指针指向第一个节点，链表的尾节点指针指向最后一个节点。当链表需要扩容时，动态数组会重新分配更大的内存，并将原有元素复制到新的内存中。

#include <stdlib.h>

typedef struct node_t {
    int val;
    struct node_t* next;
} node_t;

int size;
int capacity;
node_t** nodes;

void init() {
    size = 0;
    capacity = 1;
    nodes = (node_t**)malloc(capacity * sizeof(node_t*));
    nodes[0] = NULL;
}

void insert(int val) {
    node_t* node = (node_t*)malloc(sizeof(node_t));
    node->val = val;
    node->next = NULL;
    nodes[size] = node;
    size++;
    if (size == capacity) {
        capacity *= 2;
        nodes = (node_t**)realloc(nodes, capacity * sizeof(node_t*));
    }
    if (size == 1) {
        nodes[0] = node;
    } else {
        nodes[size - 2]->next = node;
    }
}

void remove(int val) {
    node_t* curr = nodes[0];
    node_t* prev = NULL;
    while (curr != NULL && curr->val != val) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL) {
        return;  // 没有找到值为val的节点
    }
    if (prev == NULL) {
        nodes[0] = curr->next;
    } else {
        prev->next = curr->next;
    }
    free(curr);
    size--;
    if (size <= capacity / 2) {
        capacity /= 2;
        nodes = (node_t**)realloc(nodes, capacity * sizeof(node_t*));
    }
}

void show() {
    node_t* curr = nodes[0];
    while (curr != NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}