-
Dynamic Array Resizing
I am creating a list class using a dynamic array (later I will use a linked list). I am having trouble coming up with a good Add() function. Any help would be appreciated.
Private data members:
Code:
private:
int* list;
int end;
Constructor:
Code:
DList::DList()
{
end = -1;
list = new int[SIZE];
}
Add member function:
Code:
void DList::Add(int item)
{
int* temp = new int[Length() * 2];
end++;
if(end == (Length() - 1))
{
for(int i = 0; i < Length() - 1; i++)
{
temp[i] = list[i];
}
list = temp;
delete temp;
}
list[end] = item;
}
Above the Length() function returns the current size of the array - so if end of the array is equal to the length the array should double in size... This is where I am having problems, I dont know if the way I use the temp array above is correct.
Thanks in advance..
-
You may benifit from keeping a member that keeps track of the last valid element in your list, having end keep track of the maximum capacity for the list. That way, you only have to create a new array if cur == end. If that isn't true, then it's as simple as
Code:
list[end] = item;
end++;
also, once you delete temp (which should be deleted using delete []), list is still pointing to that memory. Instead, you would want to delete [] list, then set list = temp. There's a few more bugs in your code, but this should help you out.
-
what is end? wouldn't length-1 be the same thing? Your did end++ then tried to compare it to length-1 which would never work if your end and length variables are correct.
-
I thought end was the length of the list, my mistake.
-
No, end is the last entry in the array. So about deleting, I am alittle confused..
What you are saying is: the way I delete temp - leaves the memory allocated...?
So I need something to delete each entry in the array? ie: for loop?
-
Also, I am using Length() - 1 because my length function is implenmented to return the "logical" size of the array.. IE: if there is one entry in the array, its in spot 0, so the Length() with do a +1 and return there is "One" thing in the array -- hope this makes scense, its for the clients benefit.
Now I realize what you are saying - lenght is returning the end --- CRAP!!
-
Ok, I am clear with the delete - I forgot to use delete [], I must be drunk..
-
That's one thing, what I was also saying pertains to this:
Code:
list = temp;
delete [] temp;
You just demolished temp, which is the same stuff list was pointing to. When you try to index list, you're going to poking around in strange places you shouldn't be.
-
So...
Code:
delete [] list;
list = temp;
Is that better?
-
-
You should try experimenting with Vectors...
I guess you could look it up on the internet
#include <vector>
-
Is using vectors a more efficent way of allocating dynamic memory than a linked list?
-
Not 100% sure, I just know a vector is basically an array that can be dynamic, without any extra crap code :d, you can add and remove elements, with 1 or 2 commands...
-
It depends on what you are using it for. Generally, the standard library's vector or list (or deque, set, map, etc) containers are better to use than your own versions unless you are creating your own for learning purposes. Which of those you use depends on your requirements.
Whether you are trying to build your own, or using the standard versions, the dynamic array is often the first choice. Use linked lists for lots of insertions and/or removals from the middle of the list. There are other factors to consider as well.