Algorithms and Lists

Algorithms and Data Structures

Algorithms and Data Structures

Algorithms and data structures comprise the core conceptual concerns of computer science. Algorithms are how we do things. Data structures are how we represent things.

The two topics are intertwined. We will implement data structures to support certain algorithms. And we will design algorithms that utilize specific data structure capabilties.

Algorithm Analysis

Algorithm Analysis

As we proceed, we will spend more time talking about how long certain algorithms take and why—or performing algorithm analysis. To do this we use something called Big-O notation to describe the behavior of algorithms. Let’s define those terms:

Complexity Categories

Complexity Categories

We’ll take a very high-level view of Big-O as we get started with algorithm analysis. Let’s provide an overview of the different complexity categories that we’ll learn to identify, and some of the code features that are associated with them.

Array Lists

Array Lists

To get some practice with algorithm analysis, over the next few lessons we’ll be implementing a data structure known as a list. You’ve already been working with Java’s built-in Lists, so this will give you a peek at how they are actually implemented.

Lists store a sequence of elements. We already know how to do that using arrays, and we can build an implementation of lists on top of an array. Let’s see how!

// Initial SimpleArrayList

Remove

Remove

OK, this is good start. But so far all we have is a wrapper around an array! That’s not particularly interesting.

Indeed, the key difference between a Java array and list is that the size of the list can change. But doing this using a list that maintains are array internally requires more work. Let’s see how, starting with the remove operation. (You get to implement add as this lesson’s homework.)

// SimpleArrayList remove

Homework Restricted to Current CS 124 Students

A publicly-accessible version of this content is available at learncs.online.

Practice: SimpleArrayList get and set

Created By: Geoffrey Challen

/ Version: 2020.10.0

Let's begin building a simple list implementation that uses arrays to store the values. Create a class SimpleArrayList with a public constructor that initializes the list using a passed array of Object references. assert that the passed array is not null.

Next, implement:

1. Object get(int), which takes an int index and returns the Object at that index
2. void set(int, Object), which takes an int index and an Object reference and sets that value at the index to the passed reference.

Both your get and set method should assert that the index passed is valid for that SimpleArrayList. Here's an example of how your SimpleArrayList should work:

Don't overthink this! Both get and set should be two lines of code (including one for the assert).

WorkingPrevious

List Method Algorithm Analysis

List Method Algorithm Analysis

Next, let’s take a look at our core list functions and see how they perform. We’re going to use our new big-O vocabulary and try to understand the performance of get, set, and remove.

// SimpleArrayList performance

Homework Restricted to Current CS 124 Students

A publicly-accessible version of this content is available at learncs.online.

Homework: SimpleArrayList add

Created By: Geoffrey Challen

/ Version: 2020.10.0

Let's write the add method for our SimpleArrayList. First, create a SimpleArrayList class with a single public constructor that initializes the list with a passed array of Object references. You should assert that the passed array is not null. Next, implement a getter getValues() which returns the Object array that the list uses to store values. (This is purely for testing.) Also implement size() which returns the size of this list as an int.

Now write the add method, which takes the position to add at as an int as its first parameter and the Object reference to add as its second. add should add the element to the list, increasing the size by one and shifting elements after the add position backward. You should assert that the passed position is valid for this list. But note that you should allow adding a new item to the end of the existing list.

When you are done, here is how your SimpleArrayList class should work:

WorkingPrevious

CS People: Mark Dean

CS People: Mark Dean

Mark Dean was a pioneering Black American computer scientist, engineer, and inventor, who made important contributions to several computing technologies. He developed the ISA bus, an early computer standard allowing interconnection of hardware components. He also worked on computer graphics and the first chip to achieve a 1 GHz clock rate⁽¹⁾.

In recognition of his many accomplishments, Mark Dean was the first African-American to be named an IBM Fellow. Watch the following short video to learn more about Mark Dean:

More Practice

Need more practice? Head over to the practice page.