如何移动双向链表中的元素？

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 * 
    ... 
} 

上面的代码工作，除了在列表中的第二个对象，我想移到最左边（或最顶端）。 （即说，如果列表（obj5，obj9，obj11，obj12，..），列表中的obj9移动到第一给错误）

Answer 1

见Bubble-sorting doubly linked list

我假设你ELEM类并还含有数据，因此，移动数据或 - 如果它是一个简单的数据指针 - 交换指针：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的指针更新为第一个元素。