This post is similar but does pose different questions than an earlier post, please read on. Especially the second question. Thanks. Yea! I finally understand how linked lists work! Now for the problem. I can make and search a linked list, no prob. I can even pre-sort stuff before putting it into the list and I have an idea on how to perform a binary search on the list. Does anyone have any other ideas on how to perform a very fast search on a linked list? Each node in my list is an actual unit on the battlefield, so if I sort my list what variable(s) inherent to strategy games would be ideal to use? I love the forums. Create. Edited by - RolandofGilead on August 5, 2001 6:36:06 PM

I was looking at other posts and someone posted the
following URL.
http://www.wxWindows.org
Has anybody used it?

Create.

Treating the game map as the XZ plane, it makes sense to sort units by their Z coordinates, so they can be drawn back-to-front if you''re making a 2d game, or front-to-back if you''re doing a 3D one so as to avoid too much overdraw.

An insertion sort would probably make sense in that situation.

The words "sort" and "linked list" should generally not appear in the same sentence. Unless you''re doing something tricky, it''s very expensive to search a linked list for any value, regardless of whether it''s sorted or not.

If you''re STL-savvy, it sounds like you should be using a map. If not, you might want to look into hash tables (yes, I know about the non-standard hash_map, but I''ve never used it so I can''t speak to it).

If you''re really bent on using a linked list look into skip lists. They provide insert and search operations of order O(lgn). The problem with them is the added overhead they require for storing so many damn links. You should really be using the STL map though, which is implemented with red-black trees--a specific implementation of 2-3-4 trees. Red-black trees are a balanced (mostly) BSTs that give all of the benefits of skip lists without nearly as much overhead.

.-If you have understood what binary search, you know that it needs random access. have another look at it.

.-Searching lists is not good. You should have a look ate the STL´s list search() method, it is specially designed for lists.

.-If a list becomes big, swicht to a tree-like data structure.

.-My last advice is to have a look to STL. It is really powerful.

What the hells!