Как поменять элементы в списке?

Question

Я пытаюсь узнать о структурах данных и алгоритмах самостоятельно. Я написал свой собственный двойной связанный список в C, и теперь я хочу написать некоторые алгоритмы для выполнения в списке. Каков предпочтительный способ обмена элементами списка? Лучше поменять местами содержимое или переставить указатели, которые указывают на следующий и предыдущий элемент списка?

Answer 1

Переставьте указатели. Обмен элементов данных может иметь побочные эффекты. В частности, вы, возможно, сохранили ссылку на узел где-то за пределами функции, и обычно , когда вы меняете порядок узлов в списке, вы не хотите, чтобы люди, имеющие ссылку на узел, вдруг обнаружите, что узел указывает на новые данные. Это потому, что обычно важной, идентифицирующей характеристикой узла являются данные, на которые он указывает , а не его положение в списке.

Answer 2

Я склонен быть на стороне того, что большинство людей уже сказали. Немного фона, вероятно, поможет: замена указателей гарантированно сработает, тогда как обмен объектами не всегда может быть таким простым, как кажется. Подумайте о временных временах, которые могут / будут создаваться, и исключения (и я имею в виду в целом, а не особенность языка C ++) могут возникнуть и фактически оставить ваш контейнер (список) в нежелательном состоянии. Ищите инварианты в вашем контейнере - это означает, что подкачка должна оставить размер списка без изменений, а также неповрежденные элементы и дизайн по ним.

Answer 3

Зависит от того, как вы разместили контент.

Если вы храните указатель на контент, переключение контента не имеет большого значения. Если у вас есть большая структура, которая является частью вашего узла, то переключение указателей может быть более эффективным, чем копирование всего содержимого.

Answer 4

В зависимости от типа содержимого, хранимого в элементах связанного списка, обмен фактическим содержимым элемента будет сложным (например, подумайте о связанном списке строк различной длины), поэтому проще поменять местами указатели которые указывают на следующий и предыдущий элементы списка.

Answer 5

Канонический обмен выполняется через перестановку указателя, не имеет побочных эффектов и, конечно, быстрее:

void swap (node *a, node *b) {
    node *tmp;

    tmp = a;
    a = b;
    b = tmp;
}