VietMX Staff asked 3 years ago
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 amortised
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 (a persistent data structure is a data structure that always preserves the previous version of itself when it is modified). This advantage allow tail sharing between two linked list. Tail sharing makes it easy to use linked list as copy-on-write data structure.
- Linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local – affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked list. With an array, any change that modifies the size of the array is likely to require locking a large portion of the array.
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.
