双链接列表插入到特定列表函数

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

我需要首先创建这个表，然后添加到这个记录。

我的困难在于实现一个函数，该函数将要添加的值插入到这个特定的表中。我需要另一个插入功能，还是必须编辑我拥有的功能？

如果需要一个新的函数作为参数：一个指向结构类型的新表>代码> ListSt目< /C> >，要添加的记录的字符串和地址，我需要在参数中考虑我的列表的上一个和下一个记录吗？

我不确定插入后如何处理上一个和下一个指针。

有人能发布这样一个功能的实现吗？

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
 \`========'/

C不再指向D：

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

D指向B：

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

B点回到D点：

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

正如你现在看到的，B不再指向a，视觉上重新排列就解决了这个问题：

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

等于：

A = D = B = C

如果您了解这一点，就可以对双链接列表执行任何操作。a谢谢你给我机会做一些ascii艺术。

总结一下：你实际上没有一个“列表”。只有节点指向另一个向后指向的节点，或者不指向任何节点（NULL）。