双向链表插入特定列表函数和参数

Question

我有以下代码，它是双向链表实现的一部分。然后我必须使用我的 ADT 实现来创建 value 形式的 table（这是一个字符串），address（它是 uint32_t 类型）（所以2 列 table)。

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

我需要先创建这个 table，然后向其中添加记录。

我的难点在于实现向这个特定 table 插入要添加的值的函数。我需要另一个插入功能，还是必须编辑现有的功能？

如果我需要一个新的函数作为参数：一个指向新的table类型struct listEntries的指针，字符串和要添加的记录的地址，我是否需要考虑在参数中我列表的上一条和下一条记录？

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

有人可以post实现这样的功能吗？

Answer 1

您唯一需要将项目插入（双向）链表的是引用节点，以及您要在该节点之前还是之后插入它的位置。解决这个问题的最佳方法无疑是将其可视化。您应该始终小心确保两种方式的引用都是正确的，并且您可能会很好地对其进行一些自我测试，因此每个节点指向，指向同一个节点，否则你有一个完整性问题。

现在进行可视化。可以这样想（双线代表双链接）：

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

如果你明白了这一点，你就可以对双向链表进行任何操作。一种并感谢您有机会做一些 ascii 艺术。

总而言之：您实际上没有 "list"。你只有节点，指向另一个指向后面的节点，或者什么都没有（NULL）。

Answer 2

所以这是我对我自己的问题的回答（已编译、测试并且有效）。我使用了迭代器，感谢上面的可视化，但我需要更多提示，比如迭代器这个词。

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

双向链表插入特定列表函数和参数

Doubly Linked List Insertion to Specific List function & parameters

c

doubly-linked-list