CMPE 226 • Midterm I • Data Structures

Introduction

Definition and Decleration

Assignment and Dereference

Be Careful!

Pointer of Pointers - new Keyword

Pointers with Arrays

sizeof() - malloc() - free()

delete Keyword

Pointers as Function Parameters

Pointers of Functions

Example 1

Example 2

Example 3

Static Array vs Dynamic Array

2D Static Arrays

2D Dynamic Arrays

Efficiency of Pointers

Example 1

Example 2

Definition of Recursion

An Example: Factorials

Another Example: Fibonacci Numbers

Another Example: Binary Search Operation

Motivation

Big-O Notation

Big-Omega Notation

Big-Theta Notation

Fundamental Rules

Analyzing Complexity

Example 1

Example 2

Example 3

Recurrences

Example 4

Some Background Information

What is a linkedlist?

Reminder: Structs

Constructing Linkedlists

Head and Tail Pointers

Printing a Linkedlist

Adding a Node to the End

Adding a Node in between Two Nodes (Add to a Sorted List)

Finding a Node in the List

Deleting a Node

Deleting the List

Example 1 (Parts a-c)

Example 1 (Parts d-e)

Example 2 (Part 1)

Example 2 (Part 2)

What is a Circular Linkedlist?

Constructing the List

Adding a Node to the Beginning/End

Adding a Node in between Two Nodes (Add to a Sorted List)

Counting Number of Elements

Finding a Node in the List

Deleting a Node

Example 1 (Parts a-c)

Example 1 (Parts d-e)

Example 2 (Part 1)

Example 2 (Part 2)

Constructing the List

Adding a Node to the Beginning

Adding a Node In Between two Nodes (Add to a Sorted List)

Adding a Node to End of the List

Deleting a Node from the Beginning

Deleting a Node in between Two Nodes (Deleting from a Sorted List)

Deleting a Node from the End

Finding a Node in the List

Example 1 (Parts a-c)

Example 1 (Parts d-e)

Example 2 (Part 1)

Example 2 (Part 2)

Our First Data Structure

Code for Amateurs

Linkedlist.h

ListNode

ListItr

List

Example 1

Example 2

Example 3

What is a Stack?

Stack Operations

Static Int Stack Implementation

Using StaticIntStack

Dynamic Int Stack

Dynamic Int Stack Implementation

Using DynIntStack

What is a Stack?

Stack.h

Implementation

Example 1

Example 2

Example 3

Recursion 1

Recursion 2

Recursion 3

Single Linked List 1

Single Linked List 2

Single Linked List 3

Single Linked List 4

Single Linked List 5

Circular Linked List 1

Doubly Linked List 1

Doubly Linked List 2

Doubly Linked List 3

Doubly Linked List 4

Templated Linked List 1

Templated Linked List 2

Templated Linked List 3

Templated Linked List 4

Stack 1

Stack 2

Stack 3

Templated Stack 1

Templated Stack 2

Templated Stack 3