Вставка двусвязного списка в функцию и параметры конкретного списка

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

Мне нужно сначала создать эту таблицу, а затем добавить к ней записи.

Моя проблема заключается в реализации функции, которая вставляет в эту конкретную таблицу значения, которые будут добавлены. Нужна ли мне другая функция вставки, или мне нужно отредактировать ту, которая у меня есть?

Если мне нужна новая функция, которая принимает в качестве параметров: указатель на новую таблицу типа struct 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
 \`========'/

У 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

Если вы понимаете это, вы можете выполнить любую операцию в двусвязном списке. и спасибо за возможность заняться искусством.

Подводя итог: у вас на самом деле нет "списка". У вас есть только узлы, указывающие на другой узел, который указывает назад, или на ничто (NULL).