Basics

Data structure is just a way to organize data

User defined data structures are either linear or non-linear

Linear (array, linked list, stack, queue) vs non-linear (graph, tree)

set is faster than list (hint: look at its implementation, but don’t forget trade-offs)

Common operations: inserting, deleting, sorting, searching, merging, traversing

ADT:

  1. Operations
  2. Data Structure
  3. Error Conditions

Program \(\leftrightarrow\) ADT (functions, data)

All primitives are ADT

Primitive data structures:

  • int (1, 2, 3, etc.)
  • float (1.0, 1.1, etc.)
  • character (‘a’, ‘b’, etc.)
  • pointer (*, **, etc.)
  • boolean (true, false)

unsigned integers integers that are always positive, examples: memory addresses, color values (RGB)

signed integers

##

Consider LIFO (last in first out) and FIFO (first in first out)

  • Queue = first in first out
  • Stack = last in first out

infix, prefix, postfix