Chapter 6 LISTS AND STRINGS I1 List Specifications 2. List Implementations a). Class Templates (b). Contiguous c). Simply Linked d). Simply Linked with Position Pointer e). Doubly Linked
Chapter 6 LISTS AND STRINGS 1. List Specifications 2. List Implementations (a). Class Templates (b). Contiguous (c). Simply Linked (d). Simply Linked with Position Pointer (e). Doubly Linked
Chapter 6 LISTS AND STRINGS L3. Strings 4. Application: Text Editor 5. Linked Lists in Arrays 6. Application Generating Permutations 7. Pointers and pitfalls
Chapter 6 LISTS AND STRINGS 3. Strings 4. Application: Text Editor 5. Linked Lists in Arrays 6. Application: Generating Permutations 7. Pointers and Pitfalls
6.1 List Definition DEFINITION a list of elements of type T is a finite sequence of elements of T together with the following operations 1. Construct the list, leaving it empty 2. Determine whether the list is empty or not 3. Determine whether the list is full or not 4. Find the size of the list 5. Clear the list to make it empty 6. Insert an entry at a specified position of the list 7. Remove an entry from a specified position in the list 8. Retrieve the entry from a specified position in the list 9. Replace the entry at a specified position in the list 10. Traverse the list, performing a given operation on each entry
DEFINITION A list of elements of type T is a finite sequence of elements of T together with the following operations: 1. Construct the list, leaving it empty. 2. Determine whether the list is empty or not. 3. Determine whether the list is full or not. 4. Find the size of the list. 5. Clear the list to make it empty. 6. Insert an entry at a specified position of the list. 7. Remove an entry from a specified position in the list. 8. Retrieve the entry from a specified position in the list. 9. Replace the entry at a specified position in the list. 10. Traverse the list, performing a given operation on each entry. 6.1 List Definition
Comparison with Standard Template Library: The Stl list provides only those operations that can be implemented efficiently in a List implementation known as doubly linked, which we shall study shortly The stL list does not allow random access to an arbitrary list position The STL vector does provide some random access to a sequence of data values but not all the other capabilities we shall develop for a list In this way, our study of the list adt provides an introduction to both the stl classes list and vector
Comparison with Standard Template Library: ◆The STL list provides only those operations that can be implemented efficiently in a List implementation known as doubly linked, which we shall study shortly. ◆The STL list does not allow random access to an arbitrary list position. ◆The STL vector, does provide some random access to a sequence of data values, but not all the other capabilities we shall develop for a List. ◆In this way, our study of the List ADT provides an introduction to both the STL classes list and vector
Method Specifications List: ListO; Post: The list has been created and is initialized to be empty. void List clear(; Post: All List entries have been removed the list is empty
List :: List( ); Post: The List has been created and is initialized to be empty. Method Specifications void List :: clear(); Post: All List entries have been removed; the List is empty