1

I am learning about arrays, single linked list and double linked list now a days and this question came that

" What is the best option between these three data structures when it comes to fast searching, less memory, easily insertion and updating of things "

As far I know array cannot be the answer because it has fixed size. If we want to insert a new thing. it wouldn't always be possible. Double linked list can do the task but there will be two pointers needed for each node so there will be memory problem, so I think single linked list will fulfill all given requirements. Am I right? Please correct me if I am missing any point. There is also one more question that instead of choosing one of them, can I make combination of one or more data structures given here to meet all the requirements?

Sabiqa Rani
  • 51
  • 10
  • nowadays memory is not as precious as it once was, i recommend a data structure with more features and capabilities to accommodate any and all requirements that arise. double link list is the most powerful of the 3. – RAZ_Muh_Taz Jan 26 '18 at 22:47

3 Answers3

0

Each of those has its own benefits and downsides.

For search speed, I'd say arrays are better suitable due to the quick lookup times. Since an array is a sequence of same-size elements, retrieving the value at an index is just memoryLocation + index * elementSize. For a linked list, the whole list needs traversing. Arrays also win in the "less memory" category, since there's no need to store extra pointers.

For insertions, arrays are slow. You'll need to traverse the array, copy contents to a new array, assign the new array, delete the old one... Insertions go much quicker in linked- or double lists, because it's just a matter of changing one or two pointers.

In the end, it all just depends on the use case. Are you inserting a lot? Then you probably want to consider a non-array structure. Do you need many quick lookups? Consider those arrays again. Etc..

See also this question.

Stratadox
  • 1,291
  • 8
  • 21
  • What will your opinion about application for a shopping mall to maintain the inventory of different products? I mean in this case, insertion and updation and searching occur at the same rate. So what will be the best? – Sabiqa Rani Jan 26 '18 at 21:50
  • It is impossible to draw such conclusion without a lot more information. My advice would be to just pick a solution that works, then measure the actual rates of insertion, updating, searching and don't forget plain lookups. Use that data as input for three different performance tests (for array, list and linked) and see which data structure is best for your situation. – Stratadox Jan 26 '18 at 21:56
0

"What is the best option between these three data structures when it comes to fast searching, less memory, easily insertion and updating of things".

As far as I can tell Arrays serve the purpose.

  1. Fast search: You could do binary search if array is sorted. You dont get that option in linkedlist

  2. Less memory: Arrays will take least memory (but contiguous memory )

  3. Insertion: Inserting in array is a matter of a[i] = "value". If array size is exceeded then simply export data into a new array. That is exactly how HashMaps / ArrayLists work under covers.

  4. Updating things: Only Arrays provide you with Random access. a[i] ="new value".. updated in O(1) time if you know the index.

Tanvi Jaywant
  • 375
  • 1
  • 6
  • 18
  • I have agreed to your all points except the 3rd one. because take a supposition of an application for a shopping mall to maintain the inventory of different products. In this case when the new product will arrive, it should be added to inventory what we array has filled already? I don't want to edit the code in this case to export elements into another array. I will need something like list which grow organically – Sabiqa Rani Jan 26 '18 at 23:00
  • I agree ! Again a lot of it depends on application. An update on a HashMap will use a combination of arrays and linkedlist :) – Tanvi Jaywant Jan 26 '18 at 23:40
0

  • A linked list is usually the best choice when we don’t know in advance the number of elements we will have to store or the number can change dynamically.

  • Arrays have slow insertion and deletion times. To insert an element to the front or middle of the array, the first step is to ensure that there is space in the array for the new element, otherwise, the array needs to be RESIZED. This is an expensive operation. The next step is to open space for the new element by shifting every element after the desired index. Likewise, for deletion, shifting is required after removing an element. This implies that insertion time for arrays is Big O of n (O(n)) as n elements must be shifted.

  • Using static arrays, we can save some extra memory in comparison to linked lists because we do not need to store pointers to the next node

  • a doubly-linked list support fast insertion/removal at their ends. This is used in LRU cache, where you need to enter new item to front and remove the oldest item from the end.

Yilmaz
  • 35,338
  • 10
  • 157
  • 202