linked list question
BlitzMax Forums/BlitzMax Beginners Area/linked list question
| ||
| If i have 5 Objects in a linked list, how could i get Object Nr. 4 without doing "for..eachin" loops? Could the containting value you get via "Listfindlink:Tlist" help? |
| ||
| .ValueAtIndex However, be aware that function is just doing a eachin itself, so there's no speed benefit - just convenience. |
| ||
One option is to convert the list to an array -- not for speed critical stuff, though, so probably no use here!' A generic Object array to hold a converted list of objects... Local RocketArray:Object[] ' Example type... Type Rocket Field x End Type ' List for Rockets... RocketList:TList = New TList ' Create some rockets and add to list... For a = 0 To 4 r:Rocket = New Rocket r.x = a ListAddLast RocketList, r Next ' Copy list into RocketArray... RocketArray = ListToArray (RocketList) ' Show result... Print "" Print "Fourth item in list..." Print "" ' 3 is fourth item: 0, 1, 2, [3], 4 Print Rocket (RocketArray[3]).x |
| ||
| Um ... I guess you want the flexibility of a linked list so that you can add and delete links at any position. ... otherwise if you didn't, you could just keep an array of pointers to the link's data? I dunno, ignore me ;-) |
| ||
| James, wouldn't this be slower? |
| ||
| DMOC, that's what I said! ^^^ (Though it does what was asked for, in terms of getting the xth item in the list!) |
| ||
| Thank you all for reply and for the code example. Realy nice language:-) |
| ||
| One option is to convert the list to an array -- not for speed critical stuff, though, so probably no use here! If you had to do several ValueAtIndex-es, the array way could well be faster. |
| ||
| Sorry James. Note to self: get eyes tested! |
| ||
| Could you not just give each element in the list an index field. and then traverse through them starting from the first link until you find the index of value your looking for. like pseudo code ish..
seach(6,mylist)
function search(index:int,list)
if list.id<>index
search(index:+1,list)
end if
end function
Im not doing it all in the above code , I mean im not checking for the next list item pointer or anything but you should be able to get the idea. its called a traversal and it uses recurtion so im not sure if max can do it, but its worth a shot. hope it helps if not oh well. |
| ||
| and then traverse through them starting from the first link until you find the index of value your looking for. No. |
| ||
| Just occurred to me, obvious really - IIRC in bb3d I often used an "index array" to complement a list and used this as the "quick-reference" for the n'th element by storing the object/element address. I think my actual usage was a fixed list but indexed differently using several arrays. Usefulness depends on how dynamic your list is, ie, is it fixed length, can it grow but not shrink, etc, but this may be a good compromise for what you want. |
| ||
| No. What he wants is a Hashmap, so he should just use that instead. |
| ||
| Hash/key not needed so simplest solution, if it fits his specific requirement, is an array of object ptrs. |
| ||
Flameduck is correct, hash/key is the best solution. Something like:
object = hash.GetFromHash("character_bobsmith_object")
object.killcharacter()
hash.setHash("character_bobsmith_object",object)
If you do it with an array instead, you have to have some way of keeping all the index to each value. Lets say you are keeping track of hundreds of characters in an RPG. It is going to get pretty difficult to keep track of each index. |
| ||
| Flameduck my method is a tried and tested one. so your NO reply was indeed wrong. unless of course you want to argue with my C++ prof. Either way I havent heared of the hashmap methed so I'll google it once worldofwarcraft has finished downloading. you have peeked my intreset now. |
| ||
| I don't believe Max has a built in hashmap does it? If not, it's really a moot point. |
| ||
| Flameduck my method is a tried and tested one. so your NO reply was indeed wrong. unless of course you want to argue with my C++ prof. Very well. Your method might be 'tried and tested', but it's still not applicable to this situation.What your professors method does is a waste of resources - your type already has a unique ID - namely its address or handle, so createing any additional ID's are redundant. Additionally there is no way in your version to ensure that ID's are sequential unless you sort the list every time you add a new element which makes it an even worse solution. The bottomline is that, contrary to what LISP programers might believe, a list is not a good solution to any given problem. A list is a good solution to a problem that requires sequential access. If you need random access and you're using lists, you're using a wrong collector. The goal of any algorythm is to get as close to a constant time complexity as possible. Lists have linear time complexity for random access. Arrays and Hashmaps constant, thus they would be better solutions. I don't believe Max has a built in hashmap does it? If not, it's really a moot point. Why? |
| ||
| Mikkel you lost me with the time complexity thing, must be reading more books? ;-) Just teasing you. I wonder if someone can explain what a hash table is, how it works and what you might use it for? |
| ||
| Mikkel you lost me with the time complexity thing, must be reading more books? Time complexity is a measure of how much time (relative) an algorythm takes as compared to the size of a problem.An algorythm with a constant time complexity will take the same ammount of time, regardless how many elements it has to deal with. An example would be accessing an Array by index, or a Hashmap by key. An algorythm with a linear time complexity will take a linearly increasing ammount of time as the number of elements increase. Thus if it takes 1 second with 4 elements, it'll take 2 seconds with 8 and 3 seconds with 12, and so on. An example is traversing lists and certain (slow) sorting algorithms. An algorythm with a logarithmic time complexity will also take more ammounts of time for more elements, but will do so in a logarithmic fashion. An example is the classic "Binary Search" or number guessing game, where your next guess is always exactly half of your previous guess. This technique is used for traversing binary trees, and thus binary trees are faster to access than lists (but are slower for insert/update). The last often used time complexity is exponential time complexity where an algorithm takes exponentially longer for more elements. Thus if 1 element takes 1 second, 2 elements will take 2 seconds and 3 elements 4 seconds and so on. Obviously large problems of exponential time complexity (like the traveling salesmans problem) cannot be solved by throwing all the worlds processing power at it. I wonder if someone can explain what a hash table is, how it works and what you might use it for? Sure. A hashtable is clever mathematics using prime numbers. What happens is you make a 'hash' of your object, and use that much in the same way you would index an array. The catch? Your hashtable needs to be at least twice as big as the ammount of data you plan on using, and on top of that, has to have a length of a prime number. This will help you avoid hash collisions (you can do it without all the prime number and double space if you want, but then you won't get a constant time complexity).Now the trick here is that two different objects with the same data, will still have the same Hash, so the HashTable will be unable to tell the difference between two different concrete objects with the same data (unlike an array or list for instance). This is useful in a lot of situations, for example if you want to have a cache for intermediate storage of objects, or if you want to use a Factory pattern to create objects for you. Say you're working in a dynamic environment where you don't want to have hundreds of duplicate objects floating around. You want a so-called Factory class to handle creation, and make sure that for every specific object, only one ever exsists at any given time. So you tell the Factory to create an object with certain parameters. The Factory does a look-up in the HashTable to see if such an object already exists, and if it does, it returns the handle of the exsisting object. If not, it creates a new object, puts it in the HashTable, and returns that object. Thus all your creation problems are solved elegantly. |
| ||
| Hmm, I understand the stuff about the time complexity but I still don't understand what a hash table is or what it looks like or what a hash is. You're talking about how to use it but a much simpler explanation is needed. |
| ||
| http://www.google.com/search?q=hashmap http://www.google.com/search?q=hashtable |
| ||
| Basically one implementation is that you take an object, make a number out of it (By say adding some value of the fields for instance) and use that number as an index into an array. Now if you do it right, you get no or little collisions and lookup is constant time - ( Is that O(1)?, I'm not up on that stuff) Aaron |
| ||
ValueAtIndex doesn't seem to work.Parms:TList = New TList Parms.AddLast(23) Parms.AddLast(32) Print Parms.ValueAtIndex(0) Yields an index out of range error! Please help. -Jim |
| ||
| AFAIK these things works with Objects only. Types and strings are objects, numbers are not. So something like this works
Parms:TList = New TList
Parms.AddLast("23")
Parms.AddLast("32")
Print String(Parms.ValueAtIndex(0))
|
| ||
| Thanks, that did it. This brings up a question though, why can't I convert an object to an int? I have to convert the object to a string, then I can convert the string to an int. |
   |