Linked list help

[sorthon123]

so i have been working with linked list lately in my computer science class and i have a program i have been working on for a little while and most of the stuff works in my class but i have been told on here plenty of times that my code is dirty and has allot of memory leeks in it, my question is can you all as a group help me clean up my code so it will run more efficiently and with less problems?

also the code contains a function that pushes things into a queue in order of their designated priority, it works when i take the setting the priority stuff out but does not work with it in.

#include <iomanip>
#include <iostream>
#include <typeinfo>
#include <cstdlib>
#include <string>

using namespace std;

// Specification file for a linked list abstract data type class.
// This linked list is actually a stack, since all additions and
// removals are at the head.
template<class type>
struct node // Each node has two fields:
{
type data; // a data field,
node<type> *next; // and a pointer field.
type priority;
};

template<class type>
class stack
{
private:
node<type> *head; // Pointer to the first cell.

public:

stack();
void push(type item);
void pushprior(type item, type priority);
type pop();
void view();
void pushqueue(type item, type priority);
};

template<class type>
stack<type>::stack()
{
head=NULL;
}

template<class type>
void stack<type> :: push (type item)
{
node<type> *t = new node<type>;
t -> data = item;
t -> next = head;
head = t;

}
//adds the int into the list and then sorts it to where it should be located
template<class type>
void stack<type>::pushqueue (type item,type priorityt)
{
node<type> *t = new node<type>;
node<type> *tmp = new node<type>;
node<type> *trail = new node<type>;
//trail = NULL;

if(head == NULL) //Startig the list
{
t-> data = item;
t->priority=priorityt;
t -> next = head;
head = t;
}
else if(head != NULL)
{
t = head;
while(t != NULL && priorityt > t->priority){ //Puts inside the list
trail = t;
t = t->next;
}
tmp->data = item;
tmp->priority=priorityt;
tmp->next = t;
trail->next = tmp;
}
}
// Function to remove the first element from the stack and
// return it to the caller.
template<class type>
type stack<type> :: pop ()
{

node<type>* cur;
cur = head;
if(cur == NULL)
{
cout<<"Nothing to pop"<<endl;;
}

else
{
head = cur -> next;
return cur->data;
delete cur;
}
}
// Accessor functions.
// Function to see whether an element is on the list.
template<class type>
void stack<type> :: view ()
{
node<type>* tmp = head;

while(tmp != NULL){
cout << tmp -> data;
tmp = tmp -> next;
cout<<endl;
}
cout<<endl;
}

int main()
{

stack<char> b;
stack<int> c;
b.pushqueue('6',3);
cout<<endl;
b.pushqueue('@',4);
cout<<endl;
b.pushqueue('b',2);

b.view();

}

one of the issues is the trail=NULL; when taken out the linked list replaces the last thing with the next thing added to the queue. and then when it is added i get a seg fault but i don't know where and according to my professor what i have should work ok.

[D80DSL3A]

Hi sorthon123, I have a couple of questions about your code:

1) Why do you allocate 3 nodes when you are pushing only 1 item onto the list?
I'm referring to lines 55-57 in your pushqueue():

node<type> *t = new node<type>;
node<type> *tmp = new node<type>;
node<type> *trail = new node<type>;

One new node is enough to store one new item + one pointer to the next node.

2) What exactly is the role of priority in your node structure? It looks like you want to use it to determine where to insert a new node in the existing list. Is this right?
If so, why is it a <type> object?
I see that the 2nd argument in your calls to pushqueue() in main() is an integer. This is what you are passing as a <type> object for priority.

I'm assuming that the integers are meant to determine the order of the items in the list so that this code:

b.pushqueue('6',3);
cout<<endl;
b.pushqueue('@',4);
cout<<endl;
b.pushqueue('b',2);
b.view();

would produce:

b6@

Is that right?

I'm replying because I just wrote an ordered list template class which is working well, so maybe I can help. The way I did the ordering of items was to rank them using the < operator, which must be overloaded in the <type> class. This works very naturally. The property determining priority (node order) should belong to the <type> object, not the node object.

Let me know if you wish to compare methods.

[sorthon123]

well the purpose of this is because it will lead up to my next program which takes reverse polish notation and infix notation and converts infix into reverse polish.

the purpose for all of the nodes was to keep track of where i was in the linked list and because it was a queue add it to the very back of the linked list and i am sure it will work with less thats just how i got it to work in a fit of confusion haha. The role of priority is how you stated, it needs to be in the queue in the order of priority how ever if the priority is the same it should be inserted in a first in last out method but i have not gotten around to writing that just yet.

i do have a program written that will take a stacked list and insert numbers into it in numerical order and i am trying to use the logic behind that and work in the same way but instead of comparing the data fields it compares the priority fields.

[D80DSL3A]

OK. I forgot to ask what your trail pointer is for. Is this to maintain a pointer to the last node in the list? I'm probably wrong about that though, since it would be named tail instead.

the purpose for all of the nodes was to keep track of where i was in the linked list

Would having the pushqueue() return a pointer to the new node accomplish this?

I can see having a data member of your node structure for storing priority but it seems that an integer would work better for that than a <type> object.

[sorthon123]

well i pretty much tossed out the trail node. and am now getting errors that dont make sence to me im getting a seg fault because it wont do my first step where it says if(head==NULL) then push in the number normally but apparently head isn't null ever when im pretty sure it should be.

[Zhuge]

This topic looks suspiciously the same as another...
http://cplusplus.com/forum/beginner/38376/

[sorthon123]

that is because we are in the same class and group i guess he posted it as well either way its code that i wrote haha i told him i already made a post but i guess he wanted to see if people would replay on his

