Static and dynamic list structure
Static lists are of fixed size. They are mostly implemented using arrays. Dynamic lists' size can be varied during runtime. They are mainly implemented as linked lists. Static lists may cause memory wastage but there is no such problem in dynamic lists. Static lists take less time to compute but dynamic lists take more time to compute.
Summary
Static lists are of fixed size. They are mostly implemented using arrays. Dynamic lists' size can be varied during runtime. They are mainly implemented as linked lists. Static lists may cause memory wastage but there is no such problem in dynamic lists. Static lists take less time to compute but dynamic lists take more time to compute.
Things to Remember
- Static lists, being fixed sized, are implemented using arrays.
- Dynamic lists, having dynamic size, are implemented as linked lists.
- The memory may get wasted in static lists, but there is no wastage in dynamic lists.
- Static lists take less computation time but the computation time is more in dynamic lists.
MCQs
No MCQs found.
Subjective Questions
No subjective questions found.
Videos
No videos found.
Static and dynamic list structure
Static data structures are of fixed size (eg: array) i.e. the memory allocated remains same throughout the program execution.
Dynamic data structures, on the other side, have flexible (eg: linked list) size i.e. they can grow or shrink as needed to store data during program runtime.
The static implementation allows faster access to elements but is expensive for insertion/deletion operations whereas in the case of dynamic implementation, the access to elements is slower but insertion/deletion operations are faster.
In the case of static data structures, the memory space is allocated to the actual operations on the list. Hence, the memory may go wasted or may be insufficient in cases. So, static implementation requires the knowledge of the exact amount of data in advance. If there is no certainty about the amount of data, dynamic implementation is to be used.
Static vs Dynamic List
| Static List | Dynamic List |
| Array Implementation | Linked list implementation |
| Static size of list | Dynamic size of list |
| Suitable if fewer nodes are used | Suitable if large no. of nodes are used |
| Programming implementation is easy | Programming implementation is difficult |
| Less computation time | More computation time |
The static (array) implementation of the list is covered in the note "Array Implementation of List". The dynamic implementation of the list will be covered in the upcoming chapter "Linked List."
References
1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
2. G. Brassard and P. Bratley, “Fundamentals of Algorithms”
Lesson
List
Subject
Computer Engineering
Grade
Engineering
Recent Notes
No recent notes.
Related Notes
No related notes.