CODEWITHSUNDEEP
operating-systemstackheap-memory
user1369975
user1369975

Reputation: 420

Faster access time,stack or heap?

The classic Algorithm Design Manual by Steven Skienna states that linked list is faster than dynamic array in terms of creation.Is this the reason of Heap performing faster?Can anyone explain it in terms of Operating Systems?

Upvotes: 0

Views: 172

Answers (1)

Habib
Habib

Reputation: 223217

Both Link list and dynamic array are maintained on heap. Insertion in dynamic array may cause the array to grow, whereas with link list it will be addition to the end. Even if the insertion is in the middle of link list, it will require time to search and later just one operation to add pointer to the previous node. Link list will not require adjustment for adjacent memory places.

Dynamic Array - Wiki

Compared to linked lists, dynamic arrays have faster indexing (constant time versus linear time) and typically faster iteration due to improved locality of reference; however, dynamic arrays require linear time to insert or delete at an arbitrary location, since all following elements must be moved, while linked lists can do this in constant time. This disadvantage is mitigated by the gap buffer and tiered vector variants discussed under Variants below. Also, in a highly fragmented memory region, it may be expensive or impossible to find contiguous space for a large dynamic array, whereas linked lists do not require the whole data structure to be stored contiguously.

Upvotes: 1

Related Questions