0

This might be a quite stupid question but, knowing the poor efficiency of searching for an element inside a list (singly-linked or doubly-linked), why not using a vector or dynamic array to store the elements of the list in order, therefore making it easier to access elements ?

PeePeePooPoo
  • 27
  • 7
  • the point of a linked list is to allow O(n) insertion and deletion which can't be achieved with a vector. That said, you should almost never use a linked list nowadays because vectors are much more compact and far more better for caches which usually result in better performance even after copying the elements to delete/insert – phuclv Jan 08 '21 at 07:43
  • see [Bjarne Stroustrup says we must avoid linked lists](https://stackoverflow.com/q/34170566/995714), [Number crunching: Why you should never, ever, EVER use linked-list in your code again](https://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/) – phuclv Jan 08 '21 at 07:43
  • Well I guess not, but let's say I need to build a map like the one in Hunt The Wumpus : each room is connected to other 3 and the rooms don't change after they are generated. I just cannot think of a simpler representation in code for that rather than making a struct Room that has pointers to other 3 rooms, somehow link the rooms, and then store them in a vector. – PeePeePooPoo Jan 08 '21 at 07:55

1 Answers1

1

Linked lists used to be more important because they are stored non-contiguously which is better for memory management. Linked lists and vectors / arrays both have a search time complexity of O(N). It's only faster to access array elements if you know the index in advance. Linked lists are for niche cases where you are frequently inserting elements into the beginning of the array. Linked lists let you do this in O(1) time as opposed to arrays O(n) because the other elements need to be shifted.

Mick
  • 796
  • 4
  • 8