Please enable JavaScript.

Coggle requires JavaScript to display documents.

Abstract Data Types and Data Structures, Element Implementations - Coggle…

- - - - Class List is a template of one parameter, named E for “element”. E serves as a placeholder for whatever element type the user would like to store in a list.
        
        . The key design decision embodied in this ADT is support for the concept of a current position. For example, member moveToStart sets the current position to be the first element on the list,
        
        The intention is that any implementation for this ADT support the concept of a current position.
        
        Find method ADT
        
        // Return true if "K" is in list "L", false otherwise bool find(List<int>& L, int K) {
        int it;
        for (L.moveToStart(); L.currPos()<L.length(); L.next()) {
        it = L.getValue();
        if (K == it) return true ; // Found K } return false; // K not found }
- - - - the array-based list implementation is defined to store list elements in contiguous cells of the array, the insert, append, and remove methods must maintain this property. Inserting or removing elements at the tail of the list is easy,
- - - - . Objects in the Link class contain an element field to store the element value, and a next field to store a pointer to the next node on the list. The list built from such nodes is called a singly linked list, or a one-way list, because each list node has a single pointer to the next node on the list
        
        Elements of a linked list
        
        The list’s first node is accessed from a pointer named head. To speed access to the end of the list, and to allow the append method to be performed in constant time, a pointer named tail is also kept to the last link of the list. The position of the current element is indicated by another pointer, named curr.
        
        The value cnt stores the length of the list.
        
        the linked list class does not need to declare a fixed-size array when the list is created, this parameter is unnecessary for linked lists. It is ignored by the implementation.
  - - - Array-based lists have the advantage that there is no wasted space for an in- dividual element. Linked lists require that an extra pointer be added to every list node.
        
        Array-based lists are faster for random access by position. Positions can easily be adjusted forwards or backwards by the next and prev methods. These opera- tions always take Θ(1) time. In contrast, singly linked lists have no explicit access to the previous element, and access by position requires that we march down the list from the front (or the current position) to the specified position
        
        hen implementing the array-based list, an implementor could allow the size of the array to grow and shrink depending on the number of elements that are actually stored. This data structure is known as a dynamic array
        
        in c++ we have the bibliotec (VECTOR)
        
        Vector classes implement a dynamic array. Dynamic arrays allow the programmer to get around the limitation on the standard array that its size cannot be changed once the array has been created. This also means that space need not be allocated to the dynamic array until it is to be used. The disadvantage of this approach is that it takes time to deal with space adjustments on the array. Each time the array grows in size, its contents must be copied.
    - - inked lists are more space efficient when implementing lists whose number of elements varies widely or is unknown. Array-based lists are generally more space efficient when the user knows in advance approximately how large the list will become
- - - - Besides C ++ templates, there are other techniques that implementors of a list class can use to ensure that the element type for a given list remains fixed, while still permitting different lists to store different element types. One approach is to store an object of the appropriate type in the header node of the list (perhaps an object of the appropriate type is supplied as a parameter to the list constructor), and then check that all insert operations on that list use the same element type