Kotlin

Java

#### Linked Lists :

`45`#### Algorithms and Lists :

`44`#### Lambda Expressions :

`43`#### Anonymous Classes :

`42`#### Practice with Interfaces :

`41`#### Implementing Interfaces :

`40`#### Using Interfaces :

`39`#### Working with Exceptions :

`38`#### Throwing Exceptions :

`37`#### Catching Exceptions :

`36`#### References and Polymorphism :

`35`#### References :

`34`#### Data Modeling 2 :

`33`#### Equality and Object Copying :

`32`#### Polymorphism :

`31`#### Inheritance :

`30`#### Data Modeling 1 :

`29`#### Companion Objects :

`28`#### Encapsulation :

`27`#### Constructors :

`26`#### Objects, Continued :

`25`#### Introduction to Objects :

`24`#### Compilation and Immutability :

`23`#### Practice with Collections :

`22`#### Maps and Sets :

`21`#### Lists and Type Parameters :

`20`#### Imports and Libraries :

`19`#### Multidimensional Arrays :

`18`#### Practice with Strings :

`17`#### null :

`16`#### Algorithms and Strings :

`15`#### Strings :

`14`#### Functions and Algorithms :

`13`#### Practice with Functions :

`12`#### More About Functions :

`11`#### Errors and Debugging :

`10`#### Functions :

`9`#### Practice with Loops and Algorithms :

`8`#### Algorithms I :

`7`#### Loops :

`6`#### Arrays :

`5`#### Compound Conditionals :

`4`#### Conditional Expressions and Statements :

`3`#### Operations on Variables :

`2`#### Variables and Types :

`1`#### Hello, world! :

`0`

interface SimpleList {

fun get(index: Int): Any?

fun set(index: Int, value: Any?)

fun remove(index: Int): Any?

fun add(index: Int, value: Any?)

}

class SimpleArrayList(private var values: Array<Any?>) : SimpleList {

override fun get(index: Int): Any? {

require(index in values.indices)

return values[index]

}

override fun set(index: Int, value: Any?) {

require(index in values.indices)

values[index] = value

}

override fun remove(index: Int): Any? {

TODO("Not implemented!")

}

override fun add(index: Int, value: Any?) {

TODO("Not implemented!")

}

override fun toString() = values.contentToString()

}

val list = SimpleArrayList(arrayOf("you", "are", "not", "alone"))

Welcome back! The rest of the course is incredibly exciting material. We’ll begin building and analyzing new data structures and algorithms, while also introducing new bits of Java syntax along the way.

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

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:

Algorithm analysis: the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.

Big-O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

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

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 Kotlin’s built-in `List`

s, 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

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 an 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

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 non-`null`

able
array of `Any?`

references.
Your array should be private.

Next, implement:

`fun get(Int): Any`

, which takes an`Int`

index and returns the`Any`

at that index`fun set(Int, Any?)`

, which takes an`Int`

index and an`Any`

reference and sets that value at the index to the passed reference.

Both your `get`

and `set`

method should require 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 `require`

).

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

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
non-null array of `Any?`

references.
Call the array `values`

and provide a public getter but not a public setter.
(This setter is purely for testing.)
Also provide a method `size()`

with that returns the current size of the list.

Now write the `add`

method, which takes the position to add at as an `Int`

as its first parameter and the `Any?`

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:

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^{(1)}.

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:

Need more practice? Head over to the practice page.