Linked List

[Taztingo]

I'm having trouble with my Linked List. For some reason my sort function will not work. I was able to solo it down to the push_back function, but it still refuses to work! For some reason the head of the linked list keeps getting replaced. Any advice would be very helpful :).

#include <iostream>
#include <stdlib.h>
using namespace std;

class List
{
	private:
		Node *head;
		int length;
	
	public:
		List()
		{
			head = NULL;
			length = 0;
		}

		/***************************************

			Remove All Functions Below		

		***************************************/
		Node* getPrevious(Node* node)
		{
			Node* temp = head;
			Node* previous = head;

			if(node == head)
				return NULL;

			while(temp && temp != node)
			{
				previous = temp;
				temp = temp->getNext();
			}

			return previous;
		}

		Node* getIndex(int n)
		{
			Node* temp = head;
			for(int i = 0; i < n && temp; i++)
			{
				temp = temp->getNext();
			}
			return temp;
		}

		void setHead(Node* n)
		{
			head = n;	
		}

		void setLength(int i)
		{
			length = i;
		}

		int getLength()
		{
			return length;
		}

		int countNodes(int value)
		{
			Node* temp = head;
			int count = 0;

			while(temp)
			{
				if(temp->getValue() == value)
					count++;
				temp = temp->getNext();
			}

			return count;
		}

		void print()
		{
			Node* temp = head;
			while(temp != NULL)
			{
				cout << temp->getValue() << " ";
				temp = temp->getNext();
			}
			cout << endl;
		}

		void push_front(Node* newNode)
		{
			newNode->setNext(head);
			head = newNode;
			length++;
		}


		/***************************************

			Remove All Functions Above		

		***************************************/

		Node* front()
		{
			return head;
		}

		const Node* front() const
		{
			return head;
		}

		Node* back()
		{
			Node* temp = head;
			while(temp->getNext())
				temp = temp->getNext();
			return temp;
		}

		const Node* back() const
		{
			Node* temp = head;
			while(temp->getNext())
				temp = temp->getNext();
			return temp;
		}

		Node* begin()
		{
			return head;
		}

		const Node* begin() const
		{
			return head;
		}

		Node* rbegin()
		{
			
			Node* temp = head;
			if(length == 0)
				return NULL;
			while(temp->getNext())
				temp = temp->getNext();
			return temp;
		}

		const Node* rbegin() const
		{
			Node* temp = head;
			if(length == 0)
				return NULL;
			while(temp->getNext())
				temp = temp->getNext();
			return temp;
		}

		Node* end()
		{
			Node* temp = head;
			while(temp)
				temp = temp->getNext();
			return temp;
		}

		const Node* end() const
		{
			Node* temp = head;
			while(temp)
				temp = temp->getNext();
			return temp;
		}

		Node* rend()
		{
			return NULL;
		}

		const Node* rend() const
		{
			return NULL;
		}

		int size() const
		{
			return length;
		}

		/*Implement this
		*/
		int max_size() const
		{
		}

		bool empty() const
		{
			if(head == NULL)
				return true;
			
			return false;
		}

		void push_front(const int val)
		{
			Node* newNode = new Node;
			newNode->setValue(val);
			newNode->setNext(head);
			head = newNode;
			length++;
		}

		void pop_front()
		{
			head = (head->getNext());
			length--;
		}

		void pop_back()
		{
			Node* temp = getPrevious(rbegin());
			temp->setNext(NULL);
			length--;
		}

		void push_back(const int val)
		{
			Node* newNode = new Node;
			newNode->setValue(val);
			newNode->setNext(NULL);
			if(length == 0)
			{
				head = newNode;
				cout << head->getValue() << endl;

			}
			else
			{
				cout << head->getValue() << endl;
				(rbegin())->setNext(newNode);
			}
			newNode->setNext(NULL);
			length++;
		}

		Node* insert(Node* position, Node* newNode)
		{
			Node* prev = head;

			if(position == head)
			{
				push_front(newNode->getValue());
			}
			else
			{
				prev = getPrevious(position);
				prev->setNext(newNode);
				newNode->setNext(position);
				length++;
			}

			return newNode;
		}

