Your thoughts on this doubly-linked list

This is a discussion on Your thoughts on this doubly-linked list within the C++ Programming forums, part of the General Programming Boards category; For our lab 1 our professor has given us an assignment to create a doubly-linked list template class. He is ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    25

    Your thoughts on this doubly-linked list

    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?

  2. #2
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    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.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by ArlexBee-871RBO View Post
    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.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    Last edited by iMalc; 06-21-2008 at 05:02 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Mar 2007
    Posts
    25
    Quote Originally Posted by tabstop View Post
    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.
    Last edited by ArlexBee-871RBO; 06-22-2008 at 04:25 AM.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Does this really have to be a linked list? This smells a lot like an array-type thing.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 09:38 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21