重新排列双链表时偶尔出现错误

Question

我很抱歉，如果这对一些人来说可能是微不足道的，但在过去的一天里，我无法弄清楚为什么会发生这种故障。我有一系列的双链表，我保持一定的顺序。每次访问或更新列表中的节点时，都会将其移动到列表的开头，这在数组中的每个链接列表中都会发生。我将提供如何初始化链表数组以及如何排列顺序的代码。感谢您的帮助。如果有帮助的话，可以使用双链表数组来模拟缓存。我只是希望这是显而易见的事情，因为我对malloc和C有点陌生。第一次使用这个网站，所以请让我知道，如果我没有遵循惯例，或者我的帖子有问题

我试着打印出链表数组的结构，它似乎总是结构合理的。只有当我重新排列节点时，特别是当我试图访问节点时，才会出现分段故障。

void maintainLRU(cacheBlock* ptr, int index)//rearranges a list with node passed in to be head
{
    if(ptr->next == NULL)//Tail
    {
        ptr->next = cache[index].head;
        cache[index].head = ptr;
        cache[index].tail = ptr->prev;
        ptr->prev->next = NULL;
        ptr->prev = NULL;
    }
    else
    {
        ptr->prev->next = ptr->next;
        ptr->next = cache[index].head;
        cache[index].head = ptr;
        ptr->prev->next = NULL;
        ptr->prev = NULL;
    }
}

//following code exists within main and is how i initialize the'cache'
numLines = cacheSize/(blockSize*assocType); //determines number of linked lists in my array. 
cache = malloc(sizeof(cacheLine)*numLines);
for(int i = 0; i < numLines; i++)
{
        cacheBlock* temp = malloc(sizeof(cacheBlock));
        temp->valid = 0; //whether the node holds data yet or not
        cache[i].head = temp;
        for(int j = 1; j < assocType; j++)//assoctype is just how many nodes in the list
        {
            temp->next = malloc(sizeof(cacheBlock));
            temp->next->prev = temp;
            temp->next->valid = 0;
            temp = temp->next;
        }
        cache[i].tail = temp;
}//cacheblock is just a node with next, prev, and a valid bit
//cacheLine is just a struct with a pointer to a headnode
//the maintain order function is explicitly called only if the node updated or accessed is not the head.```

Answer 1

案例1：ptr是在列表的末尾，你正确地移除自己，把自己放在列表的开头，但不要让列表的“旧”头指向你；所以你的名单是腐败的。

案例2：ptr不在列表的末尾，你将上一个指向下一个，但不要将下一个指向上一个，这样列表就会损坏。

所有情况下：你应该提供足够多的程序，有人可以编译并试用。在某种程度上，这将导致你对自己的工作进行充分的分析，从而注意到明显的错误。微妙的是这个论坛的目的。

30年前，严格优化链表操作是非常重要的；在那段时间里，编译器书呆子已经提升了他们的游戏水平，你应该能够将维护LRU写成：

void maintainLRU(cacheBlock* ptr, int index) {
    list_remove(&cache[index], ptr);
    list_insert_before(&cache[index], cache[index].head, ptr);
}

所以你不会成为简单错误的受害者。