Удаление узла в двусвязном списке

Я работаю над функцией, которая удалит узел двусвязного списка. Вот мой заголовочный файл:

class LinkedList
{
private:
      struct Node
      {
         int data;
         Node *next;
         Node *previous;
      };

      int count;
      Node *head;
      Node *tail;

public:
      LinkedList() {head = NULL; tail = NULL; count = 0;} //Constructor

      void insert(const int );
      bool remove(const int );
      bool contains(const int );

      size_t lenght() {return count;}
};

Другие мои функции работают нормально, но моя функция удаления ломается во время выполнения. Когда я запускаю свой код, я получаю ошибку сегментации, и после 2 дней попыток выяснить ошибку в моей логике я обращаюсь к сообществу за помощью. Буду признателен за любую обратную связь на данный момент, спасибо. Вот моя функция удаления:

bool LinkedList::remove(const int item)
{//if the list is empty returns false
if(head == NULL) {return false;}

Node *hptr = head;
Node *tptr = tail;

if((hptr -> data) == item)
{//if the node is at the head of the list
  hptr = hptr -> next;
  delete head;
  hptr -> previous = NULL;
  head = hptr;
  --count;
  return true;

} else if((tptr -> data) == item) {
 //if the node is at the tail of the list
  tptr = tptr -> previous;
  delete tail;
  tail = tptr;
  tptr -> next = NULL;
  --count;
  return true;

} else {//if the node is in he middle of the list
  Node *ptr_head = head;   Node *ptr_headp = NULL;
  Node *ptr_tail = tail;   Node *ptr_tailp = NULL;

  while((ptr_head -> data) != item || (ptr_tail -> data) != item)
  {//pointers pass each other then data was not found
     if((ptr_tail -> data) < (ptr_head -> data)) {return false;}
   //traversing the list from the head and tail simultaniously
     ptr_headp = ptr_head;
     ptr_head = ptr_head -> next;

     ptr_tailp = ptr_tail;
     ptr_tail = ptr_tail -> previous;
  }

  if((ptr_head == ptr_tail) && ((ptr_tail -> data) == (ptr_head -> data)))
  {//the item is at the intersection of both head and tail pointers
     ptr_headp -> next = ptr_tailp;
     ptr_tailp -> previous = ptr_headp;
     delete ptr_head;
     delete ptr_tail;
     --count;
     return true;
  }

  if((ptr_head -> data) == item)
  {//the item is before middle node
     ptr_headp -> next = ptr_head -> next;
    (ptr_head -> next) -> previous = ptr_headp;
     delete ptr_head;
     --count;
     return true;
  }

  if((ptr_tail -> data) == item)
  {//the item is after the middle node
     ptr_tailp -> previous = ptr_tail -> previous;
    (ptr_tail -> previous) -> next = ptr_tailp;
     delete ptr_tail;
     --count;
     return true;
  }
}

return false;
}

person Samuel    schedule 25.09.2013    source источник


Ответы (2)


Это типичный пример ситуации, когда небольшое изменение структуры данных может значительно упростить логику за счет объединения случаев, которые иначе выглядят по-разному*.

Основная проблема с логикой заключается в том, что у вас есть много условий для проверки:

  • Удаление первого узла, за которым следуют другие узлы
  • Удаление последнего узла, которому предшествуют другие узлы
  • Удаление единственного узла
  • Удаление узла в середине

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

class LinkedList
{
private:
      struct Node
      {
         int data;
         Node *next;
         Node *previous;
      };

      int count;
      // The change begins here
      Node headTail;
      // End of the change

public:
      LinkedList() {head = NULL; tail = NULL; count = 0;} //Constructor

      void insert(const int );
      bool remove(const int );
      bool contains(const int );

      size_t lenght() {return count;}
};

Указатель head соответствует указателю next headTail; указатель tail является его previous. И следующий, и предыдущий указывают на себя в пустом списке.

Это немного неэффективно, потому что data из headTail не используется. Список становится круговым, всегда присутствует один узел. Имея этот узел, вы можете безопасно удалить любой узел в середине и обновить предыдущий и следующий указатели, как если бы они принадлежали разным объектам.


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

person Sergey Kalinichenko    schedule 25.09.2013
comment
Спасибо за отзыв Dasblinkenlight. Лекция была действительно интересной, жаль, что имя этого человека не запомнится... Попробую модифицировать свой код с учетом изменений в заголовочном файле. - person Samuel; 25.09.2013
comment
@Samuel Что значит не будет запоминаться? :) :) :) :) - person Sergey Kalinichenko; 25.09.2013
comment
лол, теперь эта вики-статья попадет в мои закладки. Спасибо еще раз :) - person Samuel; 25.09.2013

person    schedule
comment
Спасибо, но я скопировал/вставил это в свою функцию, и это все еще дает мне ошибку сегментации во время выполнения. - person Samuel; 25.09.2013
comment
Затем научитесь использовать отладчик и получите больше информации о том, почему. Код правильный. В вашем списке должно быть повреждение из-за какой-то другой операции. - person Dark Falcon; 25.09.2013
comment
Вы единственный, кто здесь говорит, что ваш код правильный. У тебя, должно быть, изъян в собственной логике. - person Samuel; 25.09.2013