Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lists - Coggle Diagram
Lists
Linked List
Linked lists are dynamic arrangements, allowing them to grow or shrink at runtime by allocating and deallocating memory
Linked lists efficiently utilize memory. Since their size can adjust dynamically, there’s no wasted memory due to pre-allocation
Adding or removing elements in a linked list is efficient. You only need to update pointers without shifting other elements.
Linked lists use nodes to represent elements, where each node contains the data and a pointer to the next node.
Array based list
Arrays offer constant time access to any value in the array. This property allows get(i) and set(i, x) operations to run in constant time.
Adding or removing an element near the middle of a list requires shifting a large number of elements in the array.
Arrays cannot dynamically expand or shrink. Resizing involves creating a new array and copying data.
Key points for an array-based list:
Define an array to hold the elements.
Keep track of the current number of elements (length).
Implement functions for adding, removing, and accessing elements.
-
A list is a finite, ordered sequence of data items known as elements.
Each element in a list has a position.
The term “ordered” means that each element has a position in the list, but it does not necessarily imply that the elements are sorted by value.
The first position in the list is denoted as 0, so if there are n elements in the list, they are given positions 0 through n-1.
Element implementations
For implementors who wish to minimize the number of classes created by
the compiler, the lists can all store a void* pointer,with the user performing the
necessary casting to and from the actual object type for each element. However, this approach requires that the user do his or her own type checking, either to enforce
homogeneity or to differentiate between the various object types.
To use list implementations need to be aware of memory management, especially when dealing with user-defined classes or pointers to objects. Responsible memory handling prevents memory leaks and dangling pointers.