Search algorithm for a sorted double linked list

Question

As a learning excercise, I've just had an attempt at implementing my own 'merge sort' algorithm. I did this on an std::list, which apparently already had the functions sort() and merge() built in. However, I'm planning on moving this over to a linked list of my own making, so the implementation is not particuarly important.

The problem lies with the fact that a std::list doesnt have facilities for accessing random nodes, only accessing the front/back and stepping through. I was originally planning on somehow performing a simple binary search through this list, and finding my answer in a few steps.

The fact that there are already built in functions in an std::list for performing these kinds of ordering leads me to believe that there is an equally easy way to access the list in the way I want.

Anyway, thanks for your help in advance!

Answer 1

The way a linked list works is that you step through the items in the list one at a time. By definition there is no way to access a "random" element in the list. The Sort method you refer to actually creates a brand new list by going through each node one at a time and placing items at the correct location.

You'll need to store the data differently if you want to access it randomly. Perhaps an array of the elements you're storing.

Further information on linked lists: http://en.wikipedia.org/wiki/Linked_list

Answer 2

A merge sort doesn't require access to random elements, only to elements from one end of the list.