array
vector
depends on situation...
hmmm, i was actually taught that way too (in java). but like i said above ( i think it was this thread), this guy from EA said the STL was evil because its ADT's are based on linked lists. either way, i prefer to write my own.Originally posted by Polymorphic OOP
No, actually you're wrong here. A vector is usually implemented as an array, NOT a linked list. they "expand" by reallocating and/or reserving memory. This I am sure of.
Whats an array?!
Free the weed!! Class B to class C is not good enough!!
And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi
Serious question: What are the advantages of using a linked list? When should one use a linked list instead of an array or vector? From what little I've seen, linked lists just look like a hassle to use.
FAQ
"The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.
"If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.
linked list can save you on memory. however, you have to use sequential search. arrays and vectors can be searched with binary or random access. but at the same time, can take up more memory. it depends on what you are using it for and which you feel is the best to use in the situation.Originally posted by joshdick
Serious question: What are the advantages of using a linked list? When should one use a linked list instead of an array or vector? From what little I've seen, linked lists just look like a hassle to use.
You got it mixed up. linked lists will actually take up more memory than arrays because each node in a linked list has to have a pointer to at least one other node.Originally posted by alpha
linked list can save you on memory...
arrays and vectors ... can take up more memory
The reasons you use a linked list is because you can add and remove elements (particularly adding and removing elements in the middle of the list) without having to reallocate any memory that has values which aren't changing, while with an array, you will many times have to completely reallocate more memory and copy all of the data over, and to remove an element in an array, you have to copy all the ones after it back one space.
It's all about data access, creation, and removal -- are you going to be adding and removing a lot of something, more particularly, are you going to be adding and removing a lot of something in no predefined order. If so, then a linked list makes much more sense. An example would be a game with a bunch of enemies on the screen. You have no idea what order the player will be killing the enemies in, so you use a linked list making it more efficient to remove an element from the middle.
You can usually use arrays as stacks or queues of predetermined maximum lenght. One perfect example I can give of this is "the stack" that you should be familiar with as a C++ programmer. If not, then go back to lesson 1
Thanks. That makes much more sense.Originally posted by Polymorphic OOP
You got it mixed up. linked lists will actually take up more memory than arrays because each node in a linked list has to have a pointer to at least one other node.
Assuming the array is filled, then that's true.You got it mixed up. linked lists will actually take up more memory than arrays because each node in a linked list has to have a pointer to at least one other node.
However, if you're having a variable amount of data, an array must have enough room for extra elements, while a linked list only allocates what it needs. This usually leads to sizeof(Array) > sizeof(LinkedList).
MagosX.com
Give a man a fish and you feed him for a day.
Teach a man to fish and you feed him for a lifetime.
that's true too. i think that's what i was thinking when i posted it. assuming you only have a few nodes and a big array, then the linked list should take up less memory. but assuming the same size for linked list and array, then array should take up less space.Originally posted by Magos
Assuming the array is filled, then that's true.
However, if you're having a variable amount of data, an array must have enough room for extra elements, while a linked list only allocates what it needs. This usually leads to sizeof(Array) > sizeof(LinkedList).
I just read this article and it says you should prefer deques over vectors:
http://www.gotw.ca/publications/mill10.htm
Should i consider myself sociaal outcast upon finding this discussion entertaining reading???
yes.Originally posted by DirX
Should i consider myself sociaal outcast upon finding this discussion entertaining reading???
darn...... thats not good
