5.1.18 – 5.1.20 – Applications

5.1.18 – Define the term dynamic data structure

Dynamic Data structure is defined as “A dynamic data structure (DDS) refers to an organization or collection of data in memory that has the flexibility to grow or shrink in size, enabling a programmer to control exactly how much memory is utilized.”

  • These data structures can change size during the execution of a program
  • Dynamic data structures grow and shrink as required by the program
  • The size of the structure is determined during run- time
  • They are a very efficient use of memory space

5.1.19 – Compare the use of static and dynamic data structures

5.1.20 – Suggest a suitable structure for a given situation

What structure for what?

Lets explore:

  • Stacks
  • Queues
  • Linked Lists
  • Arrays
  • Binary Trees

Stacks

Best used for:

Perhaps the most important application of stacks is to implement function calls (methods).

Most compilers implement function calls by using a stack.

This also provides a technique for eliminating recursion from a program: instead of calling a function recursively, the programmer uses a stack to simulate the function calls in the same way that the compiler would have done so.

Conversely, we can often use recursion instead of using an explicit stack.

Queues

Best used for:

Computing applications: serving requests of a single shared resource (printer, disk, CPU),

Buffers

MP3 players and portable CD players, iPod playlist.

Playlist for jukebox: add songs to the end, play from the front of the list.

Interrupt handling: When programming a real-time system that can be interrupted (e.g., by a mouse click or wireless connection), it is necessary to attend to the interrupts immediately, before proceeding with the current activity. If the interrupts should be handles in the same order they arrive, then a FIFO queue is the appropriate data structure.

Linked Lists

Best when:

You need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

You don’t know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

You don’t need random access to any elements uYou want to be able to insert items in the middle of the list (such as a priority queue)

Arrays

Best when:

You need indexed/random access to elements

You know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

You need speed when iterating through all the elements in sequence.

Memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

Binary Tree’s

Binary Search Tree

Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages’ libraries.

Heaps

Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.

GGM Trees

Used in cryptographic applications to generate a tree of pseudo-random numbers.

Syntax Tree

Constructed by compilers and (implicitly) calculators to parse expressions.