Quick Index
Overview
OO Review
Fixed Array Review
References
Overview
This chapter discusses concepts and algorithms for a dynamic array. Algorithms will be shown in pseudocode or human language text.
A dynamic array conforms (meets) the
DynamicList ADT spec (blueprint)
A primary purpose of a DynamicArray is to solve the
BIG DISADVANTAGE
of a fixed array.
Let's take a
one minute peek here...
at how we ended our discussion on a fixed array. We concluded:
Fixed arrays have a "BIG DISADVANTAGE" of not support adding, inserting, or removing of elements
In this chapter we'll be learning the concepts of a
DynamicArray
whose purpose is:
Retain the efficient indexed access performance of a fixed array
Make the array dynamic, i.e., supporting adding, inserting and removing elements
Overcome the fixed array's big disadvantage of not supporting adds/removes
OO Review
Key
oo
review concepts to prep us for this chapter:
Method Summaries
Helper (Buddy) Methods
The special object 'this'
Fixed Array Review
Big Advantage
Recall that a fixed array indexed access is terrifically fast. And, the indexed access time does
not
increase as the size of the array increases.
Big Disadvantage
The size (number of elements) in the fixed array is fixed.
In other words, we can not add or remove elements.
References
wiki
algolist
algorithmtutor.com
geeksforgeeks
brilliant
Data Structures and Abstractions (Book by Carrano and Henry) -- Chapter: "A List Implementation That Uses An Array"
Data Structures And Algorithms (DSA) (Chapter 304 - Dynamic Array)
Chapter 304 - Dynamic Array
Introduction
Contents
Intro
Design
Add
Grow
Insert
Remove
Access
Design-2
Memory
Chapter
Top
Search
TOC