C中的鏈接列表：爲什麼我要進行分段轉換？

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; 
} 

調試器輸出。這是我運行這段代碼時得到的調試器輸出。

Valgrind的：

==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; 

Answer 2

第二個問題。如果刪除最後一個節點，清除最後一個參考

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

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

    if (!l->first) 
    { 
    l->last = 0; 
    } 

    free(head); 
}