Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Recursion : 47

    • Lists Review and Performance : 46

    • 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

    Lists Review and Performance

    interface SimpleList {
    fun get(index: Int): Any?
    fun set(index: Int, value: Any?)
    fun remove(index: Int): Any?
    fun add(index: Int, value: Any?)
    fun size(): Int
    }
    class SimpleLinkedList(values: Array<Any?> = arrayOf()) : SimpleList {
    private inner class Item(var value: Any?, var next: Item?)
    private var start: Item? = null
    private var size = 0
    init {
    for (i in values.indices.reversed()) {
    add(0, values[i])

    Welcome back! In this lesson we’re going to wrap up our discussion of lists. First, we’ll make some forward progress on our linked list implementation. Then, we’ll compare and contrast the two performance of our two approaches.

    Warm Up Debugging Challenge
    Warm Up Debugging Challenge

    But! Let’s warm up with another debugging challenge!

    Linked List Remove
    Linked List Remove

    At this point we can initialize our linked lists and get and set items. But what about add and remove? It’s not a list yet!

    Both add and remove require adjusting the linkage to either insert or delete elements. This is tricky! Let’s start with remove. First, let’s look at what needs to happen using a diagram.

    OK, now let’s take a stab at this in code!

    // SimpleLinkedList remove

    Linked List Add
    Linked List Add

    What about add? We’ll leave that for you to work on… But, to help you get started, let’s diagram it first:

    ArrayList v. LinkedList Performance
    ArrayList v. LinkedList Performance

    Let’s examine the performance tradeoffs of our ArrayList versus our LinkedList.

    Now, you might be wondering why anyone would use a linked list, ever! However, there are applications that only ever modify the ends of the list!

    For example, consider a help queue. Requests are added at one end and removed from the other. So we are only ever modifying the front or the end of the list.

    Modifying the front of a linked list is O(1). But what about the end? Could we make that O(1) too? Sure! Let’s see how.

    // Optimizing addToEnd

    Note that this approach allows us to implement adding to the end of a linked list in O(1). What about if we also wanted to support efficient removal from the end? We’d need to make one additional change.

    Homework: SimpleLinkedList add

    Created By: Geoffrey Challen
    / Version: 2020.10.0

    Starting with the SimpleLinkedList class below, complete the code for add. You'll want review the rest of the code to understand how this list implementation works and how to walk a linked list and manipulate the references properly.

    add 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 require 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 SimpleLinkedList class should work:

    CS People: Cathy O’Neil
    CS People: Cathy O’Neil

    Increasingly, important decisions about our lives are being made by algorithms. Whether you get a job. Who you meet, get to know, and fall in love with. When you’re in trouble, whether you get extra help or are left to struggle. If you can get a loan to buy that home, or need to live somewhere else.

    Cathy O’Neil has played an important role drawing attention to the ways in which algorithmic decision making is shaping and misshaping our lives. Her foundational book “Weapons of Math Destruction” explores how this topic intersects with multiple aspects of our lives. In the video below, she discusses what we should expect from the increasingly mysteriously algorithms that seem destined to continue to shape our lives:

    More Practice

    Need more practice? Head over to the practice page.