C S 314 Chapter Notes - Chapter 5: Abstract Data Type, Parsing, Linked List
Document Summary
An array is a contiguous group of elements, all of the same type, indexed by an integer. In a sense, the array is the most basic data structure, since the main memory of a computer is essentially one big array. The major advantage of an array is random access or o(1) access to any element. (paging and cache behavior can add significantly to access time, but we will ignore that. ) The major disadvantage of an array is rigidity: Storage may be wasted because an array is made larger so it will have two arrays cannot be combined some extra space. In java, an array is an object, so it is possible to expand it in effect by making a new larger array, copying the old array contents into the new array, and letting the old array get garbage-collected. Stacks are used in many places in computer science: Most programming languages keep variable values on a runtime stack.