1

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.

Ahmad Anis
  • 2,322
  • 4
  • 25
  • 54
  • For the efficiency estimation (time) you need to count the number of steps the program should perform for an operation. For `arr[n]` it will probably be 1, for a loop, it will be `n` steps. Please refer to big O notation. – vahancho Mar 02 '20 at 16:18
  • 1
    Why not use a [std::vector](https://en.cppreference.com/w/cpp/container/vector) instead? Or, if you *insist* on a linked list (but why?), then at least use a [std::list](https://en.cppreference.com/w/cpp/container/list), don't roll your own. – Jesper Juhl Mar 02 '20 at 16:20
  • 1
    https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html – Jarod42 Mar 02 '20 at 16:25

2 Answers2

2

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.

Mike Robinson
  • 8,490
  • 5
  • 28
  • 41
1

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.

Conzel
  • 26
  • 3
  • 2
    Constant time arbitrary position insertion into a linked list is a trap because it usually involves first finding an iterator to the position where you want to insert, which isn't constant time. – François Andrieux Mar 02 '20 at 16:21
  • 1
    I disagree with every point the answer in the linked question makes. I don't understand how it can be so upvoted. – François Andrieux Mar 02 '20 at 16:23
  • 2
    To expand on the first comment by @FrançoisAndrieux ; not only is finding the insertion point in a linked list not constant time, it is usually *really expensive* since it involves chasing pointers all over memory which usually results in a bunch of cache misses. Copying a linear block of memory in a vector when inserting usually ends up much faster over all. – Jesper Juhl Mar 02 '20 at 16:26
  • The most important property of (and reason to use) a `list` is IMHO that iterators and references are never invalidated, as long as the element is in the list. If you need that, there are no alternatives to a list. – alain Mar 02 '20 at 16:48