Menu
Over the past few days I have been preparing for my very first phone interview for a software development job. In researching questions I have come up with this article.
Every thing was great until I got to this passage,
"When would you use a linked list vs. a vector? "
Now from experience and research these are two very different data structures, a linked list being a dynamic array and a vector being a 2d point in space. The only correlation I can see between the two is if you use a vector as a linked list, say myVector(my value, pointer to neighbor)
Thoughts?
344
A linked list has a more complex data structure than a vector; each of its elements consists of the data itself and then one or more pointers. A pointer is a variable that contains a memory address. In the case of a singly linked list, there will be just one pointer referencing the address of the next element.
For example, taking a bunch of random integers and inserting them in sorted order into a vector or a linked list -- the vector will always be faster, regardless of the number of items total, due to cache misses when searching for the insertion point in the linked list.
Vector may have a default size. List does not have default size. In vector, each element only requires the space for itself only. In list, each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
linkedlist is implemented as a double linked list. its performance on add and remove is better than arraylist, but worse on get and set methods. vector is similar with arraylist, but it is synchronized. arraylist is a better choice if your program is thread-safe.
Vector is another name for dynamic arrays. It is the name used for the dynamic array data structure in C++. If you have experience in Java you may know them with the name ArrayList. (Java also has an old collection class called Vector that is not used nowadays because of problems in how it was designed.)
Vectors are good for random read access and insertion and deletion in the back (takes amortized constant time), but bad for insertions and deletions in the front or any other position (linear time, as items have to be moved). Vectors are usually laid out contiguously in memory, so traversing one is efficient because the CPU memory cache gets used effectively.
Linked lists on the other hand are good for inserting and deleting items in the front or back (constant time), but not particularly good for much else: For example deleting an item at an arbitrary index in the middle of the list takes linear time because you must first find the node. On the other hand, once you have found a particular node you can delete it or insert a new item after it in constant time, something you cannot do with a vector. Linked lists are also very simple to implement, which makes them a popular data structure.
65
I know it's a bit late for this questioner but this is a very insightful video from Bjarne Stroustrup (the inventor of C++) about why you should avoid linked lists with modern hardware. https://www.youtube.com/watch?v=YQs6IC-vgmo With the fast memory allocation on computers today, it is much quicker to create a copy of the vector with the items updated.
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
