CODEWITHSUNDEEP
c++arraysperformancelinked-list
Ahmad Anis
Ahmad Anis

Reputation: 2704

Looping vs Indexing

Let's say I have a Linked List of 100 elements.

struct node{
int data;
node*next;
}

and I want to access some element at n position, so I have to do a loop. If I don't loop over that Linked List and instead store its data element in an array while taking input/reading data and when I want to output any element at n pos, I can just call arr[n] so is it more efficient approach or should I use the loop.

Upvotes: 1

Views: 204

Answers (2)

Mike Robinson
Mike Robinson

Reputation: 8945

The beauty of the C++ language is that it provides a wide selection of "container classes" which you can "simply use." So you really don't need to bother with, say, rolling your own linked-list. ("Do not do a thing already done ...")

Furthermore, many of these container classes provide "[array index]" capability so that you can reference the contents as an ordered collection, as though it were a traditional "array," even though it actually isn't. They may also provide other options such as retrieving an element by some kind of key.

Simply browse through the set of container classes that are available in your particular C++ implementation and grab the best one for your needs, "right off the shelf." No implementation required. You simply know that they do work, and that you really don't have to care how they work.

Upvotes: 2

Conzel
Conzel

Reputation: 26

If you often have to access elements at certain positions, arrays will generally be faster, yes. If you just need to do it once, you can stick with the node structure you have and just loop over it. For looking up an element at a certain position, you can do it on an array in O(1), and in a linked list in O(n).

Linked lists offer other advantages, such as constant-time insertions, which you do not have with arrays. Unless you specify your problem more exactly, we cannot tell you which data structure would be preferrable.

Edit: Refer to Array versus linked-list for more information about list vs array use cases.

Upvotes: 1

Related Questions