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

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

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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, 2017 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, 2017 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, 2017 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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