1. Introduction

Read the outline

The main focus of this course is:

  • The organization and manipulation of data

  • Organize data into collections, such as

    • Stacks

    • Queues

    • Bags

    • Trees

  • How to implement various data structures

  • Algorithm Analysis

1.1. Data Structures

  • A data structure is some structure used to store, organize, and manage data

1.1.1. Linear Data Structures

  • A linear data structure is one where the data is stored in a line

  • Generally, everything has one thing that comes before it (predecessor) and one thing that comes after it (successor)

1.1.1.1. Stacks

  • Like a stack of plates

  • The last thing put on top of the stack will be the first thing off

../../_images/stack_example.png

Adding a plate to the top of a stack of plates.

1.1.1.2. Queues

  • Like any line you’ve ever waited in

  • First person in the line will be the first person served

../../_images/queue_example.png

A first come first served queue/line.

1.1.1.3. Bags

  • Like Python lists, but we can define specific types

    • Ordered

    • Indexed

    • Unordered

../../_images/ordered_bag_example.png

An element being added to an ordered bag such that the order is preserved.

1.1.2. Nonlinear Data Structures

  • Sometimes data has no natural linear ordering

  • For example, in the below figures:

    • What comes after root in the filesystem example?

    • What comes after “Toronto” in the graph example?

1.1.2.1. Trees

  • Like your file system

  • Information is stored in a hierarchy

../../_images/tree_example.png

A simple file system on a computer.

1.1.2.2. Graphs

  • A way to represent relationships between things

  • Like a road network, or flight routes

../../_images/graph_example.png

A hypothetical network of available flights between airports.

1.1.3. Abstract Data Types

  • These collections of data are sometimes called Abstract Data Types (ADTs)

    • ADTs because they are an abstract idea of how we want to interact with our data

      • What they do and how we interact with them

    • We do not talk about specific implementations and implementation issues

  • A specific implementation of these ADTs is a data structure

  • For example

    • The Stack ADT could be implemented with an array — ArrayStack

    • A Queue ADT could be implemented with a series of linked nodes — LinkedQueue

1.2. Java

  • We are now going to switch programming languages to Java

  • What about Python?

    • Don’t worry, you’ll quickly realize how similar Python and Java are

    • More than that, the important ideas are the same between the languages

    • There are some java-isms I will point out along the way

    • Python’s flexibility often gets in the way when our programs grow in complexity

Warning

Programming and Java are not a direct learning objective of this course. We are learning abstraction, data structures, and algorithms.

1.2.1. How do I go about programming Java!?

1.2.2. Can we Write Code Now?

  • Below is an example of Hello, world! in Python and Java

1# Python --- hello world
2print("Hello, world!")

1// Java --- hello world
2public class SomeClass {
3    public static void main(String[] args){
4        System.out.println("Hello, world!");
5    }
6}

  • Other than the boilerplate code in the Java example, they’re nearly the same

    • System.out.println("Hello, world!") is doing the job of print

    • Mind the fact that our strings have double quotes (") as single quotes is for a single character

      • "Hello" vs. 'h'

  • What about:

    • public

    • class

    • static

    • void

    • main

    • String[] args

    • { … }

public

  • Visibility modifier

  • Remember adding underscores in Python to our attributes?

  • More on this later

1def __init__(self, firstName='John', lastName='Doe', stNum='000000000', curAvg=0):
2    # The following attributes are "private"
3    self._firstName = firstName
4    self._lastName = lastName
5    self._stNum = stNum
6    self._curAvg = curAvg

class

  • This is the same idea as a Python class

  • Everything in Java needs to be within a class

static

  • Means that the function (or variable) belongs to the class, and not an instance of the class

    • We don’t need to make an instance of the class to use the method

  • A good example of this in Java is the Math class

  • More on this later, but here is an example of calling a method on a class vs. an instance of the class

1// Calling a static function from the class "SomeClass"
2SomeClass.someStaticFunction();
3
4// Creating an instance of SomeClass and calling a method
5SomeClass anInstance = new SomeClass();
6anInstance.someMethod();

void

  • This is the return type of the function

  • Like Python, all values have a type in Java

    • Variables

    • Return types

  • Unlike Python, we must be explicit about our types in Java

  • In this case, the function returns nothing, so the type is void

main

  • A very very very special function

  • The main function is the function that is called when we tell our computer to run our programs

  • Line 1 of the main function is the first line run by the program

String[] args

  • This defines a variable called args that is an array (indicated by the []) of Strings

    • Remember, all values need a type

  • This is how we give our programs command line arguments

    • Basically parameters for our whole program

  • More on this later — not overly important right now

{ … }

  • In Java we don’t use indentation to define scope, we use open and close squiggly braces

  • You will quickly realize how great this is when compared to whitespace/indentation

1.3. For Next Time