c - C 中的链表 : Why am I segfaulting?

Question

我是 C 的新手，一直致力于手工编写链表。现在，我正在研究一种从列表前面删除元素的方法。内容如下:

   void remove_from_front(List *l)
    {
      Node *head = l->first;

      l->first = l->first->next;

      free(head);
    }

我确定这是显而易见的事情，但我不明白。以下是关于我的问题的一些相关数据:

先前的研究。我查看了多个 SO 帖子，包括 this one ，但都使用不同的实现，我似乎无法区分。网上到处都是这段代码的例子，但我不明白它们是如何工作的，而是想了解我的代码哪里做错了。

相关代码片段。这是我程序中的其余代码:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
  void *element;
  struct Node *next;
  struct Node *prev;
} Node;

typedef struct List{
  struct Node *first;
  struct Node *last;
} List;

void add_to_front(List *l, void *toAdd)
{
  Node *n = (Node *)calloc(1, sizeof(Node));
  n->element = toAdd;
  n->next = l->first;
  n->prev = NULL;

  if(l->first != NULL)
    {
      l->first->prev = n;
    }
    l->first = n;
}


void add_to_back(List *l, void *toAdd)
{
  Node *n = (Node *)calloc(1, sizeof(Node));
  n->element = toAdd;
  n->next = NULL;
  n->prev = l->last;

  if(l->last != NULL)
    {
      l->last->next = n;
    }
    l->last = n;
}

void remove_from_front(List *l)
{
  Node *head = l->first;

  l->first = l->first->next;

  free(head);
}

int main(int argc, char *argv[])
{
  List *l = calloc(1, sizeof(List));
  l->first = NULL;
  l->last = NULL;

  add_to_front(l, (void *)'a');
  printf("First element: %c\n", l->first->element);
  add_to_back(l, (void *)'b');
  printf("Last element: %c\n", l->last->element);
  remove_from_front(l);
  printf("New first element: %c\n", l->first->element);
  return 0;
}

调试器输出。这是我运行这段代码时得到的调试器输出。

瓦尔格林德:

==9389== Invalid write of size 4
==9389==    at 0x804852E: remove_from_front (in /home/vagrant/plc/linkedList)
==9389==    by 0x80485D3: main (in /home/vagrant/plc/linkedList)
==9389==  Address 0x8 is not stack'd, malloc'd or (recently) free'd
==9389==
==9389==
==9389== Process terminating with default action of signal 11 (SIGSEGV)
==9389==  Access not within mapped region at address 0x8
==9389==    at 0x804852E: remove_from_front (in /home/vagrant/plc/linkedList)
==9389==    by 0x80485D3: main (in /home/vagrant/plc/linkedList)
==9389==  If you believe this happened as a result of a stack
==9389==  overflow in your program's main thread (unlikely but
==9389==  possible), you can try to increase the size of the
==9389==  main thread stack using the --main-stacksize= flag.
==9389==  The main thread stack size used in this run was 8388608.
==9389==

GDB:

Starting program: /home/vagrant/plc/linkedList
First element: a
Last element: b

Program received signal SIGSEGV, Segmentation fault.
0x0804852e in remove_from_front ()

当我在没有调试器的情况下运行可执行文件时的输出很简单:

First element: a
Last element: b
Segmentation fault

如果可能的话，我将不胜感激。谢谢!

Answer 1

问题是当你在前面添加的时候，如果是列表的第一个元素，你需要设置最后一个指针，让它也指向第一个元素，即当列表有单个元素时元素，第一个和最后一个应该指向同一个节点。

// in add_to_front
if (l->last == NULL) {
    l->last = l->first;
}
// add to back:
if (l->first == NULL) {
    l->first = l->last;
}
// in remove from front, check if the list is empty:
if (l->first == NULL)
    return;