How are linked lists more efficient than arrays?

  • Insertion and Deletion
  1. Insertion and deletion process is expensive in an array as the room has to be created for the new elements and existing elements must be shifted.
  2. But in a linked list, the same operation is an easier process, as we only update the address present in the next pointer of a node.
  • Dynamic Data Structure
  1. Linked list is a dynamic data structure that means there is no need to give an initial size at the time of creation as it can grow and shrink at runtime by allocating and deallocating memory.
  2. Whereas, the size of an array is limited as the number of items is statically stored in the main memory.
  • No wastage of memory
  1. As the size of a linked list can grow or shrink based on the needs of the program, there is no memory wasted because it is allocated in runtime.
  2. In arrays, if we declare an array of size 10 and store only 3 elements in it, then the space for 3 elements is wasted. Hence, chances of memory wastage is more in arrays.
  • It’s easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
  • As you mentioned, it’s easier for a linked list to grow organically. An array’s size needs to be known ahead of time, or re-created when it needs to grow.
  • Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.
  • As long as your iterations all happen in a “foreach” context, you don’t lose any performance in iteration.