Trouble removing items within a double linked list.

[Neb1000]

I am working on a homework assignment where we have to make the class for a double linked list and when I test it Segmentation faults.

Code for remove: It should remove all instances of x in the list.

template<typename generic>
void List<generic>::remove(generic x)
{
	bool done = false;
	do
	{
		if(x == m_front -> data)
		{
			pop_front(); // removes first item and I know that this is not the problem
		}
		else
		{
			Node<generic>* temp = m_front;
			bool complete = false;
			do
			{
				if(temp -> b == NULL)
					done = true;
				if(temp -> data != x)
				{
					temp = temp -> b;
				}
				if(temp -> data == x)
				{
					temp -> b = temp -> b -> b;
					temp -> f = temp -> f -> f;
					m_size--;
					delete temp;
					complete = true;
				}
			}while(!complete);
		
		}
	}while(!done);
}

If you need more information I can put it on here. If any of you know a better way of removing the items that would also help. Thanks.

[ne555]

//you will delete temp
temp -> b = temp -> b -> b; //so, why bother adjusting its links?
temp -> f = temp -> f -> f;
m_size--;
delete temp;

You need to adjust the links of the cell before and after you (provided that they exist). You better encapsulate that behaviour in another method List::erase( Node*)

Also, your algorithm is inefficient. Why do you go back to the beginning after deleting one instance? You already know that all that path is clear.

Instead of using that flags, you could simply return or break

if(temp -> b == NULL)
	done = true; //done, but not complete, so the inner loop will keep going 

[zwA4jE8b]

yeah like ne555 said, you are updating the links for temp, but you are deleting temp, creating a hole in your list.

it might make more sense to use a node and call it 'next' and 'previous' take these nodes along with you on your search. then updating links is 'easier'. so if temp is sitting on the node to delete,

previous -> f = temp -> f;
next -> b = temp -> b;

so the node after temp links back to the one before temp and the node before temp links to the one after it.

also, drawing a picture and visualizing what you need it to do helps a lot.

This is my code for a single linked list. You should easily be able to adapt it to your doubly :)

template <class dType>
void OrderedLinkedList<dType>::insert(nodeType<dType> *newnode)
{
	nodeType<dType> *current, *trail;
		trail = head;
		current = head->link;
		while (current != tail && current->id < newnode->id)
		{
			trail = current;
			current = current->link;
		}
		newnode->link = current;
		trail->link = newnode;
		count++;
}

p.s. mine uses a grounded list structure, meaning there is a fixed head and tail node

[Neb1000]

Hmm... I think I know what you are saying but in the .h file there is no erase(Node*) function.
Here is the .h file:

#ifndef LIST_H
#define LIST_H

#include"node.h"
#include"listiterator.h"
#include<stdexcept>
using std::out_of_range;

template<typename generic>
class List
{
 public:
  List();
  List(const List& l);
  List& operator=(const List& l);
  ~List();
  void push_front(generic x);
  void pop_front();
  void push_back(generic x);
  void pop_back();
  void remove(generic x);
  generic& front();
  generic& back();
  const generic& front() const;
  const generic& back() const;
  void clear();
  unsigned int size() const;
  bool empty() const;
  typedef ListIterator<generic> Iterator;
  Iterator begin() const;
  Iterator end() const;

 private:
  unsigned int m_size;
  Node<generic>* m_front;
  Node<generic>* m_back;
};

#include"list.hpp"
#endif 

So is there still a way of doing this without going through the whole list every time?

[zwA4jE8b]

no with linked lists you must do a sequential search.. its one of the drawbacks

also, im not 100% sure but I think the header file should only declare the datatype for the parameter. not the variable name..

so List(const List& l); should be List(const List&);

and so on

[Neb1000]

It can be either, it is a matter of preference, my teacher gave me the .h file anyway. But I have changed my code and it still doesn't work. It keeps segmentation faulting.

Now it is:

template<typename generic>
void List<generic>::remove(generic x)
{
	Node<generic>* temp = m_front;
	if(m_front -> data == x)
	{
		pop_front();
	}
	if(m_back -> data == x)
	{
		pop_back();
	}
	while(temp -> b != NULL && m_size > 0)
	{
		if(temp -> b -> data != x)
		{
			temp = temp -> b;
		}
		else
		{
			Node<generic>* temp1 = temp -> b;
			temp -> b = temp -> b -> b;
			temp -> b -> b -> f = temp;
			delete temp1;
			m_size--;
		}
	}
}

I have stepped through it with pencil and paper multiple times and it should work but it doesn't.

[Zhuge]

On line 23, I have a suspicion you have too many ->b statements because you have already reassigned temp->b to point to the node before/in the b-direction of the node you are deleting.

[Neb1000]

Ok I see it, I guess I overlooked that. But it works now, thanks everyone.

[zwA4jE8b]

This will traverse your list and stop when it finds the node to delete or hits the end of the list. the while loop should only be one line. once the node is found you want to exit the while loop. also depending on what kind of field 'data' is and what direction you are going you either want to use >= or <= while searching for the node.

while(temp -> b != NULL && temp -> data >= x) temp = temp -> b;

next you need to double check the node is the correct node to delete, if not move on or output a message.

if(temp -> data == x)
{
//update links here
Node<generic>* next = temp -> b;
Node<generic>* previous = temp -> f;
previous -> b = temp -> b;
next -> f = temp -> f;
delete temp;
m_size--;
}
else
do whatever... exit, output a message.. so on


I am not sure what your pop_front and back function are, nor do i want to know.. but what I wrote should work, as long as the rest of it is working properly

[zwA4jE8b]

also, i apologize the code i gave you before was for my insert, here is delete for a single linked list...

template <class dType>
void OrderedLinkedList<dType>::deleteNode(dType todel)
{
	nodeType<dType> *current, *trail;

	if(!isEmpty())
	{
		trail = head;
		current = head->link;
		while (current != tail && current->id < todel)
		{
				trail = current;
				current = current->link;
		}
		if (current->id == todel)
		{
			trail->link = current->link;
			delete current;
			count--;
		}
		else
			cout << "The node to delete is not in the list!" << endl;
	}
	else
	{
		cout << "The list is empty!" << endl;
	}
}

[CppSpartan]

a hint

template<typename generic>
void List<generic>::remove(generic x)
{
	//pointers set to 0 zero in constructor
	if(m_front == 0){
		//list is empty
		return;
	}else{
		if(m_front -> data == x){
			//First node contains data
			Node<generic>* tmp = m_front; // create a tmp pointer to front
			m_front = m_front -> b; // move front pointer to next element
			delete tmp; // delete front element
			return;
		}else{
			//First was not what we looked for, iterate over collection
			if(m_front -> b == 0){
				//No more elements in list
				return;
			}
			while(){
				// Do something here , I leave that to you =)
			}
		}
	}
}