Re: My Double Linked List
Here is a sample app to show it in use.
PHP Code:
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#include <cDoubleList.h>
cDoubleList<int> dList;
//-----------------
//Main
//-----------------
int main()
{
if (dList.Empty()) {
cout << "LIST IS EMPTY" << endl;
}
dList.InsertFront(4);
dList.InsertFront(5);
dList.InsertEnd(2);
dList.InsertFront(7);
dList.InsertEnd(3);
dList.Insert(6, dList.Head());
dList.Insert(1, dList.Tail());
cout << dList.RemoveFront() << endl;
cout << dList.RemoveFront() << endl;
cout << dList.RemoveFront() << endl;
cout << dList.RemoveFront() << endl;
cout << dList.Remove(dList.Tail()->pPrev) << endl;
cout << dList.Remove(dList.Tail()->pPrev) << endl;
cout << dList.RemoveEnd() << endl;
if (dList.Empty()) {
cout << "LIST IS EMPTY" << endl;
}
int x = 0;
cin >> x;
}
Re: My Double Linked List
I need to get a grip on my c/c++ again. :(
Re: My Double Linked List
Looking good. You could also add some sort of search function so you don't have to keep using 'next'. It wouldn't make it any more efficient, but it would certainly make it easier to use.
Re: My Double Linked List
Looks fine. The next thing to do is to make sNode a private struct inside the list class and hide it from the user. Then, give the thing an iteration interface, so that the whole list can be traversed.
Re: My Double Linked List
Yah, I wanted to do that.
So far the struct could be private but then the Insert() and Remove() from artibrary nodes would no longer be possible.
I was pondering on a method of transversion through the list.
Re: My Double Linked List
The iterator interface of the standard library works really well. Try to emulate it.
Re: My Double Linked List
:)
I would love to but I need an explanation of the basic theory behind it.
Is it a compliation of Search functions?
Or does it allow a sort of random access? Does it ease tranversal?
A search func could be easy, pass in data and start from the head and compare the data to the data in each node.
Re: My Double Linked List
Simplified view here, as I'm not covering const iterators or reverse iterators here.
An iterator is an object that acts very much like a pointer in that you can, depening on the category:
1) Dereference it using *. (This applies to all iterators.)
2) Apply both pre- and postincrement (++) to it. (This applies to all iterators.)
3) Use -> to call methods on referenced objects. (This applies only to forward iterators or better.)
4) Create a copy of it using a copy constructor or an assignment operator. This copy references the same object initially, but can be modified independently. (This applies only to forward iterators or better.)
5) Apply both pre- and postdecrement (--) to it. (This applies only to bidirectional iterators or better.)
6) Apply +, -, += and -= with an integer argument to it to modify its position, or use - to calculate the distance between two iterators. (This applies only to random access iterators.)
A linked list would support bidirectional iterators.
As far as the container goes, the interface is thus:
1) The iterator type is called 'iterator' and is a nested type of the container. Thus, container<T>::iterator gets a suitable iterator type.
2) The member function begin() returns an iterator that points to the first element of the container, in iteration order.
3) The member function end() returns an iterator that points one past the last element of the container, in iteration order. This means that dereferencing the end iterator yields undefined behaviour.
As such, the iterator loop is:
Code:
container<int> c;
c += 1, 2, 3, 4, 5, 6; // This requires a Boost library to work - it simply puts a few elements into the container.
for(container<int>::iterator it = c.begin(); it != c.end(); ++it) {
}
Note that the pre-increment is important, as the post-increment creates temporary copies of the iterator that waste time, since they aren't used.
So your iterator would store a pointer to its current node, on dereferencing return a reference to the node's data field, and on in- and decrementing replace the current node by the next or previous one.
At least in release mode, iterators don't do error checking. If you overflow, you overflow.
Re: My Double Linked List
Ah yes, that makes a ton of sense.
Doesn't seem like to hard a task.
So that last snippet you posted goes along with my first mis-understanding.
A list's pointers are not fluent.
pHead+1 != pHead->pNext
so the custom iterator would have to have its own pre increment code added, so in the for loop you posted, ++it actually would have to returns the current nodes ->pNext right?
Re: My Double Linked List
Quote:
so the custom iterator would have to have its own pre increment code added, so in the for loop you posted, ++it actually would have to returns the current nodes ->pNext right?
Right -- you'll probably want to overload both the pre and post increment operators.
Code:
//pre increment
myiterator& myiterator::operator++()
{
// ...
return *this;
}
// post increment
myiterator myiterator::operator++(int)
{
// ...
return new_myiterator;
}
Re: My Double Linked List
How would the declaration of iterator look in a class?
Sunburnt I didnt quite follow...
for(container<int>::iterator it = c.begin(); it != c.end(); ++it)
-I assume in this case iterator is type int*
-My list class begin() would return the head, end would be the tail, thus I get confusion. But if +it returns pNext on the tail it will be NULL.
- When ++it occurs, in my list class it would have to return the current nodes pNext member since none of the memory can be guarantee'd to be aligned. Each list index is created with a new call. (If I had a custom memory pool I suppose I could get rid of that problem quickly, but I'm goona save that for next game engine).
Re: My Double Linked List
Any double linked list should have the following fuctions:
move first
move next
move previous
move last
get current item
I did not see any of those...
Also, you were talking about a search function, wich one is it ? i don't see it.
Re: My Double Linked List
No, it should not. No container should ever have an iteration state, it just cries for trouble.
Re: My Double Linked List
I agree with CB, who has yet to lead me wrong.
Implmenting those kinda functions would definetly lead to more trouble than ease.
I am however able to write an iterator specific to the double list...
I am yet to see the connection that can be made to write an iterator for anything.
Re: My Double Linked List
OK, I learned linked lists, and double linked lists at school and i learned it pretty well, but I just don't get what you guys are talking about....
A double linked list where you only put data in it ??? That totaly does not makes sence to me... what's the use then ? I mean wherever you put data, you need to read it...
The code you have, looks more like a stack... wich is both FIFO (First in first out), and FILO (First in, last out). Only in a stack you don't iterate through the nodes...
Re: My Double Linked List
Iteration is necessary, but the methods your described are the wrong way to go about it. That's because they hold the iteration position within the container, which means there can be only one iteration position, which means there can only be one iteration at a time. Even in a single-threaded environment this means that, for example, you can't perform any operations where each element of the container must be matched against each other, like:
Code:
int array[100];
for(int i = 0; i < 100; ++i) {
for(int j = 0; j < 100; ++j) {
cout << array[i]*array[j] << ' ';
}
}
The iteration state (= the current element) must be held in an object separate from the container. This object is usually called the iterator, and the C++ standard library recommends a common interface for all such iterator objects.
Re: My Double Linked List
OK, I get it now... if you have the iterator built in the doule linked list, you can't read data for a multithreaded application (or something like that)...
But to use it like the array example, you can do it with a single iterator too, but it takes more processing because it's moving back and forth a lot...
To avoid to make an extra iterator class to do only the iteration, you can include the iteration in the container (so it will have one iteration as I originally said), but make a copy constructor, and when you copy, don't actually make a copy to the whole data, just to the head and tail pointers, so then the copy will iterate the same data. (just an idea...) That way you won't have to expose the node structure since it's doing everyting internally in one class
Re: My Double Linked List
I have read in many places that the linked list is what the array isn't.
No random access but items are added in constant time.
I do not think a list should have the ability to go dList[1] = ... Overloading the [] for a list container.
I think it would be better to use an iterator interface and do something like
itr = dList.Head();
itr++ is actually itr = itr->pNext
Which is whats been pointed out.
