изменение порядка элементов внутри связанного списка

Question

Я пытаюсь использовать простой связанный список:

struct index 
{ 
    struct index* next_element; 
    int data; 
    struct index* previous_element; 
} 

Каков наилучший способ изменить порядок элементов с точки зрения производительности? Например, у меня есть 1 2 3 4 5 6 7 8 и мне нужно 1 4 2 3 5 6 7 8.

Answer 1

Трудно сказать в целом. Кажется, что вы хотите переместить элемент 4 после элемента 1. У вас есть index* для обоих? Или вы просто знаете, что четвертый элемент должен двигаться на два места? Это, очевидно, влияет на количество переписчиков, которые вы должны делать.

В целом, для достижения максимальной эффективности, вы хотите функцию

void list_remove_unsafe_(index* i) { 
    // These two have to change (minimum needed) 
    i->previous_element->next_element = i->next_element; 
    i->next_element->previous_element-> = i->previous_element; 
    // We leave i itself unchanged (dangling) 
} 

и последующей деятельности

void list_insert_unsafe_(index* after, index* i) { 
    // These four have to change (minimum needed) 
    index* before = after->next_element; 
    i->previous_element = after; 
    i->next_element = before; 
    before->previous_element = i; 
    after->next_element = i; 
} 

Эти операции являются опасными, поскольку они временно покидают список в поврежденном состоянии и сделать много предположений (например, проверить начало/конец списков). Им нужна специальная обработка. Для основной операции эти 6 указателей записываются как минимум.