vectors and their relation to linked lists

This is a discussion on vectors and their relation to linked lists within the C++ Programming forums, part of the General Programming Boards category; Are vectors (the dynamic array, not the mathematical kind ) similar to linked lists, in the aspect that they hold ...

  1. #1
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949

    vectors and their relation to linked lists

    Are vectors (the dynamic array, not the mathematical kind ) similar to linked lists, in the aspect that they hold the next node in the list, and that they have an internal node class, or how else do they work? Anyway, thanks for any explanation .
    Do not make direct eye contact with me.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    vector is not node based. It is array based. a vector is a dynamic 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

  3. #3
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088

    Re: vectors and their relation to linked lists

    Originally posted by Lurker
    Are vectors similar to linked lists, in the aspect that they hold the next node in the list, and that they have an internal node class
    No, they are not similar to linked lists in that aspect. I assume you are referring to the vector class in the STL, which is basically an array (as Stoned_Coder said). If you already know how an array works, then the rest of the answer won't matter much.
    Originally posted by Lurker
    or how else do they work?
    An array does not have an internal node, instead, it has space allocated for as many objects (or maybe more) as it currently contains. This memory is in one contiguous block (at least logically). Therefore, there is no need to have a next pointer, since you know the size of each "node" and you can just move that distance from the current object to find the next one.

    That is why arrays (and consequently vectors) provide fast access to any random index. If you have an array of 243 objects which are 16 bytes each, and you want to access the one at index 156, then simply go to the memory location 2496 bytes (156*16) after the first object in the array. With a list, the objects could be anywhere in memory, so you have to traverse each node looking at the next pointer to see where the next node is. You'd have to do that 156 times.

    One negative for arrays (and of course vectors) compared to lists is that it is ineffiicent to insert into the middle. If you insert an object into spot 156 in the middle of your array of 243 objects, then you have to copy the data for each object after spot 156 and move it over 16 bytes in memory. This is because arrays must always have contiguous memory, so object 157 must be immediately after 156 in memory. In a list, you just put the object wherever you want and then set the next pointer for object 155 to it, then put the next pointer for the new object to the one that used to be at spot 156 - much more efficient.

    Those are just a couple examples of how the differences in the way the two container types work affect their use. Of course there are many other container types that have other positives and negatives.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21