c - 使用O(1)插入操作创建邻接表

Question

我目前所拥有的是：

void addEdge(listNode **adjacencyList, int firstVertex, int secondVertex, int cost) {
    if (firstVertex == secondVertex) return;

    attachNeighbor(firstVertex, cost, adjacencyList[secondVertex]);
    attachNeighbor(secondVertex, cost, adjacencyList[firstVertex]);
}

void attachNeighbor(int id, int cost, listNode *root) {
    if (root->vertex == 0) {
        root->vertex = id;
        root->cost = cost;
    } else {
        listNode *neighbor;
        neighbor = (listNode *) malloc(sizeof(listNode));
        neighbor->cost = cost;
        neighbor->vertex = id;

        listNode *next = root;
        while (next->next != NULL) {
            next = next->next;
        }

        next->next = neighbor;
    }
}

但是，对于具有10k +个顶点和超过一百万条边的情况，这确实很慢，因为每个插入操作都需要O（Neighbors）。后来，我要做的只是遍历所有邻居一次，因此不需要快速检索。我考虑过使用双向链表并保留指向最后一个节点的指针，然后当我必须进行迭代时，我只会向后走，但我不确定如何在C中做到这一点

Answer 1

您可以将新节点放在列表的前面，每次都更改根：

void addEdge(listNode **adjacencyList, int firstVertex, int secondVertex, int cost) {
    if (firstVertex == secondVertex) return;

    attachNeighbor(firstVertex, cost, adjacencyList + secondVertex);
    attachNeighbor(secondVertex, cost, adjacencyList + firstVertex);
}

void attachNeighbor(int id, int cost, listNode **pRoot) {
    listNode *root = *pRoot;
    if (root->vertex == 0) {
        root->vertex = id;
        root->cost = cost;
    } else {
        listNode *neighbor;
        neighbor = (listNode *) malloc(sizeof(listNode));
        neighbor->cost = cost;
        neighbor->vertex = id;
        neighbor->next = root;
        *pRoot = neighbor;
    }
}