Lecture Notes for SE 598, Data Structures and Algorithms

14 June 2000, Implementing Vectors

1. operations and behavior

   1. create - create a vector

   2. delete - delete a vector

   3. read - place a value in a vector

   4. write - retrieve a value from a vector

   5. grow - add a new element to the end of the vector

   6. shrink - delete an element from the end of the vector

   7. size - return the number of elements in a vector

2. design

   1. what data structures are best for implementing vectors?

   2. how can the operations best be implemented?

   3. these questions are related

   4. examples

      1. use an array

         1. creating is fast, deleting is interesting

         2. reading and writing are fast and easy

         3. grow is simple but slow, shrink is easy

         4. size is easy

      2. use a linked list

         1. creating is fast, deleting is slow

         2. reading and writing are slow and not so easy

         3. grow and shrink are easy and either fast or slow

         4. size is easy

      3. a trick - combine complimentary implementations

         1. use a linked list with an array index

         2. creating is fast, deleting is slow

         3. reading and writing are fast and easy

         4. grow is simple but slow, shrink is easy

         5. size is easy

      4. don't forget the exotics

         1. functional array implementation - an array is a function mapping integers to array elements

      5. what will you do

         1. the kiss principle - keep is simple, stupid

            1. quickest to results

            2. reasonable chance of first-order success - performance issues may be week, for example

            3. a working implementation gives you the most valuable data you can have

            4. but: make sure your implementation is well hidden so changes can be kept local

         2. use arrays

3. implementation

   1. create - not an array

   2. delete - usually messy and implementation dependent

   3. read - simple

   4. write - simple

   5. grow - either there's room or there isn't

   6. shrink - error conditions

   7. size - simple

This page last modified on 12 June 2000.