如何移動雙向鏈表中的元素？

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的指針更新爲第一個元素。