[sorthon123]

so i have this code and its supposed to creat a priority queue and so far i have goten to where it puts them in the right order but, it is an infinite loop and ik how much you love an infinite loop. i know were the loop is accruing but what i dont get is why it puts them in the right order but not when i fix the loop.

template<class type>
void stack<type>::pushqueue (type item,int priorityt)
{
node<type> *t = new node<type>;
node<type> *tmp = new node<type>;

if(head == NULL) //Startig the list
{
t-> data = item;
t->priority=priorityt;
t -> next = head;
head = t;
}
tmp->next=head;
while(tmp->next != NULL ){ //Puts inside the list

tmp = tmp->next;
if(priorityt > t->priority)
break;
}
t->data=item;
t->priority=priorityt;
t->next=tmp->next;
tmp->next=t;


}

i know where the loop is occurring i just dont understand why it works with a infinite loop but not with a fixed loop

[D80DSL3A]

I adapted my own orderedList class to function like what you're after here. It works fine.

template<class T> struct node
{
	T data;
	int priority;
	node* next;
};

template<class T>
class orderedList
{
private:
	node<T> * head;
public:
	orderedList(void){ head = NULL; }
	~orderedList();
	node<T>* insert(const T& item, int Priority);// returns a pointer to the new node
	bool remove(int Priority);// returns true if item with Priority found in list, false if not
	void print(void);
};

template<class T>
orderedList<T>::~orderedList()
{
	int Ndeleted = 0;
	while(head)
	{
		node<T> *t=head;
        head = head->next;
        delete t;
		Ndeleted++;		
	}
	cout << Ndeleted << " node(s) deleted" << endl;
}

template<class T>
node<T>* orderedList<T>::insert(const T& item, int Priority)
{
	if(head)
	{
		// check against head->data	
		if( Priority < head->priority )
		{
			node<T> *t=new node<T>;
			t->data = item;
			t->priority = Priority;
			t->next = head;
			head = t;// new head
			return t;
		}
		// go further into list
		node<T> *iter = head;
		while( iter->next )	
		{
			if(  iter->next->priority < Priority )
				iter = iter->next;
			else
				break;
		}	
		// insert node 
		node<T> *t=new node<T>;
		t->data = item;
		t->priority = Priority;
		t->next = iter->next;
		iter->next = t;
		return t;
	}
	else// new item starts list
	{
		head = new node<T>;
		head->data = item;
		head->priority = Priority;
		head->next = NULL;
		return head;
	}
}// end of insert()

template<class T>
bool orderedList<T> :: remove(int Priority)
{
	node<T> *t = NULL;// local

        if(head)
        {
			if( Priority == head->priority )// delete head node
			{
		        t = head;
			    head = head->next;
				delete t;
				return true;
			}
			// go further into list
			node<T> *iter = head;
			while( iter->next )
			{
				if( Priority == iter->next->priority )
				{
					t = iter->next;
					iter->next = iter->next->next;
					delete t;
					return true;
				}
				else
					iter = iter->next;
			}
			return false;// value not found
        }

        return false;
}// end of remove()

template<class T>
void orderedList<T>::print(void)
{
	if(head)
	{
		node<T> *iter = head;
		do
		{
			cout << " " << iter->data;
			iter = iter->next;
		}while( iter );
	}
	else
		cout << "List is empty.";
	cout << endl;
}// end of print() 

I tested it with this:

int main(void)
{
	orderedList<char> List;
	
	List.insert('a', 5);	
	List.insert('b', 1);	
	List.insert('c', 2);	
	List.insert('d', 7);	
	List.insert('e', 4);

	List.print();
	
	List.remove(2);
	List.print();

	cout << endl;
	return 0;	
}

It gives this as output:

b c e a d
b e a d

4 node(s) deleted
Press any key to continue . . .

That's what you're trying to do isn't it?

[sorthon123]

thank you fun2code i grabbed what you did and made mine work the ways yours does it works, how ever it is pushing in the first item twice for example for your code i would get

b b c e a d

[sorthon123]

i got it to work, i had to use the returns that you made at the end of some of the things in the insert function. and then make the function node<type>* stack::insert...

i was trying to get away with having it void but i guess how you have it i cant get it to work that way.

could you explain exactly why you need to return t and head?

[sorthon123]

although a problem i am running into is if you try to push in an item with the same priority of 1 i get a seg fault

and now fixed haha

[D80DSL3A]

Funny thing! The insert() IS of type void in my own class. I modified it to return a pointer to the new node because you had said:

the purpose for all of the nodes was to keep track of where i was in the linked list

I figured that returning a node* would enable you to do this.

Here's the void type version:

template<class T>
void orderedList<T>::insert(const T& item, int Priority)
{
	if(head)
	{
		// check against head->data	
		if( Priority < head->priority )
		{
			node<T> *t=new node<T>;
			t->data = item;
			t->priority = Priority;
			t->next = head;
			head = t;// new head
			return;
		}
		// go further into list
		node<T> *iter = head;
		while( iter->next )	
		{
			if(  iter->next->priority < Priority )
				iter = iter->next;
			else
				break;
		}	
		// insert node 
		node<T> *t=new node<T>;
		t->data = item;
		t->priority = Priority;
		t->next = iter->next;
		iter->next = t;
		return;
	}
	else// new item starts list
	{
		head = new node<T>;
		head->data = item;
		head->priority = Priority;
		head->next = NULL;
		return;
	}
}// end of insert() 

I just tested it out using the same values of priority for some nodes. It worked for me in these cases. Not sure why it didn't work at first for you but glad you got it working.

P.S. I'm new to using template classes. Pretty awesome stuff!