Arrays, Vectors & Linked Lists

Question

My main question is on how vectors work.

I understand that a linked-list is a list of nodes joined together. That's how I imagine it in my head. But I can't imagine what a vector looks like.

I read that vectors have random access, just like arrays. But what is random access? Does the computer not ended up eventually searching for the index internally? I say this because I can overload the [] operator to give me the i^th element in a linked-list, by running a for-loop.

Also what is an array made of? I know how arrays work but what is behind it, is it also a collection of nodes? I'm asking this just for general knowledge.

Here is a question on vectors. It looks very similar to the functions used for a linked-list.

Answer 1

An array is a location in memory and a series of serial locations following it.

Consider if I had array int[] a = [1,2,3,4,5,6,7,8,9,10];

If we looked at this array in memory it might look like this --

15  null           00000000
    null           00000000
    null           00000000
    a[10]          00001011
    a[9]           00001010
10  a[8]           00001001
    a[7]           00001000
    a[6]           00000111
    a[5]           00000110
    a[4]           00000101
5   a[3]           00000100
    a[2]           00000011
    a[1]           00000010
    a[0]           00000001
    other stuff    00011101
0   other stuff    01010101

You get random access in an array because the compiler is doing work for you to find the exact address you are looking for for you.

For instance in this case if I run the function

print(a*); //print the location in memory of a (the pointer to a)

it will output

2

Now when i ask for a[2]

print (a[2]) 

what the compiler is actually doing is this

print (&(a*+2) // print the values at the memory location 
               // that is 2 plus the pointer to a

this mean it should print out the value at memory location 4, which is

3

When we say an array has random access, it means that the time to access is constant, since to find element a[100000] and a[1] both take the same amount of time.

1.) look-up a.
2.) add the index to a. 
3.) look-up the value at a + index. 

Now a vector is just a wrapper for an array. It add special functionality and define 'behaviors' for the array.Imagine it like a struct with 3-4 pieces of data, some of those piece of data being pointers to special 'vector functions'.

Imagine a piece of data like this.

struct vect { 
    int* array; 
    int  arraysize; 
    int* functionPtr1;
    int* functionPtr2;
    int* functi....
};

Im going to avoid the gorp of how this would look in c, since Im not very good and would be sure to get something wrong, but in an object oriented language like java, our vector would look something like this

vect.array[1];
int arg2 = vect.array[2]; 
vect.functionPtr1(2); 
int vectSize = vect.arraysize; 

Pretty simple. Where it confusing is that c++ lets you define the [] operator on a object. In the vector in c++ when you do this.

vect[2]; 

It is actually just syntactic sugar for the java equivalent here :

vect.array[2]; 

But the tl;dr; version of it all is that a vector is just a object used to wrap functions around a primitive array. C++ provides special synatic sugar so that you can address the primitive array directly from the object pointer, not just from the objects array member, however the work to get the object array member is still being done, only abstracted away.

Answer 2

A vector (at least in C++) represents a contiguous block of memory holding objects of equal size. That allows it to compute the address of any given item in constant time, with something like:

address = base_address + index * item_size;

Note that most of this is under the covers (so to speak though) -- C++ (like C before it) defines indexing in terms of computing addresses of objects of some specified size, so in reality the code is likely to just look something like:

T &operator[](size_t index) { return base[index]; }

...and the compiler handles generating code to do the multiplication based on sizeof(T).

That means accessing any part of the array requires essentially the same mechanism on the part of the code. In fairness, it doesn't mean all accesses will necessarily be the same speed though.

For example, part of the data might be in the cache, other parts in main memory, and still other parts might well be in virtual memory where retrieval requires reading data from a disk drive. That might easily mean a difference in speed of a million to one (or more).

That is still, however, a contrast to a linked list, which requires linear complexity just to find the address of an arbitrary item in the list. From there, we get all the same possibilities as far as how that data might be stored (and since the data isn't contiguous, we tend to get poorer locality of reference, leading to an even greater chance that any given data will be in one of the slower forms of storage).

Answer 3

Usually a vector has three data members:

• a pointer to the start of the data
• a pointer to the end of the data (or an integer holding the size of the vector)
• an integer containing the current capacity of the vector (don't worry about this)

"the data" is an array, so ultimately a vector looks like a pointer to an array with some extra information.

An array is a sequence of adjacent objects in memory, so each one starts at an address one byte higher than the last byte of the previous object.

Does the computer not ended up eventually searching for the index internally?

No, part of the function of RAM hardware is to fetch the contents of a specified address without scanning through memory. This is what distinguishes RAM from (say) rotating drum memory.

In this context, "random access" means access to any address in at most a fixed amount of time.

With both a vector and an array, the address of the ith element can be computed by adding an offset to the address of the first element. The offset in bytes is equal to i times the size of a single element. With a linked list, the only way to get the ith element is by following the next pointer i times. So if you did implement that operator[] for a linked list, it would take longer to execute the greater the value of i, and so would not provide random access.

Answer 4

Without being specific to a language, the terms generally mean:

• An array is a fixed-length, unstructured area of contiguous memory. Locations are accessed by computing an offset from the base address.
• A vector is random-access like an array but knows its length, so it can be dynamically changed.
• A linked list is entirely dynamic and non-contiguous, so it is not random-access.

Answer 5

A vector in C++ is a class that esentially wraps an array and provides automatic resizing of it as you add new elements to it.

An array is essentially just a contiguous block of memory, where every element is placed right after the other in memory.

Random access basically means to access an element by index, i.e. to get the 5th element in the list. An array (and hence vector) provides efficient random access with constant time lookup of an element. That means that it is just as fast to access the 5th element as the 573rd.

Since vector wraps an array and stores its data internally as an array, the efficiency for element lookup is the same as that of an array (basically). And it does not need to do a lookup of an index or anything like that since it holds its data in an array.