UTPA STEM/CBI Courses/Computer Science/Linked Lists

Course Title: Computer Science II

Lecture Topic: Linked Lists

Instructor: Emmett Tomai

Institution: UTPA

Backwards Design

Course Objectives

• Primary Objectives- By the end of the next class period students will be able to:
  • Use a linked list to solve problems involving storing variable-size (1 dimensional) data sets.

• Sub Objectives- The objectives will require that students be able to:
  • Implement a linked list using a primitive data type or class
  • Implement a linked list using templates
  • Implement a linked list using inheritance
  • Implement append, (sorted) insert and delete

• Difficulties- Students may have difficulty:
  • Defining and using classes
  • Using pointers
  • Understanding recursive functions

• Real-World Contexts- None, really, because this is pedagogical - in the real world you use STL/Boost containers, you don't write your own. But, ignoring that those exist, any variable-length data set with insert/remove/search will do.
  • phone numbers have insert and edit, but don't delete much
  • rosters, team lists and the like don't typically add/delete on the fly
  • opt-in/opt-out systems have insert/delete
  • small data is easy to write on the board or on paper
  • however, complex data is more conducive to interesting template/inheritance points

Model of Knowledge

• Concept Map
  • Understand array storage
    • Limitations of compile-time allocation
    • Limitations of run-time (dynamic) allocation
  • Array strategy weaknesses
    • Fast append, but run out of space
    • Delete requires copy
    • Insert requires copy
  • Array strategy strengths
    • Random access, good search for 1-d
  • Understand linking nodes
    • Sequential access
    • Data recursion
  • Contrast with array operations
    • No inherent size limitations
    • Slow access (binary search stinks)
    • Slow append
    • Fast insertion/deletion
  • Variability with templates/inheritance
    • Template data pointer type
    • Storing derived classes in a base class list

• Content Priorities
  • Enduring Understanding
    • Link nodes and traversal
    • Insert/delete operations
  • Important to Do and Know
    • Flexibility with templates and inheritance
  • Worth Being Familiar with
    • Access limitations
    • Poor binary search

Assessment of Learning

• Formative Assessment
  • In Class (groups)
    • Group code review
  • Labs (individual)
    • Complete labs implementing and using basic linked lists

• Summative Assessment
  • End-of-module quiz in class

Legacy Cycle

OBJECTIVE

By the next class period, students will be able to:

• Define and use classes
• Use pointers
• Understand recursive functions

The objectives will require that students be able to:

• Implement a linked list using a primitive data type or class
• Implement a linked list using templates
• Implement a linked list using inheritance
• Implement append, (sorted) insert and delete

THE CHALLENGE

A friend calls you tomorrow and says, I hear you know computers, and I have a problem I need help with. The casino where I work paid a guy to write a program that keeps track of how much players are winning and losing, to try to catch on to cheaters. He showed us some tests where it worked, but we hooked it up to the real system and it keeps crashing. I can pay you $1000 to help me fix this problem. What do you think is wrong?

GENERATE IDEAS

Debugging process: what questions should you be asking? what was the error? under what conditions does it crash? is it always consistent? what was different in the tests? can I see the code?

The goal here is to focus in on memory problems - the test environment involved only a dozen entities while the production environment involves hundreds, coming and going. This leads to a particular piece of the code, the container class which uses a static array, appends only, and doesn't delete.

Memory management: how do you deal with large, unknown numbers of entities coming and going?

MULTIPLE PERSPECTIVES

The students know enough to implement a resorting array (solving the delete problem), or dynamic allocation and copy (solving the growth problem). These together solve the functional problem, but lead to spikes of heavy load.

STL is something like a multiple perspective, at least confirming that solutions exist. Complexity guarantees could lead to the discovery that there must be something better, but that's perhaps a bit out of field.

RESEARCH & REVISE

Linked lists, insert/append/delete performance, search performance with ordering, iterative access.

TEST YOUR METTLE

Lab work, implementing the class with a linked list.

GO PUBLIC

Mixed code review.