Your thoughts on this doubly-linked list

**ArlexBee-871RBO** · 06-21-2008

For our lab 1 our professor has given us an assignment to create a doubly-linked list template class. He is actually calling it a database, but it's really a doubly linked list. I've finished the assignment, but thinking about it I've realized that I don't really like his requirements/design for this class.

His assignments states that we need to create a template class (named UBArray for UnBounded Array). Two template arguments will be used, (a) the first will be the data type to be stored, (b) the second is the data type of the index of the array (default to integer). Allow an unlimited number of elements. Elements will not be created unless they are used. A subscript operator [], and a function At which operates in the same way as the subscript operator. Also, the usual member functions such as GetFirst, GetLast, Remove, etc.

My problems is this: The data type that's chosen for the Index needs to support comparison operators because the list is sorted based on the value of the Index, not the Data. Is that wise? Of all the examples I've seen on the net, none of them are designed this way. So in reality we get two types of data in the Node, one is used for sorting and the other is the actual data that we need to be stored. Shouldn't we just get rid of Index?

Code:

//UBArray<DATA, INDEX>
//DATA &At(const INDEX &)

UBArray<double, int> uB;
for(int i = 0; i < 100; i++){
    cout << uB.At(i) << endl;
}

The above code shows another problem, and I can't come up with a way to fix it without getting rid of Index argument. At() is called 99 times but no value is assigned to data, but memory gets allocated for each node. How can I make sure a constant version of At() is called when only reading the list so unnecessary allocation doesn't occur?

**Raigne** · 06-21-2008

Generally, Linked Lists are sorted by order of insertion. First in Last out kinda thing. Although I am definitely not an expert, so please do not quote me on that.

**tabstop** · 06-21-2008

Originally Posted by ArlexBee-871RBO

The above code shows another problem, and I can't come up with a way to fix it without getting rid of Index argument. At() is called 99 times but no value is assigned to data, but memory gets allocated for each node. How can I make sure a constant version of At() is called when only reading the list so unnecessary allocation doesn't occur?

All At should do is walk forward i times and then spit out the value.

**iMalc** · 06-21-2008

The idea of having a doubly-linked-list being indexed by position through something like an 'At' function of [] operator is fundamentally broken! You've basically been asked to implement a C++ map container but with a data structure that gives O(n) access time rather than O(log n).

However, given this is C++, when there is no such item at the index provided to 'At', then the propper thing to do would be to throw an exception. That will prevent unnecessary allocations if it doesn't exist.

**ArlexBee-871RBO** · 06-21-2008

Originally Posted by tabstop

All At should do is walk forward i times and then spit out the value.

Well in this case At() is used to read and write data.

Code:

int x = 3;
At(x) = 784.

The index 3 stores 784. To read index 3 you would call At(x), and if index doesn't exists in the list, say x = 7, then a node is created with index 7 but no value is assigned to data in the node when reading the list.

EDIT:That's the way he wants us to do it.

**tabstop** · 06-21-2008

Does this really have to be a linked list? This smells a lot like an array-type thing.

**iMalc** · 06-22-2008

I think some people are not clear here on how this needs to work, including the OP.

Elements will not be created unless they are used.

The means that if I declare a UBArray and do:

Code:

At(999999999) = 42;

then only element 999999999 should exist!

But back to your original problem:

My problems is this: The data type that's chosen for the Index needs to support comparison operators because the list is sorted based on the value of the Index, not the Data. Is that wise? Of all the examples I've seen on the net, none of them are designed this way. So in reality we get two types of data in the Node, one is used for sorting and the other is the actual data that we need to be stored. Shouldn't we just get rid of Index?

Yes that is actually very wise. In fact the std::map container works exactly that way and requires the same thing. Whatever examples you looked at were not as closely related to the problem. No you can't get rid of index, it is the key value. Without that you can't store or retrieve anything. However the mapped type doesn't even have to be comparable.

Thread: Your thoughts on this doubly-linked list

Thread Tools

Search Thread

Display

Your thoughts on this doubly-linked list

Similar Threads

help! Placement of nodes in a Linked List

circular doubly linked list help

Reverse function for linked list

airport Log program using 3D linked List : problem reading from file

singly linked list