0
$\begingroup$

I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a linked list as an underlying DS. I'm inclined toward toward linked list because of the easiness of operations. Is it a good decision? What other things I need to consider?

Thanks

$\endgroup$
  • $\begingroup$ Why not use a library collection? $\endgroup$ – Thumbnail Jul 21 '17 at 14:30
  • 1
    $\begingroup$ Implement in which context? Programming is offtopic here. Also, please define "good" -- it depends. $\endgroup$ – Raphael Sep 19 '17 at 15:24
1
$\begingroup$

Well, if you're looking for easiness of operations, I would recommend a vector. Vectors support a wide array of operations, providing a large number of top-level methods, and iterators namely std::iterator, reverse iterator, and a lot more. With these top-level functions and iterators however, comes the caveat of not being able to modify these to suit your needs. Consider all of this when making the choice.

$\endgroup$
  • 4
    $\begingroup$ As I understand it, std::iterator is specific to C++ but the question doesn't mention any language. Indeed, we're not looking for language-specific answers here, since we're a site about computer science, not programming. Is the whole of your answer C++-specific? $\endgroup$ – David Richerby Jun 21 '17 at 15:25
  • $\begingroup$ Oh, I'm sorry, I saw the word vector and assumed OP was working with C++ $\endgroup$ – Pratik K. Jun 21 '17 at 22:09
  • $\begingroup$ Well, now you mention that, maybe the question itself is C++-specific and off-topic. I don't know C++ so "vector" didn't have that association for me. $\endgroup$ – David Richerby Jun 21 '17 at 22:10
1
$\begingroup$

Since deleting or inserting in the middle of a vector is a linear time operation, a linked list is the better choice. This assumes of course that you have reasonably large lists (i.e. they don't fit in cache) and that you frequently insert or delete items in the middle, compared to just iterating or changing the end of the list. If you have small lists or change them only infrequently, the smaller constants in the asymptotic runtime for operations on a vector could beat asymptotic improvements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.