Vectors vs linked lists

KidTsunami
Unregistered
 
Post: #1
I'm currently using vectors to store the tiles for my levels. I was wondering if using vectors is too slow and that I should look into implementing a linked list. I've used linked lists multiple times in the 5 years of programming that I've taken throughout high school and college so implementing them wouldn't be too much of a pain, but I'd like to avoid it.
Quote this message in a reply
Member
Posts: 156
Joined: 2002.10
Post: #2
If you are planning to access all of the tiles in sequence, then yes, use a linked list. Otherwise, for random access a vector will be much more convenient and probably faster too. What language are you using?

- Iain
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #3
std::vector?

You realize that std::list is a linked list, right, so you wouldn't have to roll your own?

std::vector is faster than std::list except in the case where you want to insert or remove from the middle or start of the list frequently.

Even if you do insert or remove from the middle or start of the list frequently, std::vector may still be faster than std::list if you do a lot of "random access".
Quote this message in a reply
Moderator
Posts: 916
Joined: 2002.10
Post: #4
vector:
pros:
O(1) access to any particurlar element
contiguous in memory
cons:
slow insertion (maybe)
slow deletion (maybe)
wastes memory (has elements that may not be in use or never used)

list:
pros:
Uses only the memory you need
variable size
O(1) insert (assuming you know where you are inserting)
O(1) delete (assuming you know where you are deleting)
best for queues and stacks
cons:
non contiguous in memory (not necessarily bad)
O(N) access time (for random element)
wastes memory (needs extra memory for pointers)
Quote this message in a reply
Member
Posts: 177
Joined: 2002.08
Post: #5
Quote:Originally posted by skyhawk

O(1) insert (assuming you know where you are inserting)
O(1) delete (assuming you know where you are deleting)


In the vast majority of places I've seen lists used, it was feasible to simply declare order meaningless and reduce the insert case to O(1) at all times.

Also, deletion is only O(1) for a doubly-linked list.
Quote this message in a reply
lpetrich
Unregistered
 
Post: #6
First, bear in mind that these tiles will likely be loaded when each level is loaded -- or even when a game starts. This means that there will likely be no changes in the tile-storage data structure when in a level.

If all your tiles are some fixed size, then you can put all their data into a single vector. From that size, you can find the multiplier from tile index to index in the data vector.

But if they vary in size, then you may need another vector that contains, for each tile

Width
Height
Offset

or

Width
Height
Pointer to Individually-Allocated Data

There is also the problem of how the tiles are referred to from the rest of your code and data. Are they referred to by indiex? By collection number and index? By name?

Collection number can be taken care of by creating an array of tile vectors, but named tiles are more difficult. A simple way of handling named tiles is to search for a tile by scanning through the list and checking each tile name for a match.

However, that's needlessly slow; there are some alternatives. One is to set up a binary search by sorting the tiles by name. This can be done with a minimum of data shuffling by doing an index sort -- sorting only indices of the data objects. Another is to construct a hash table. One constructs an index from a name, and then uses that index to look up an entry in a hash table. This table will have been set up by scanning through the list of tiles, calculating hash indices from the tiles' names, and then placing the tile indices at the hash-table locations indicated by the hash indices. Sometimes, more than one name may share the same hash index. There are a number of ways to handle such "hash collisions":

If a tile index in the hash table turns out to be incorrect, then search through the tiles for a match and update the hash table with one's success.

Construct a linked list of same-hash-index tiles; one can do this by adding a "Next" field to the tile data, with the final entry having index -1 or something like that.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  CoreData, Vectors, and relationships viscount dirigible 4 3,021 Nov 14, 2008 04:41 AM
Last Post: viscount dirigible
  Finding Rotational Vectors and Angles Nick 9 4,662 Mar 25, 2005 12:14 AM
Last Post: tigakub
  ObjC/c code error with lists ededed 5 3,336 Jan 31, 2003 06:56 AM
Last Post: w_reade