2.1 Mystery of the Walrus

Study Guide Link: https://sp21.datastructur.es/materials/lectures/lec3/lec3.html

• Recall Question
• Answer:

Notes:

1. The Golden Rule of Equals (GRoE):

• b = a copies the bits from a into b

  

• passing parameters copies the bits (pass by value)

  

  • Pass by value means the actual value is passed on. Pass by reference means a number (called an address) is passed on which defines where the value is stored.

  2. Recursion & Iteration

  

  Question: Get number of the item in L

  • IntLists are lists of integers that can change size (unlike arrays), and store an arbitrarily large number of integers.

  public class IntList{
      public int first;
      public IntList rest;
      
      public IntList(int f, IntList r){
          first = f;
          rest = r;
      }
  
      /** add a method size to the IntList class so that if you call 
       * L.size(), you get back the number of items in L */
  
      /** Return the size of the list using... recursion! */
      // IntList Size (best solution)
      public int size(){
          if(rest == null){
              return 1;   //base case
          }
          return 1 + this.rest.size();
      }
  
      /** No recursion or iteration */
      public int iterativeSize(){
          IntList p = this;
          int totalSize = 0;
          while (p != null) {
              totalSize += 1;
              p = p.rest;
          }
          return totalSize;
      }
  
      public static void main(String[] args){
          IntList L = new IntList(15, null); 
          L = new IntList(10, L);
          L = new IntList(5, L);
  
          // System.out.println(L.size());
          System.out.println(L.size());
      }
  }
  

  can't override "this" because it is a java keyword and it always refers to the current object.

3. Challenge Question:

Write a method int get(int i) that returns the ith item in the list.

    /** Write a method get(int i) that returns the ith item of the list. 
     * For example, if L is 5 -> 10 -> 15, then L.get(0) should return 5, 
     * L.get(1) should return 10, and L.get(2) should return 15. */
    public int get(int i){
        if (i == 0){
            return first;
        }
        return rest.get(i - 1);
    }    

2.2 The SLList (Single Linked List) 本质：Add middleman

Study Guide Link: https://sp21.datastructur.es/materials/lectures/lec4/lec4

• Recall Question

Notes:

1. Caching:

Saving important data to speed up retrieval. (eg. We add a size variable to the SLList class that tracks the current size, yielding the code below.)

public class SLList {
    ... /* IntNode declaration omitted. */
    private IntNode first;
    private int size;    //create a size variable

    public SLList(int x) {
        first = new IntNode(x, null);
        size = 1;
    }

    public void addFirst(int x) {
        first = new IntNode(x, first);
        size += 1;  // increment for size
    }

    public int size() {
        return size;
    }
    ...
}