Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • 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

    • Static : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Type Inference : 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

    Linked Lists

    public interface SimpleList {
    Object get(int index);
    void set(int index, Object value);
    Object remove(int index);
    void add(int index, Object value);
    int size();
    }
    public class SimpleLinkedList implements SimpleList {
    private class Item {
    private Object value;
    private Item next;
    Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
    }
    }

    Welcome back! Let’s continue discussing lists, but explore a new approach: linked lists. No arrays required! Let’s get to it…

    Linked Lists
    Linked Lists

    So far we’ve seen how to implement a list using an array to store the references. However, the array was also maintaining the order!

    But this is not the only way! Let’s look at another approach that uses references to link items together into a chain. First we’ll explore it on paper, and then start our implementation, and check out a few diagrams along the way.

    Linked List Constructor
    Linked List Constructor

    Next, let’s look at how to create our linked list constructor, and a simple version of add that only supports adding items to the front of the list.

    // SimpleLinkedList constructor and add to front

    Confused? OK! Let’s look at the same code but using a diagram!

    Inner Classes
    Inner Classes

    We promised that as we continue building data structures and implementing and analyzing algorithms, we’d also meet some new Java syntax along the way. You may have noticed our implementation uses something called an inner (or nested) class. Let’s examine that more carefully!

    // Inner Classes

    SimpleLinkedList get
    SimpleLinkedList get

    Next let’s go on and implement get. But first, we need to think about how we are actually going to walk the list! Let’s see that in a diagram first:

    And now, we’ll complete our implementation of get and consider its performance.

    // SimpleLinkedList get

    But what about add and remove? We’ll get there! Next time…

    Solve: SimpleLinkedList set

    Created By: Geoffrey Challen
    / Version: 2020.10.0

    Let's implement a list using a different strategy. Instead of an internal array, we'll link items together into a chain using references. Our list class will only maintain a reference to the start of the list and walk the list to perform list operations. This approach will have interesting tradeoffs compared to our implementation that used arrays.

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

    public class SimpleLinkedList {
    private class Item {
    private Object value;
    private Item next;
    Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
    }
    }
    private Item start;
    private int size;
    public SimpleLinkedList(Object[] values) {
    assert values != null;
    for (int i = values.length - 1; i >= 0; i--) {
    add(0, values[i]);
    }
    }
    public int size() {
    return size;
    }

    More Practice

    Need more practice? Head over to the practice page.