Как перемещать элементы в дважды связанном списке?

Question

У меня есть собственный список (дважды связанный список, а не std :: list), реализованный в моем коде. Мое требование - переместить элемент на один левый или правый, обновив ссылки. Является ли это возможным?

class Elem 
{ 
    Elem *next; 
    Elem *prev; 
} 

.......

void move_element_left(Elem *e) 
    { 
    if(e->prev()==NULL) 
     return;   //Left most ... so return 

    Elem *left = e->prev(); 

    left->next() = e->next(); 
    e->prev() = left->prev(); 

    if (left->next()) 
     left->next()->prev() = left; 

    if (e->prev()) 
     e->prev()->next() = e; 

    e->next() = left; 
    left->prev() = e; 
    } 

.......

int main() 
{ 
    ElemList ls; 
    ... 
    ... 
    move_element_left(e); //e of type Elem * 
    ... 
} 

Приведенный выше код работает на 2-й объект в списке, который я хочу, за исключением переместитесь влево (или вверху). (То есть сказать, если список (obj5, obj9, obj11, obj12, ..), двигаясь obj9 к первому в списке дает ошибку)

Answer 1

См Bubble-sorting doubly linked list

Я полагаю, ваш класс Эля делает также содержать данные, так переместите данные или - если это простой указатель данных - поменяйте указатели: C++ Swapping Pointers.

Если это не возможно, я бы - от «Не повторяйте себе» точки зрения - повторно использовать эти простые связанный список функций, которые вы, скорее всего, уже есть:

void move_element_left(Elem *e) 
{ 
    Elem *left = e->prev(); 

    if(left) 
    { 
     remove_element(e); 
     insert_element_before(e, left); 
    } 
} 

Answer 2

Ниже приведен обновленный код. Вам нужно указать изменить указатель на голову, если левый указатель указывает на головку двойного связанного списка.

//**head is the address of pointer of head of double linked list 

      void move_element_left(Elem *e,Elem **head) 
      { 
      if(e->prev()==NULL) 
       return;   //Left most ... so return 

      Elem *left = e->prev(); 
      if(left==*head){ 
      *head=e; 
      } 

      left->next() = e->next(); 
      e->prev() = left->prev(); 

      if (left->next()) 
       left->next()->prev() = left; 

      if (e->prev()) 
       e->prev()->next() = e; 

      e->next() = left; 
      left->prev() = e; 
      } 

Answer 3

Работы по проекту?

После кода в схеме, показывает, что он работает как задумано:

void move_element_left(Elem *e) 
    { 
    if(e->prev()==NULL) 
     return;     //ok ! Left most ... so return 
    Elem *left = e->prev(); // ok ! (1) 
    left->next() = e->next(); // ok ! (2) 
    e->prev() = left->prev(); // ok ! (3) 

    if (left->next())   // ok ! 
     left->next()->prev() = left; // ok ! (4) 

    if (e->prev())    // ok ! e prev is left prev is null 
     e->prev()->next() = e; 

    e->next() = left;   // ok ! (5) 
    left->prev() = e;   // ok ! (6) 
    } 

Здесь схема (извините за ребяческой аспект ;-)):

Так список на самом деле прекрасен. Проблема в том, что ElemList, безусловно, содержит указатель на заголовок списка. И этот указатель по-прежнему указывает на старый первый и второй элемент. Таким образом, список больше не является обязательным.

Как это исправить?

Один выход, было бы сделать move_element_left() функция-член ElemList. В этом случае вы можете позаботиться об особом случае, когда e->left становится нулевым, и в этом случае вам нужно обновить указатель ElemList до первого элемента.