Member Avatar for Dimitar

Hello everyone,

I am trying to pre-allocate a certain number of nodes to a linked list, I allocate 10 nodes at first and, if I have more data to store, I'll need to resize it by adding half of the total number of nodes, sort of like 10, second time 5, and the third time is 15/2=7 nodes. It is giving me 2 errors C2664 on lines 154 and 163, where I'm trying to add nodes it is saying that I can't convert from const int to const staticList<T>::Node<T>. And also I'm trying to insert about a million of same same data elements.
Please Help :)

Thank you!

#pragma once
#include <iostream>
#include <ctime>
using namespace std;

template <class T>
class dynamicList
{
public:
	dynamicList(){Head=Tail=NULL;Count=0;}
	~dynamicList(){Clear();}
	dynamicList(const dynamicList<T> & other)
	{
		Head=Tail=Null;
		Count=0;
		*this=other;
	}
	const dynamicList<T> &operator =(const dynamicList<T> & rhs)
	{
		Node<T>* tmp; 

		if (this != &rhs)
		{
			Clear(); 
			tmp = rhs.Head; 
			while (tmp != NULL)
			{
				AddToRear(tmp->Data); 
				tmp = tmp->Next;
			}
		}
		return *this;
	}
	bool isEmpty(){return Head==NULL;}
	void Clear()
	{
		Node<T> *Tmp; 

		while (!isEmpty())
		{
			Tmp = Head; 
			Head = Head->Next;
			delete Tmp; 
			Count--; 
		}
		Tail = Head = NULL;
		Count = 0; 
	}
	void AddToRear(const T& item)
	{
		if (isEmpty())
		{
			AddToFront(item); 
		}
		else
		{
			Tail->Next = new Node<T>(item); 

			Count++;
			Tail = Tail->Next; 
		}
	}
	void AddToFront(const T& item)
	{
		Node<T> *Tmp;

		Tmp = new Node<T>(item); 

		Tmp->Next = Head; 
		Head = Tmp; 
		Count++;
		if (Count == 1)
			Tail = Head; 
	}
private:
	template <class T>
	class Node
	{
	public:
		Node() {Next = NULL;}
		Node(const T& item) {Data = item; Next = NULL;}
		T Data;
		Node<T> *Next;
	};
	Node<T>*Head, *Tail; 
	int Count;  

};











//using pre-allocation 
template <class T>
class staticList
{
public:
	
	~staticList(){Clear();}
	staticList()
	{
		Head=Tail=NULL; count=0;listSize=0;
		count=numNodes;
		ptrArray=new T[count];
	}

	bool isEmpty(){return Head==NULL;}
	void Clear()
	{
		Node<T> *Tmp; 

		while (!isEmpty())
		{
			Tmp = Head; 
			Head = Head->Next;
			delete Tmp; 
			count--; 
		}
		Tail = Head = NULL;
		count = 0; 
	}
	void expandlist(staticList *& P, int nodeCount)
	{
		staticList *ptr=NULL;
		nodeCount=0;
		listSize=10;
		if(nodeCount==0){ptr++;}
		else
		{
			nodeCount+=(listSize/2);//allocate half size
			//nodeCount(list length);
				ptr=new staticList[nodeCount];
			for(int k=0; k<nodeCount;k++)
				ptr[k]=P[k];
			delete[] P;
			P=ptr;
			ptr=NULL;
		}
	}
	void AddToRear(const T& item)
	{
		staticList *P;
		
		int numNodes=10;
		for(int i=0; i<numNodes;i++)
		{
			Head=new Node<T>(item);
		}
		count=numNodes;
		while(listSize==count && item!=NULL)
		{
			expandlist(P, count);
			count+=numNodes;
			for(int i=0; i<numNodes;i++)
			{
				Tail->Next=new Node<T>(item);
			}
		}
	}



	const staticList<T>& operator[](int idx)const
	{
		assert(idx>=0 && idx<count);
		return data[idx];
	}

	T *ptrArray;
private:
	template <class T>
	class Node
	{
	public:
		Node() {Next=Tail= NULL;}

		T Data;
		Node<T> *Next;
	};
	Node<T>*Head, *Tail; 
	int count;	  // total number of nodes allocated at the moment
	int numNodes; // number of nodes in the array
	int listSize; // current size of the list

};


class stopwatch
{
public:
	stopwatch(): start(clock()){}//start counting time
	~stopwatch()
	{
		clock_t total=clock()-start;
		cout <<"total of ticks for this activity: "<< total<< endl;
		cout<<"in seconds: "<<double(total)/CLOCKS_PER_SEC<<endl;
	}
private:
	clock_t start;
};
  • 3 Contributors
  • 4 Replies
  • 420 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Dimitar
Member Avatar for Bench

Why would you want to pre-allocate memory for a linked list? If you want to do that, you may aswell use a vector (or a deque).

Edited by Bench because: n/a
Member Avatar for Dimitar

The thing is that in my cpp file I'll be timing both the dynamic and the list with pre-allocated nodes. I think that the one with pre-allocation should be faster, but the downside will be when I'm trying to add the last few items and I pre-allocate a huge chunk of memory, which is going to be a waste :)

Member Avatar for mrnutty

>> I think that the one with pre-allocation should be faste

First rookie mistake, pre-optimization!

Forget about it using pre-allocation. Just do it without it. It will definitely be fast
enough, unless you have some special case.

Member Avatar for Dimitar

Well my first list that is without pre-allocation is done, the problem is with the other linked list that does pre-allocation. I need to do it because it's an assignment :) In my file here, I'm trying to make a function that creates arrays of nodes and then I pass it to my AddToRear function. But the thing is that it gives me an error when I try to do something like Head=new Node<T>(item); and again that's in the staticList class. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.