雙鏈表插入到特定列表功能和參數

Question

我有以下代碼是雙鏈表實現的一部分。然後我必須使用我的ADT實現來創建表格value（這是一個字符串），address（它是uint32_t類型）（所以是一個2列表）。

typedef struct { 
    char *label; // is a string like "mov". 
    uint32_t labelAddress; // the address of the label. 
} individualEntry; 

typedef void(*FreeList)(void*); 

typedef struct listEntries { 
    individualEntry newInstr; 
    struct listEntries *prev; 
    struct listEntries *next; 
} listEntries; 

listEntries *head; 

/* 
* HELPER FUNCTIONS 
*/ 

listEntries *createNewList() { 
    listEntries *newListPtr = malloc(sizeof(listEntries)); 
    return newListPtr; 
} 

listEntries *createNewEntry(char *label, uint32_t address) { 
    listEntries *newEntry = (listEntries*) malloc(sizeof(listEntries)); 
    newEntry->prev = NULL; 
    newEntry->next = NULL; 
    newEntry->newInstr.label = label; 
    newEntry->newInstr.labelAddress = address; 
    return newEntry; 
} 

void insert(char *label, uint32_t address) { 
    listEntries *temp = head; 
    listEntries *newEntry = createNewEntry(label, address); 
    if (head == NULL) { 
     head = newEntry; 
     return; 
    } 
    while (temp->next != NULL) { 
     temp = temp->next; 
    } 
    temp->next = newEntry; 
    newEntry->prev = temp; 
} 

我需要先創建這個表，然後添加到這個記錄。

我的困難在於插入到這個特定表中的函數的實現。我是否需要另一個插入功能，還是必須編輯我擁有的一個？

如果我需要一個新的函數，它的參數：一個指針型結構listEntries，字符串和記錄的地址的新表以復加，我需要在參數要考慮的一個和下一個記錄我的列表？

我不知道如何處理插入後的上一個和下一個指針。

有人可以發佈這樣的功能的實現嗎？

Answer 1

所以這是我對自己的問題的回答（編譯，測試，它的工作原理）。我使用迭代器，感謝上面的可視化，但我需要更多的技巧，比如迭代器這個詞。

void insert(struct list *listPtr, listIterator iter, int value) { 

struct listEntry *newEntry = list_alloc_elem(); // a helper that allocates memory for an individual entry; 
newEntry->value = value; 
newEntry->prev = iter->prev; 
newEntry->next = iter; 
iter->prev->next = newEntry; 
iter->prev = newEntry; 
} 

Answer 2

您需要將項目插入（雙向）鏈接列表中的唯一一項是參考節點，以及是否要在該節點之前或之後插入它。解決這個問題的最好方法是將其可視化。你應該小心，確保兩種方式的引用都是正確的，並且你可能會做一些適當的自檢，因此每個節點指向，指向同一個節點，否則你有一個完整性問題。

現在用於可視化。想想看這樣的（雙線表示雙鏈接）：

A = B = C 

說我要一個項目在末尾添加到這個列表中，我只需要告訴C到點到該項目，例如：

A = B = C - D 

，並指出該項目回：

A = B = C = D 

現在，如果我想移動d到另一個位置，說在第二，我可以讓參考節點「A」爲指向'd'：

A - B = C = D 
\_________/ 

有d點回到A

A - B = C - D 
\`========'/ 

有無ç不再指向d：

A - B = C D 
\`========'/ 

有d點到B：

 ______ 
    / \ 
A - B = C D 
\`========'/ 

具有B-點回到d：

 .===== 
    //  \\ 
A B = C D 
\`========'/ 

正如你現在可以看到，B不再指向一個，並在視覺上重新排列這可以解決問題：

C = B ===. 
      \\ 
A   D 
\`========'/ 

等於：

A = D = B = C 

如果你明白這一點，你可以做一個雙向鏈表上的任何操作。 a 謝謝你有機會做一些ascii藝術。

總結：你實際上沒有「清單」。您只有節點，指向指向其他節點的指向回或無（NULL）。