		/*Fix insert*/
		void insert(Node* position, int n, Node* newNode)
		{
			for(int i = 0; i < n; i++)
			{
				Node* temp = newNode->getCopy();
				insert(position, temp);
			}
		}

		/*Do this*/
		void insert(Node* position, Node* first, Node* last)
		{
		}

		/*Need to free memory*/
		Node* erase(Node* removeMe)
		{
			Node* temp = removeMe;
			Node* prev;

			if(temp == head)
			{
				head = head->getNext();
			}
			else
			{
				prev = getPrevious(removeMe);
				prev->setNext(temp->getNext());
			}
			length--;
				
			return temp;
		}

		/*Need to free memory*/
		Node* erase(Node* start, Node* end)
		{
			Node* prev;
			Node* temp = start;

			if(start == head)
			{
				while(temp && temp != end->getNext())
					temp = temp->getNext();
				head = temp;
			}
			else
			{
				prev = getPrevious(start);
				while(temp && temp != end->getNext())
					temp = temp->getNext();
				prev->setNext(temp);
			}
			return NULL;
		}

		void swap(List* swap)
		{
			Node* temp;
			int temp2;

			temp2 = swap->getLength();
			swap->setLength(length);
			setLength(temp2);
			temp = swap->getIndex(0);
			swap->setHead(head);
			head = temp;
		}

		void clear()
		{
			Node* temp = head;
			Node* temp2;
			while(temp)
			{
				temp2 = temp;
				temp = temp->getNext();
				delete(temp2);
			}
			head = NULL;
			length = 0;
		}

		void remove(int i)
		{
			Node* temp = head;
			Node* prev;
			Node* nextNode = head;

			while(temp)
			{
				if(temp->getValue() == i)	//A match
				{
					prev = getPrevious(temp);
					nextNode = temp->getNext();
					erase(temp);
					temp = nextNode;
				}
				else
					temp = temp->getNext();				
			}
			
		}

		void unique()
		{
			bool hitNode;
			Node* temp = head;
			int* array = (int*) malloc(sizeof(int) * length);
			
			while(temp)
			{
				if(countNodes(temp->getValue()) > 1)
					erase(temp);

				temp = temp->getNext();
			}
		}

		void merge(List* otherList)
		{
			List* newList = new List;
			Node* thisTemp = head;
			Node* otherTemp = otherList->getIndex(0);		

			while(thisTemp && otherTemp)
			{
				if(thisTemp->getValue() < otherTemp->getValue())
				{
					newList->push_front(thisTemp);
					thisTemp = thisTemp->getNext();
					cout << "This temp: " << thisTemp->getValue() << endl;
					pop_front();
				}
				else
				{
					newList->push_front(otherTemp);
					otherTemp = otherTemp->getNext();
					cout << "Other temp: " << otherTemp->getValue() << endl;
					otherList->pop_front();
				}
			}

			if(thisTemp)
			{
				while(thisTemp)
				{
					newList->push_front(thisTemp);
					thisTemp = thisTemp->getNext();
					pop_front();
					
				}
			}
			else if(otherTemp)
			{
				while(otherTemp)
				{
					newList->push_front(otherTemp);
					otherTemp = otherTemp->getNext();
					otherList->pop_front();
				}
			}

			cout << "Made it here" << endl;
			swap(newList);
			//delete(newList);
		}

		void sort()	//Crappy bubble sort, but w/e
		{
			int* tempArray = (int*) malloc(sizeof(int) * length);
			Node* tempPointer = head;
			int tempData = 0;
			int iTemp = 0;
			int tempLength = 0;
			int value = 0;

			
			while(tempPointer)
			{
				tempArray[iTemp] = tempPointer->getValue();
				tempPointer = tempPointer->getNext();
				iTemp++;
			}
			tempLength = length;
			clear();

			for(int i = 0; i < tempLength; i++)
			{
				for(int i2 = i; i2 < tempLength; i2++)
				{
					if(tempArray[i2] < tempArray[i])
					{
						tempData = tempArray[i];
						tempArray[i] = tempArray[i2];
						tempArray[i2] = tempData;
					}
				}
			}

			//Creates nodes
			cout << "Length: " << tempLength << endl;
			for(int i = 0; i < tempLength; i++)
			{
				value = tempArray[i];
				push_back(value);
			}
		}

