Please enable JavaScript.
Coggle requires JavaScript to display documents.
Abstract Data Types and Data Structures, Lists, Stacks, and Queues -…
-
Lists, Stacks, and Queues
Lists
We define a list to be a finite, ordered sequence of data items known as elements.
-
-
Linked Lists
The linked list uses dynamic memory allocation, that is, it allocates memory for new list elements as needed.
Implementations for the remaining operations are straightforward, each requiring Θ(1) time.
-
Linked lists require that a pointer be added to every list node. If the element size is small, then the overhead for links can be a significant fraction of the total storage.
Element Implementations
-
The third issue that users of the list implementations must face is primarily of concern when programming in languages that do not support automatic garbage collection.
In general, the larger the elements and the more they are duplicated, the more likely that references to shared elements is the better approach.