Array vs. Linked List

  • Enumerate the advantages & disadvantages of a dynamically linked list vs. an array-based implementation.

The array is a static data structure. Its length is set when the array is created, and it is fixed. A linked list is a dynamic data structure. The size (number of nodes in a list) is not set and can grow/shrink on demand.

Insertion/deletion to the front or at the middle of an array is expensive; it requires shifting other elements to make/fill a gap. However, insertion/deletion in a Linked List can be done as cheaply as updating a few reference variables (we will see this soon).

One disadvantage of a linked list is that it does not allow direct access to the individual elements. For example, suppose you want to access a particular item. In that case, you have to start at the head and follow the references until you get to that item.

Another disadvantage of a linked list is that it uses more memory than an array (to store a reference to the next node for each element).

Resource