Data Structs: What & Why?

• Arrangement of data
• How are numbers, characters, boolean represented in memory?
• How are floating point numbers stored in memory? (singles)
  How is a value stored? Retrieved? Used?
• What does a particular collection of bits in RAM mean?
  F00DCEDEBEEFDEAF
• For the most part we have been using these "abstract data types" w/o knowing details.
  Quite normal. How does WWW work? I mean really work?

Purpose of Data Structures and Algorithms

• Real-world data storage
  Personnel or student (customer) records, playoff standings, your individual grades in a class
  how is data stored in memory? would you data structure (organization of data) scale well?
• Programmer tools
  Print queue, method call chain (activation records)
• Real-world modeling
  Meteorological data, ATC (flight) data

Overview of Data Structures

• Mark pages (11-12) to refer back to
  Great list of pros/cons of various data structures
• Arrays (ordered or unordered) - elementary
• Stacks & Queues - LIFO & FIFO rules
• (Linked) Lists - elementary
• Trees - linked data structs that support various "rules"
  Binary, 2-3-4, RB, heap
• Hash tables - fast access "rules"
• Graph - generic linked structures

Overview of Algorithms

• a formalized plan to accomplish some task
• a step-by-step procedure for "calculations"
• an effective method expressed as a finite list of well-defined instructions for calculating a function.
  A mapping from a set of inputs to a set of
  permissible outputs (may be non-deterministic)
• For every data structure (even a variable)
  How do I store (insert) a value?
  How do I access (retrieve) a value to use it?
  Access all in specified order, perhaps sequentially
  How do I delete or get rid of the value?
  How do I order (sort) or maintain order of values?
• Represent relationships
• Recursion - exploit a recurrence relationship
• Abstract Data Types
  "Roughly speaking [ADTs are] a way of looking at a data structure: focusing on what it does and ignoring how it does the job." Lafore, p 202
• Abstract Data Types
  "In object-oriented programming... an Abstract Data Type is a class considered without regard to its implementation." Lafore, p 211
• Abstract Data Types
  However, a class is not necessarily an ADT!

Things you Know

• Database
  A collection of records, a file (a table). In Java, a collection of objects.
• Record
  A specific unit of closely related information A line in a table of information. A collection of fields In Java, an object
• Field
  An atomic unit of information In Java, a data member or field
• Key
  One or more fields used to uniquely identify a record. Primary key – a single (distinguished) field
• Object-Oriented Programming
  • Related to our elementary algorithms for dealing with data – objects…
  • Classes
  • Instantiation of objects: Constructors
  • Accessing methods & data
  • Public & Private
  • Deleting objects (C++)

Java

• types, ifs, loops,.. same
• Structure is different - main is within a class
• import instead of include
• use private or public for all declarations - everything is a data member
• All non-primitives need to be created using new
  String s = new String("hello");
• assignment of objects using = does not copy!!!!
• must write code to copy elements
• No pointers, no delete - garbage collection
• input and output very different - but BETTER
• See Bank account code sample
• See page 3 of Java C++ Comparison
• NOTE: Java's libraries include pre-existing data structures which you are NOT allowed to use in this course!