Doubly Linked List Check
I am working on converting a singly linked list to a doubly linked list. I think I'm finished but since I've never worked with these before, how can I know if everything works correctly? Thank you!
Last edited on
Hi Titanflyer,
I hope you will not be upset if I explain what seems wrong to me about your doubly linked list from a usage semantic rather than any technical implementation issue. I apologize in advance that I am not actually doing what you asked at all, but I hope this helps in any case :)
The usage semantic of your class feels to me to be that of a random access container (e.g. array, vector), rather than a bi-directional sequential container. This makes your interface somewhat at odds for getting the best performance out of your implementation.
A key benefit of a doubly linked list is speedy insertion/deletion from start/end of the container. Of course this does not mean that your other operations would never be necessary, but anyone intending to frequently call any of the member functions would have to accept the cost of iteration through the container to locate a specific item at a given index. Indeed, the standard library takes the policy of (in general) not providing operations with poor efficiency on containers for which it would be inappropriate (well, to a certain extent anyway).
Taking a look at the C++ standard library list interface shows a relatively straightforward container, supporting push_back, push_front, pop_back, pop_front, erase, insert and interation. The iteration accomplished using an iterator (rather than an index) provides an efficient way to walk the list (and insert efficiently based on an iterator, into the list), and yet also hides implementation details.
These basic operations can then be combined with the standard library algorithms to achieve the sort of operations you implement yourself: but the performance implications are clear, as they are defined by the choice of algorithm.
The sort of operations you provide would benefit from an approach using iterators to manipulate elements: remove( Iterator it ), insert( Iterator it, ListItemType)
I hope you don't feel this advice is unnecessarily preachy, it's difficult (for me at least!) to explain things like this on a forum rather than in person without going on a fair bit! :)
My apologies if it doesn't help one jot with the problem you are currently working on!
Best wishes,
CC
I hope you will not be upset if I explain what seems wrong to me about your doubly linked list from a usage semantic rather than any technical implementation issue. I apologize in advance that I am not actually doing what you asked at all, but I hope this helps in any case :)
The usage semantic of your class feels to me to be that of a random access container (e.g. array, vector), rather than a bi-directional sequential container. This makes your interface somewhat at odds for getting the best performance out of your implementation.
A key benefit of a doubly linked list is speedy insertion/deletion from start/end of the container. Of course this does not mean that your other operations would never be necessary, but anyone intending to frequently call any of the member functions would have to accept the cost of iteration through the container to locate a specific item at a given index. Indeed, the standard library takes the policy of (in general) not providing operations with poor efficiency on containers for which it would be inappropriate (well, to a certain extent anyway).
Taking a look at the C++ standard library list interface shows a relatively straightforward container, supporting push_back, push_front, pop_back, pop_front, erase, insert and interation. The iteration accomplished using an iterator (rather than an index) provides an efficient way to walk the list (and insert efficiently based on an iterator, into the list), and yet also hides implementation details.
These basic operations can then be combined with the standard library algorithms to achieve the sort of operations you implement yourself: but the performance implications are clear, as they are defined by the choice of algorithm.
The sort of operations you provide would benefit from an approach using iterators to manipulate elements: remove( Iterator it ), insert( Iterator it, ListItemType)
I hope you don't feel this advice is unnecessarily preachy, it's difficult (for me at least!) to explain things like this on a forum rather than in person without going on a fair bit! :)
My apologies if it doesn't help one jot with the problem you are currently working on!
Best wishes,
CC
Topic archived. No new replies allowed.