4

Why we need a linked list when we have dynamic array list?

I have studied static list and linked list. I have knowledge of dynamic array list. but I couldn't find out the exact difference between that Anyone please help me to answer this

Aadnan Farooq A
  • 626
  • 4
  • 8
  • 19

2 Answers2

14

Dynamic array is an array that resizes itself up or down depending on the number of content.

Advantage:

  • accessing and assignment by index is very fast O(1) process, since internally index access is just [address of first member] + [offset].

  • appending object (inserting at the end of array) is relatively fast amortized O(1). Same performance characteristic as removing objects at the end of the array. Note: appending and removing objects near the end of array is also known as push and pop.

Disadvantage:

  • inserting or removing objects in a random position in a dynamic array is very slow O(n/2), as it must shift (on average) half of the array every time. Especially poor is insertion and removal near the start of the array, as it must copy the whole array.

  • Unpredictable performance when insertion or removal requires resizing

  • There is a bit of unused space, since dynamic array implementation usually allocates more memory than necessary (since resize is a very slow operation)

Linked List is an object that have a general structure of [head, [tail]], head is the data, and tail is another Linked List. There are many versions of linked list: singular LL, double LL, circular LL, etc.

Advantage:

  • fast O(1) insertion and removal at any position in the list, as insertion in linked list is only breaking the list, inserting, and repairing it back together (no need to copy the tails)

  • Linked list is a persistent data structure, rather hard to explain in short sentence, see: wiki-link . This advantage allow tail sharing between two linked list. Tail sharing makes it easy to use linked list as copy-on-write data structure.

Disadvantage:

  • Slow O(n) index access (random access), since accessing linked list by index means you have to recursively loop over the list.

  • poor locality, the memory used for linked list is scattered around in a mess. In contrast with, arrays which uses a contiguous addresses in memory. Arrays (slightly) benefits from processor caching since they are all near each other

Others:

  • Due to the nature of linked list, you have to think recursively. Programmers that are not used to recursive functions may have some difficulties in writing algorithms for linked list (or worse they may try to use indexing).

Simply put, when you want to use algorithms that requires random access, forget linked list. When you want to use algorithms that requires heavy insertion and removal, forget arrays.

This is taken from the best answer of this question

I am convinced by this answer.

Weak to Enuma Elish
  • 4,622
  • 3
  • 24
  • 36
Shafi
  • 1,850
  • 3
  • 22
  • 44
  • 2
    I'm not. The author misuses big-O (there's no such thing as O(n/2)), calls O(n) "very slow" (I would reserve "very" for superlinear complexities), claims that the locality benefits of arrays are "slight" (they are so massive that even insertion at the start is faster in arrays up to several hundred cheap-to-copy elements), and makes a general claim about linked lists being persistent (single-linked lists *can* be persistent, but the standard forward_list is not, and double-linked lists can never be persistent). He also claims that you have to think with recursion for linked lists. – Sebastian Redl Feb 16 '16 at 09:51
  • Technically, there no problem with $O(n/2)$ with respect to the definition of $O$. It's just that $O(n) = O(n/2)$, and we usually prefer to say $O(n)$. – Manuel Lafond Feb 19 '20 at 14:56
  • Just to add, arrays are wonderful for heavy insertion provided all your data fits in memory - amortized cost of insertions is O(1). – Ravi R Oct 29 '21 at 11:44
2

Vector aka Dynamic Array: Like regular array. The continuous memory location is used for storing vector. Whenever you need to allocate more memory, and memory is not available in the current location, the entire array is copied to another location and extra memory is allocated.

List: Maintain a pointer in each element and that pointer points to the next element.

What are the complexity guarantees of the standard containers? Look at this link for more information.

Community
  • 1
  • 1
aaroh
  • 302
  • 2
  • 14