Class Notes (1,100,000)
CA (620,000)
UW (20,000)
CS (1,000)
CS138 (10)
Lecture 12

CS138 Lecture Notes - Lecture 12: Dynamic Array, Runtime System, Linked List

Computer Science
Course Code
Michael Godfrey

This preview shows half of the first page. to view the full 2 pages of the document.
Data Lecture 12
February 4, 2013
Dynamic Arrays
Use a vector instead except fir Assignment #2
Vectors (and other library containers) are implemented using dynamic arrays
We are just looking under the hood to better understand what is going on
Statically Allocated Arrays
Come from C
Storage is allocated on the stack
Array “extent” (size) must be a compile-time constant (usually)
Dynamically-Allocated Arrays
C++ only
Storage allocated on heap
Array extent can be any positive integer
o Checked at “instantiation” of array
Must delete[]A when done
Can’t programmatically access extent of dynamic array except by “cheating”
o Instead, use instance of class vector or array
Can’t return an array from a function, but CAN return a ptr, so we do that
The run-time system needs to store the extent somewhere to know how many elements it is
pointing to sot it can delete the right number of elements
Cant store extent with the pointer as it’s just an int* or string* so this would break normal pointer
Can’t store the size right at the beginning of the array
o Eg: a[0] would break normal array indexing arithmetic
The compiler and runtime can decide to do any number of things but the most common is to store
the extent in the 4 bytes just before a[0]
The generic “thing” we’ve been using is called a “linked list”
o Special pointer to first element
o Each element ahs a ptr to the next
o The next ptr of the last element is NULL
o Linked list can be unordered, ordered by arrival time (stacks, queues), ordered by data
(sorted by name) or ordered by some mixture (priority, queue)
You're Reading a Preview

Unlock to view full version