3.1 -Data Structures

• Static Structures - Fixed Length, Inefficient due to whitespace, easy to program, easy to calculate storage size
• Dynamic structures - accommodates data entered, complex to program, storage is hard to calculate
• Define Array

  A collection of variables of the same data type
• Array Properties

  Elements accessed through indexing, static, immutable, null values written for deleted data
• Define a Stack

  An array or linked list with a pointer to indicate the top of the stack
• Stack Properties

  First-In, Last-Out, added data is pushed to the top of the stack, removed data is popped from the top of the stack, used in web browser back buttons
• Define Queues

  Two variables, one points to the first item and another points to the next free space
• Queues Properties

  First-In, First-Out, Used to maintain playlists and schedule CPU tasking
• Define Linked Lists

  Nodes linked together by pointers to the next item and the data it is storing
• Linked List Properties

  Dynamic, powerful, used to implement other data structures
• Define Binary Trees

  A series of nodes connected by branches. Each node can have up to two branches.
• Binary Trees Properties

  Non-Linear, left branch's data is less than the node above it, right branch's data is more than the data above it, used in hierarchical structures
• Pre-Order Binary Tree Traversal

  Root, Left, Right; Used to clone trees; First Pass
• In-Order Binary Tree Traversal

  Left, Root, Right; Used to sort and search; Second Pass
• Post-Order Binary Tree Traversal

  Left, Right, Root; Used to undo a binary tree; Third Pass
• Define Hashing

  Using data entered, primary key, to generate a storage location
• Hashing Properties

  Data is direct access, collisions can occur if data is hashed to the same location, MOD function is a common example, separate chaining can resolve collisions but slow down a search