double linked list, removeAtTail busted?

[Smooth23]

I can't figure out what is going on with this bit of code. I'm building a double linked list.
when i call this function inside my find/remove i get a seg fault.

template <class T>
void LinkedList<T>::removeAtTail()
{
  if (m_tail == NULL)
    throw std::length_error("Linked list is empty");
  else
  {
    if (m_size == 1)
    {
      m_tail = NULL;
      m_head = NULL;
      m_size = 0;
    }
    else if (m_size > 1)
    {
      Node<T> *temp = new Node<T>();
      temp = m_tail;
      m_tail = m_tail->m_prev;
      delete temp;
      m_tail->m_next = NULL;
      m_size--;
    }
  }
}

and this is my find-one-instance and remove that node function:

template <class T>
bool LinkedList<T>::removeFirstOccurrence(const T& x)
{
  bool found=false;
  Node<T> *trav = m_head;
    while ((!found) && (trav != NULL))
    {
      if (trav->m_data == x)
      {
        if ((trav == m_head) && (trav !=m_tail))
        {
          m_head = trav->m_next;
          m_head->m_prev = NULL;
          m_size--;
          found = true;
        }
        else if (trav == m_tail && (trav !=m_head))
        {
          removeAtTail();
          found = true;
        }
        else if ((trav == m_head) && (m_head == m_tail))
        {
          removeAtHead(); //this works
          found = true;
        }
        else
        {
          trav->m_prev->m_next = trav->m_next;
          found = true;
          m_size--;
        }
      }
      trav = trav->m_next;
    }
  return found;
}

any ideas...please?

[Smooth23]

bump, anyone?

[coder777]

when i call this function inside my find/remove i get a seg fault.

What is the situation when that happens (how many nodes are in that list). Are you able to reproduce it?

[roberts]

      Node<T> *temp = new Node<T>();
      temp = m_tail;
      m_tail = m_tail->m_prev;
      delete temp;
      m_tail->m_next = NULL;
      m_size--;

Correct me if I'm wrong, but aren't you leaking here? You allocate memory to temp, then assign it a different address, thus losing the address of the memory you just allocated.

Secondly, you delete temp, which is holding the address of m_tail, so it is actually deleting m_tail, then you attempt to assign NULL to one of its data members.

[coder777]

@roberts

leak yes: due to the needless new Node<T>();
deleting m_tail no: due to the line above the delete m_tail = m_tail->m_prev;

[roberts]

ok, been a while since I rolled a linked list. I missed that detail.

But, otherwise, it should be a straight pointer assignment without an allocation.

[cire]

Generally a list of this sort manages the memory for its nodes. Why, then, when you remove a node, is there no memory being deallocated?

In line 29 of removeFirstOccurrence you update trav->m_prev->m_next to point to trav->m_next. Where is the corresponding update for trav->m_next->m_prev?

Why are you allocating memory in removeAtTail and throwing it away?

You're using pointers rather haphazardly. I wouldn't be surprised to learn the problem was in another method.

[coder777]

Well, removeFirstOccurrence() looks very wrong. On line 29 you set the next of the previous, but what about the previous of the next?

I would have expected something like this:

template <class T>
bool LinkedList<T>::removeFirstOccurrence(const T& x)
{
  bool found=false;
  Node<T> *trav = m_head;
    while ((!found) && (trav != NULL))
    {
      found = (trav->m_data == x);
      if(found)
      {
          if(trav->m_prev != NULL)
            trav->m_prev->m_next = trav->m_next;
          else // it must be the head
            m_head = trav->m_next;
          if(trav->m_next != NULL)
            trav->m_next->m_prev = trav->m_prev;
          else // It must be the tail
            m_tail = trav->m_prev;
          m_size--;
      }
      else
        trav = trav->m_next;
    }
  return found;
}

Not tested!