31

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?

Wheat Wizard
  • 3,982
  • 14
  • 34
Ryan
  • 342
  • 1
  • 4
  • 5

5 Answers5

61

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.

Joni
  • 108,737
  • 14
  • 143
  • 193
  • Linked lists are good for inserting a new record or deleting a new record in n time. Traverse to N, update the links, done. A vector on the other hand does not allow for easy inserting or deleting of a new record in the middle. – StarPilot Sep 26 '13 at 23:16
  • 1
    A vector allows insertions and deletions in the middle in O(n) time, just like a linked list. The algorithm moves the elements at and after the position of insertion/deletion, which makes it O(n). – Joni Sep 26 '13 at 23:18
  • You don't have to move the elements in a linked list and there is no additional memory space needed. Inserting a new item into a linked list only requires space for the 1 item. In the linked lisy, You only update the links. Vectors have to move the data after the insert point and if they go beyond their internal cache while doing that, they'll have to allocate new space for the larger resulting vector. – StarPilot Sep 26 '13 at 23:22
  • 15
    Linked list are very good at insertion and deletion in the middle. It's O(1) time to insert in the middle of a linked list. Also, linked list guarantee that the address of data doesn't change when other data is inserted or removed. – rabensky Sep 26 '13 at 23:23
  • @StarPilot, are we seriously discussing such basic matters? If you need more space in a vector you typically resize it to twice as big (or some other suitable constant times the size of the array), which means that the time needed for resizing is amortized by how cheap other operations are, so inserting in the middle and end stay as O(n) and O(1). – Joni Sep 26 '13 at 23:28
  • 6
    @cluracan, inserting or deleting an item in the middle of a linked list requires first iterating the list to find the point of insertion or deletion. It is this iteration that makes the algorithm O(n); if you have already found the item you are inserting/deleting then of course it is O(1). – Joni Sep 26 '13 at 23:31
  • 1
    @Joni - not necessarily. I have written many algorithms where you keep references to the links while building it - and then I had to insert before / after these references. Doing this with vectors is O(n), but doing this with linked lists isn't. You can say that "finding element no. `n` takes O(n) time", but the insertion itself takes O(1). – rabensky Sep 26 '13 at 23:46
  • Finding where to insert an element is part of the insertion algorithm. If you add links to the middle of the list you no longer have a simple linked list, you have a different data structure. When you start extending the basic idea of a linked list by adding links you easily invent [skip lists](http://en.wikipedia.org/wiki/Skip_list) with O(log n) for insertions and deletions for sorted data. – Joni Sep 26 '13 at 23:51
  • 2
    @joni, you are wrong. Remembering iterators of a list doesn't make it "something else that isn't a list". It's still a list I just have a variable that holds an iterator. Finding element no. n takes O(n) time in linked list, but inserting takes O(1). Inserting doesn't have to have "finding" before it, because you can choose where to insert by other methods (like remembering were you want from before). Anyway - whatever you call it, it is something you can do with linked lists but can't with vectors. – rabensky Sep 27 '13 at 00:20
  • @cluracan, it seems we disagree on definitions. When I write about insertion (and deletion) algorithms, I mean an insert-at-index algorithm, and you must account for the time required to find the node at the index. If you have already found the node by other means of course it's a different story, and no, of course you can't do anything similar with a vector... – Joni Sep 27 '13 at 00:34
  • 4
    @joni so you have to put that in the "advantages of linked list over vectors", no? As it is an advantage of linked list over vectors... – rabensky Sep 27 '13 at 00:52
  • 1
    @StarPilot you might be interested in this: http://www.youtube.com/watch?v=YQs6IC-vgmo – harold Sep 27 '13 at 08:30
  • 1
    @joni Thank you! I had not realized vector was an actual data structure in java or other languages, I was used to just the plain '2d point in space'. – Ryan Sep 27 '13 at 17:44
14

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.

Jonathan Roberts
  • 416
  • 4
  • 7
  • 10
    Hi Jonathan, when referencing a link in the answer, please try to include a summary of what a user might find by following the link. Remember that links can break. Future proof your answer. [answer] – Dan Beaulieu Oct 30 '15 at 14:47
  • 1
    I really don't think this video is a fair comparison between the list and vector types at all. The fallacy is by comparing the efficiency of the two when removing a single element at a randomly generated *index*. A much more interesting comparison would be to compare the efficiency of removing randomly selected *members*. I want to know what percentage of members need to be removed from the list for it to outperform vector. In other words, populate a list and vector with m random integers in the range [0, n). Then remove all 0's. For what values of (m, n) is list more efficient? – Jeff G Apr 19 '19 at 19:07
4

I don't like the number one answer here so I figured I'd share some actual research into this conducted by Herb Sutter from Microsoft. The results of the test was with up to 100k items in a container, but also claimed that it would continue to out perform a linked list at even half a million entities. Unless you plan on your container having millions of entities, your default container for a dynamic container should be the vector. I summarized more or less what he says, but will also link the reference at the bottom:

"[Even if] you preallocate the nodes within a linked list, that gives you half the performance back, but it's still worse [than a vector]. Why? First of all it's more space -- The per element overhead (is part of the reason) -- the forward and back pointers involved within a linked list -- but also (and more importantly) the access order. The linked list has to traverse to find an insertion point, doing all this pointer chasing, which is the same thing the vector was doing, but what actually is occurring is that prefetchers are that fast. Performing linear traversals with data that is mapped efficiently within memory (allocating and using say, a vector of pointers that is defined and laid out), it will outperform linked lists in nearly every scenario."

https://youtu.be/TJHgp1ugKGM?t=2948

simon
  • 854
  • 1
  • 9
  • 23
  • why vector has to do a linear search here to access the element. It just can jump to the element in constant time as it laid out continuously in memory. – Vencat Apr 24 '20 at 03:38
1

Use vector unless "data size is big" or "strong safety guarantee is essential".

data size is big :- vector inserting in middle take linear time(because of the need to shuffle things around),but other are constant time operation (like traversing to nth node).So there no much overhead if data size is small.

As per "C++ coding standards Book by Andrei Alexandrescu and Herb Sutter"

"Using a vector for small lists is almost always superior to using list. Even though insertion in the middle of the sequence is a linear-time operation for vector and a constant-time operation for list, vector usually outperforms list when containers are relatively small because of its better constant factor, and list's Big-Oh advantage doesn't kick in until data sizes get larger."

strong safety guarantee List provide strong safety guaranty. http://www.cplusplus.com/reference/list/list/insert/

Rahul_cs12
  • 974
  • 1
  • 13
  • 22
1

As a correction on the Big O time of insertion and deletion within a linked list, if you have a pointer that holds the position of the current element, and methods used to move it around the list, (like .moveToStart(), .moveToEnd(), .next() etc), you can remove and insert in constant time.

Laurel
  • 5,965
  • 14
  • 31
  • 57
blackbox66
  • 11
  • 1