		~List()
		{
			clear();
		}
};

int main()
{
	List list1;
	List list2;

	list1.push_front(22);
	list1.push_front(44);
	list1.push_front(66);
	list1.print();

	list2.push_front(50);
	list2.push_front(99);
	list2.push_front(77);
	list2.push_front(77);
	list2.push_back(77);
	list2.push_back(77);
	list2.push_back(77);
	list2.push_back(99);
	list2.print();

	list2.unique();
	list2.print();

	//list1.merge(&list2);
	list1.sort();
	//list1.print();

	
	//list.insert((list.begin())->getNext(), 5, &newNode);
	//list.insert(newNode.getNext(), &newNode2);
	//list.insert(list.front(), &newNode);
	//list.insert(list.front(), &newNode2);
	//list.insert(list.front(), &newNode3);

	//list.print();
	return 0;
}

[intmain311]

hi,
please explain what the push_back function is expected to do and what your class does
also, you should not define the functions inside the class definition for they are automatically defined as inline functions
for example:

class List
{
     List(){               //inline function
           whatever=stuff;
     }                       
     List(int i);          //normal function
};
List::List(int i)
{
     whatever=stuff;
}

inline functions are good for small amounts of code but can reverse efficiency if too complex
its just better to do it the c++ way ;)

[Taztingo]

My push_back function is supposed to take a value and create a node for it, and then add it to the end of the Linked List. If the Linked List is empty it makes it the head.

The Linked List class is just a list of nodes, and the list stores the first node. The other nodes can be accessed from the head and going down the line.

Here is an example:

List list = new List();
push_back(7);
----Head of List contains 7--------
push_back(8);
-----Head of List contains 7, and (7 node) is connected to (8 node)
push_back(9);
-----Head of List contains 7, and (7 node) is connected to (8 node), and (8 node) is connected to (9 node)

I hope that helps, and thank you for the advice. How does it reduce efficiency? Just by the way it looks or does it slow down the program?

[intmain311]

very interesting class, could you post the node class?

inline functions increase efficiency if used correctly--instead of taking the time to push all the local variables, it simply uses the memory address of the function

void inline func(int x)
{
cout<< "inline function";
}
void inline func(int x) <-- inline is ignored with recursion or complex statements
{
cout<<"not inline";
func(x+1);
}

functions defined directly in a class def is inline

its also a good practice and for readability

[Taztingo]

Sure here is the Node class

class Node
{
	private:
		int value;
		Node *next;

	public:
		Node()
		{
			value = 0;
			next = NULL;
		}
		
		~Node()
		{
			value = 0;
			if(next)
				free(next);
		}

		Node* getNext()
		{
			return next;
		}

		int getValue()
		{
			return value;
		}

		void setNext(Node* newNode)
		{
			next = newNode;
		}

		void setValue(int val)
		{
			value = val;
		}

		bool equal(Node* n)
		{
			if(this == n)
				return true;
			return false;
		}

		Node* getCopy()
		{
			Node* newNode = new Node;
			newNode->setValue(value);
			newNode->setNext(next);
			return newNode;
		}

	
};

[intmain311]

where is the error at push_back()? it seems to work fine

i traced your code and found an error at line 338: i think the loop goes on forever... it crashes and says segmentation fault, i am still trying to figure it out

your program crashes when you call the 'sort' because it calls the clear()

could you explain what the clear() does and could you make sure that the memory locations at the pointers are always correct

i am sorry if this is taking some time i will let you know as soon as i figure this out ;)

have you tried a debugger?