PDA

View Full Version : c++ doubly linked list challenge



potaters
July 18th, 2011, 10:34 AM
Hey guys, this is my first post on ubuntu forums. I'm really glad to be here!

Anyways, here's a c++ challenge I read somewhere a long time ago:

Write a doubly linked list class with all the normal functions:



void AddNodeToBeginning(NodeType NodeValue); //adds the node to the beginning
void AddNodeToEnd(NodeType NodeValue); // adds node to end of list
void PrintList(); // prints the linked list values
int searchList(NodeType NodeValue); //searches the list and returns found index or -1


But here's the twist, You need to add a function to reverse the list, and it has to be of order o(1) (Meaning the function needs to have a constatnt number of statements, you can't loop over the list and do something, cause then it would depend on the number of elements on the list).



void reverseList();


Yeah that's it for now, enjoy!
cheers.

dwhitney67
July 18th, 2011, 12:51 PM
Nice try, but this seems like a twist on asking for assistance in doing one's homework.

NovaAesa
July 18th, 2011, 01:46 PM
I agree, this smells of homework. Btw, reversing the list should be extremely easy to do in O(1) considering that it's doubly linked...

Tony Flury
July 18th, 2011, 02:34 PM
NovaAesa : I agree - if anything the list reversal is probably the easiest bit, and yes - it does smell of homework.

potaters
July 18th, 2011, 03:07 PM
It's not homework. And my approach of the solution was adding a boolean variable isReversed, which will be set to false for all class instances, and then for the reverseList() function , we do:



isReversed = !isReversed;
node *temp = first;
first = last;
last = temp
//reverse the first and last pointers


And then we make a check for all the other functions, say for print , if isReversed is true, we traverse the list with the Back pointer, rather than front.

cheers.

schauerlich
July 18th, 2011, 06:41 PM
That's what I'd do.

EDIT: One way to avoid a bunch of


if (isReversed) {
foo = node->prev;
}
else {
foo = node->next;
}
...

is to have ListNode have a two element array of pointers instead of a separate prev and next, and use (int)isReversed to decide which one to use. Then you can do something like


node.neighbors[!isReversed]

Assuming the convention that neighbors[0] is the "left" neighbor, and neighbor[1] is the "right", then that line above will always yield the "next" depending on if you're moving left-to-right or right-to-left.

potaters
July 19th, 2011, 04:09 PM
Elegant solution, schauerlich, deffinetely "cleaner" than mine.

I'm just curious though, how can we reverse a normal linked list? Can it be done in O(1) efficiency? (I don't think so!)

The only way I can think of is traversing the whole list and changing all the 'next' pointers to the previous node.

dwhitney67
July 19th, 2011, 06:16 PM
Elegant solution, schauerlich, deffinetely "cleaner" than mine.

I'm just curious though, how can we reverse a normal linked list? Can it be done in O(1) efficiency? (I don't think so!)

The only way I can think of is traversing the whole list and changing all the 'next' pointers to the previous node.

One should be able to insert new elements into a linked list either at the beginning, the end, or somewhere in the middle.

Thus to reverse an existing list, create a new list using the contents of the original list. This will require only one traversal of the original list, thus O(1) efficiency. Refer to the documentation on the STL list (http://www.cplusplus.com/reference/stl/list/) for more insight/ideas (hint: push_back() and push_front() functions).

johnl
July 19th, 2011, 06:22 PM
One should be able to insert new elements into a linked list either at the beginning, the end, or somewhere in the middle.

Thus to reverse an existing list, create a new list using the contents of the original list. This will require only one traversal of the original list, thus O(1) efficiency. Refer to the documentation on the STL list (http://www.cplusplus.com/reference/stl/list/) for more insight/ideas (hint: push_back() and push_front() functions).

I think you're mistaken; traversing the list means that the time to run is dependent on the number of items in the list -- i.e., O(n)?

dwhitney67
July 19th, 2011, 07:42 PM
I think you're mistaken; traversing the list means that the time to run is dependent on the number of items in the list -- i.e., O(n)?

Dooh! You're right.