Logout

Home Topic 5 Last 5.1.5 Next 5.1.11

Applications

5.1.18

Define the term dynamic data structure.

 

Teaching Note:

 

Sample Question:

sdfsdfsf

JSR Notes:

Reminder of the term "data structure"

Recall that by a structure, we mean any group of data, as opposed to single pieces of data. So ints, chars, and booleans, for example are not "structures", since they each hold one single piece of data each. An array, which is the only Java fundamental data structure, is a data structure because it can hold more than one piece of data; it holds a group of things.

Hey,... Dynamic: Isn't this Collections Again?

In terms of what comes next in the curriculum being dynamic data structures, this may ring a bell. When we looked at Collections in Topic 4, the one main distinguishing feature about them was that they were dynamic, meaning that unlike arrays, they could shrink and grow.

The truth of the matter is that there was a lot more than met the eye with Java Collections than just that. Indeed there is even more than meets the eye to Java Collections beyond what is covered next, in Topic 5. Lists (as we called them in Topic 4), and particular implementations of lists here in Topic 5, namely Stacks and Queues along with Trees feature prominently in the Java Collections Framework, but there are other Java Collection Framework ADTs also, beyond the scope of this course.

So to keep everything straight in an IB light, just think of the Collections work we did in Topic 4 (with our OurList class) as being done through an IB filter of data structures, showing us that there is more than just array. And think of our upcoming Collections work in Topic 5 and HL OOP (using ArrayList and LinkedList and Trees) as being through the IB filter of dynamic data types.

 

Dynamic

Dynamic is a word, which in general English, implies change and changeability. The change that "dynamic" refers to, in terms of data structures in a programming language, is change in the number of things being kept/stored/contained. So it refers to dynamic size.

 

Definition of Dynamic Data Structure

A dynamic structure is a collecton of data which can grow or shrink in size. Lists and trees are examples of dynamic structures.

 

Dynamic vs. Static

The programming term, which describes the opposite of a dynamic structure, i.e. a data structure that cannot change size, is static. So in terms of data structures, static means non changeable size, and dynamic means changeable size.

(Don't get this confused with the other main sense of the word static in programming. Recall that static can also mean only one copy. So any method, such as public static void main, cannot have a second copy of it made. This is opposed the multiple copies of template classes that can be made.)

But back to this sense of the word, static means not able to change size. The array data structure is the primary static, i.e. non-dynamic, data structure in Java.

 

Looking Forward to the Advantages of Dynamic Structures

As will be gone into more detail in coming assessment statements, there are distinct advantages to dynamic data structures, and disadvantages also. For now, note that the main advantage of dynamic data structures, along with their ability to change size, is that they don't waste memory. If a dynamic data structure holds, for example,182 things, it only takes up enough computer memory (RAM) to accommodate those 182 things. Meantime, arrays often waste memory by having many elements that are unused at a given point in time.