Difference between dynamic arrays vs linked list?

Question

What is the difference between dynamic arrays in c# and c++ vs a linked list. I wouldn't mind knowing how dynamic arrays are created. I know how linked lists work, but I have no clue how dynamic arrays are made. Are they made with hashes?

Answer 1

The largest difference is perhaps, access time. Dynamic arrays are really contiguous memory slots allocated dynamically to a variable. With a reference/pointer to the first memory address in the allocated contiguous memory blocks, you have direct access to each slot - Array indexes are "added" to the address and the values stored at the resulting address is returned, making it constant-time access. Since you know how linked-lists work, you probably know that that nodes within a linked list is accessed sequentially. To get to a node, you need to run through every node prior to it within the list.

Then why use linked list? Well, deletion/insertion can be performed faster. Since dynamic array blocks are contiguous, it would take more work to insert / remove an element from the middle of the array, compared to a linked list. Linked lists are also designed to grow in size more naturally than dynamic arrays.

Answer 2

Cameron Hansen

Like what has been pointed out, you specify the index of the certain block you want to access. Since the blocks are contiguous and the blocks are of the same size (homogeneous), the address can be incremented based on the index directly. The value stored by the resulting address is then returned. E.g. assuming int array with each block 4-bytes wide -

Address of first block: 0x6000127c0

The second block would be 0x6000127c4

Let's say you access index 5, we can directly know the address of the block at index 5, i.e.

First block address + (5*4) bytes, which is 0x6000127d4.

By the same logic, you can access index 100, 1000 with the same access time.

Answer 3

Oh! Now I understand! That makes sense. I forgot you can increment the pointer address. Thank you!

Answer 4

That's great information! Dynamic arrays are faster for access but slower for inserting/deleting in the middle 😎. I learned something new today, Thank you!

Answer 5

When you say that the variable has a pointer to the first block of memory,would you not have to loop through each item like a linked list to access a certain block element? I think I misunderstood that part.

Answer 6

Here is an article with a C implementation I found in Abolhashan Ashori's link : https://brilliant.org/wiki/dynamic-arrays/ . Thanks everybody.