61b 一拖再拖，课内学得稀烂。把 61b 的仓库 public 了，搬了一堆屎到博客上，希望得到存在或不存在的人的监督🙏✊ 又听到 Josh Hug 的声音，感觉好幸福。

Lists in Java#

date: 2025-8-20 23:35:07

public class SLList {
    private static class Int Node {
        public int item;
        public IntNode next;
        
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }
    
    private IntNode first;
    
    public SLList(int x) {
        first = new IntNode(x, null);
    }
    
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
    public int getFirst() {
        return first.item;
    }
    
    // Why is it `static`?
    private static int size(IntNode p) {
        if (p.next == null) {
            return 1;
        }
        return 1 + size(p.netx);
    }
    public int size() {
        return size(first);
    }
}

更强的封装性，更面向对象。留意 .size() 的实现。

The meaning of a sentinel#

统一的逻辑，严谨的结构（空表）

addLast is slow#

需要将倒数第二个节点的 next 置空，要遍历链表。

If we just maintain a lastNode, the moveLast would be slow#

多维护一个 lastNode 也没有用（思考）。

So the solution is… Doubly Linked List!#

因此想到双向链表。

Two sentinel? Can be more perfect. One Sentinel!#

public class DLList<T> {
	private class Node {
		public T item;
		public Node next;
        public Node prev;
		
		public Node(T i, Node n, Node p) {
			item = i;
			next = n;	
			prev = p;
		}	
	}
	
	private Node sentinel;
	private int size;
	
	public DLList() {
		size = 0;
		sentinel = new Node(null, null, null);\
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
	}
	
    public void addFirst(T x) {
        Node newNode = new Node(x, sentinel.next, sentinel);
        sentinel.next.prev = newNode;
        sentinel.next = newNode;
        ++size;
    }
    
    public void removeFirst() {
        if (size == 0) {
            throw new IllegalStateException("Cannot remove from an empty list");
        }
        sentinel.next.next.prev = sentinel;
        sentinel.next = sentinel.next.next;
        --size;
    }
	
    public T getFirst() {
        if (size == 0) {
            throw new IllegalStateException("Cannot get first element of an empty list");
        }
        return sentinel.next.item;
    }
	
    public void addLast(T x) {
        Node newNode = new Node(x, sentinel, sentinel.prev);
        sentinel.prev.next = newNode;
        sentinel.prev = newNode;
        ++size;
    }
    
    public void removeLast() {
        if (size == 0) {
            throw new IllegalStateException("Cannot remove from an empty list");
        }
        sentinel.prev.prev.next = sentinel;
        sentinel.prev = sentinel.prev.prev;
        --size;
    }
    
    public T getLast() {
        if (size == 0) {
            throw new IllegalStateException("Cannot get last element of an empty list");
        }
        return sentinel.prev.item;
    }
    
	public int size() { return size; }
}

Lecture8-10#

date: 2025-9-26 9:40:27

接口继承和实现继承#

Java 中, 继承分为接口继承 implements 和实现继承 entends.

前者提供一个接口 interface , 包含所有子类应实现的功能, 但没有具体实现, 子类用 implements 关键字声明.

public interface List61B<Item> {
    public void addFirst(Item x);
    public void add Last(Item y);
    public Item getFirst();
    public Item getLast();
    public Item removeLast();
    public Item get(int i);
    public void insert(Item x, int position);
    public int size();
}

public class AList<Item> implements List61B<Item> {
    @Override
    public void addFirst(Item x) { ... }
    
    ...
}

后者的使用情景为子类需要重写父类的某些方法, 对于这些方法, 加入 default 关键字声明, 子类用 extends 关键字声明.

default public void print() { // 需要重写的方法
    for (int i = 0; i < size(); ++i) {
        System.out.print(get(i) + " ");
    }
    System.out.println();
}

@Override
public void print() {
    for (Node p = sentinel.next; p != null; p = p.next) {
        System.out.print(p.item + " ");
    }
}

使用 extends 关键字, 子类继承父类构造和析构函数外的所有成员(虽然不继承, 但在子类对象构造时也会被显示/隐式调用), 并且 private variables 不能被子类直接访问.

静态类型和动态类型#

省流: 编译检查看静态类型, 为了通过编译检查会用到强制类型转换; 虚表查找(…就是那个意思)看动态类型

高阶函数和子类多态性#

Java 中高阶函数的实现.

public interface IntUnaryFunction {
    int apply(int x);
}

public TenX implements IntUnaryFunction {
    /* Returns ten times the argument. */
    @Override
    public int apply(int x) {
        return 10 * x;
    }
}

public static int do_twice(IntUnaryFunction f, int x) {
    return f.apply(f.apply(x));
}

比较器#

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }
}

上述代码通过 Comparable 实现了运算符重载.

需要实现多种不同的比大小方法时, 用到另一个类 Comparator

import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }
    
    private static class NameComparator implements Comparator<Dog> {
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name);
        }
    }
    
    public static Comparator<Dog> getNameComparator() {
        return new NameComparator();
    }
}

Eceptions and Literators#

date: 2025-9-26 11:07:16

本节实现数据结构 ArraySet

Exceptions#

throw new ExceptionObject(parameter1, ...)

/* Associates pthe specified value with the specified key in this map.
   Throws an IllegalArgumentException if the key is null. */
public void add(T x) {
    if (x == null) {
        throw new IllegalArgumentException("can't add null");
    }
    if (contains(x)) {
        return;
    }
    items[size] = x;
    size += 1;
}

Iterators and Iterables#

public interface Iterable<T> {
    Iterator<T> iterator();
}

public interface Iterator<T> {
    boolean hasNext();
    T next();
}

import java.util.Iterator:

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size; // the next item to be added will be at position `size`
    
    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }
    
    /* Returns true if this map contains a mapping for specified key. */
    public boolean contains(T x) {
        for (int i = 0; i < size; ++i) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }
    
    /* Associates the specified value with the specified key in this map.
       Throws an IllegalArgumentException if the key is null. */
    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("can't add null");
        }
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size += 1;
    }
    
    /* Returns the number of key-value mappings in this map */
    public int size() {
        return size;
    }
    
    /* Returns an iterator into ME */
    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }
    
    private class ArraySetIterator implements Iterator<T> {
        private int wizPos;
        
        public ArraySetIterator() {
            wizPos = 0;
        }
        
        public boolean hasNext() {
            return wizPos < size;
        }
        
        public T next() {
            T returnItem = items[wizPos];
            wizPos += 1;
            return returnItem;
        }
    }
    
    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);

        // iteration
        for (int i : aset) {
            System.out.println(i);
        }
}
    }

JUnit Check#

date: 2025-9-26 14:17:05

public class MaxArrayDequeTest {
    @Test
    /** Adds a few things to the list, checking isEmpty() and size() are correct,
     * finally printing the results.
     *
     */
    public void addIsEmptySizeTest() {
        Comparator<String> c = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        };
       MaxArrayDeque<String> mad1 = new MaxArrayDeque<>(c);

       assertTrue("A newly initialized MADeque should be empty", mad1.isEmpty());
       mad1.addFirst("front");

       assertEquals(1, mad1.size());
       assertFalse("mad1 should now contain 1 item", mad1.isEmpty());

       mad1.addLast("middle");
       assertEquals(2, mad1.size());

       mad1.addLast("back");
       assertEquals(3, mad1.size());

       System.out.println("Printing out deque: ");
       mad1.printDeque();
    }

    @Test
    public void addRemoveTest() {
        Comparator<Integer> c = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        };
        MaxArrayDeque<Integer> mad1 = new MaxArrayDeque<>(c);
        assertTrue("mad1 should be empty upon initialization", mad1.isEmpty());

        mad1.addFirst(1);
        assertFalse("mad1 should contain 1 item", mad1.isEmpty());

        mad1.removeFirst();
        assertTrue("mad1 should be empty after removal", mad1.isEmpty());
    }

    @Test
    public void removeEmptyTest() {
        Comparator<Integer> c = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        };
        MaxArrayDeque<Integer> mad1 = new MaxArrayDeque<>(c);
        mad1.addFirst(1);

        mad1.removeLast();
        mad1.removeFirst();
        mad1.removeLast();
        mad1.removeFirst();

        int size = mad1.size();
        String errorMsg = "  Bad size returned when removing from empty deque.\n";
        errorMsg += "  student size() returned " + size + "\n";
        errorMsg += "  actual size() returned 0\n";

        assertEquals(errorMsg, 0, size);
    }

    @Test
    public void multipleParamTest() {
        MaxArrayDeque<String>  mad1 = new MaxArrayDeque<String>();
        MaxArrayDeque<Double>  mad2 = new MaxArrayDeque<Double>();
        MaxArrayDeque<Boolean> mad3 = new MaxArrayDeque<Boolean>();

        mad1.addFirst("string");
        mad2.addFirst(3.14159);
        mad3.addFirst(true);

        String s = mad1.removeFirst();
        double d = mad2.removeFirst();
        boolean b = mad3.removeFirst();
    }

    @Test
    public void bigMADequeTest() {
        MaxArrayDeque<Integer> mad1 = new MaxArrayDeque<>();
        for (int i = 0; i < 1000000; i++) {
            mad1.addLast(i);
        }

        for (double i = 0; i < 500000; i++) {
            assertEquals("Should have the same value", i, (double) mad1.removeFirst(), 0.0);
        }

        for (double i = 999999; i > 500000; i--) {
            assertEquals("Should have the same value", i, (double) mad1.removeLast(), 0.0);
        }
    }

    @Test
    public void maxTest() {
        Comparator<Integer> c = new  Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        };
        MaxArrayDeque<Integer> mad1 =  new MaxArrayDeque<>(c);

        mad1.addFirst(1);
        mad1.addLast(29);
        mad1.addLast(18);
        mad1.addLast(2912);
        mad1.addLast(292);
        mad1.addFirst(2912);

        assertEquals((Integer) 2912, mad1.max());
    }

}

toString and equals#

date: 2025-10-3 15:06:53

toString#

@Override
publiic String toString() {
    String returnString = new String();
    for (int i = 0; i < size - 1; ++i) {
        returnString += items[i.toString();
        returnString += ", ";
    }
    returnString += items[size - 1].toString;
    returnString += ", ";
	return returnString;
}

利用迭代拼接字符串 String 效率特别低(每次迭代会复制一个字符串), 复杂度为 O(n²), 故改用 StringBuilder

@Override
public String toString() {
    StringBuilder returnSB = new StringBuilder("{");
    for (int i = 0; i < size - 1; ++i) {
        returnSB.append(items[i].toString());
        returnSB.append(", ");
    }
    returnSB.append(items[size - 1]);
    returnSB.append("}");
    return returnSB.toString();
}

Shorter toString:

@Override
public String toString() {
    List<String> listOfItems = new ArrayList<>();
    for (T x : this) {
        listOfItems.add(x.toString());
    }
    return "{" + String.join(", ", listOfItems) + "}";
}

这样的实现更简洁, 但还是效率低下, 如果不需要频繁调用 toString, 这样写更好看.

equals#

@Override
public boolean equals(Object o) { // the parameter must be Object, not ArraySet or something, because this is a overriding method
    if (o instanceof Dog uddaDog) {
        return this.size == uddaDog.size;
    }
    return false;
}

instanceof:

checks to see if o’s dynamic type is Dog
implicitly casts o as a Dog into a variable called uddaDog

@Override
public boolean equals(Object o) {
    if (this == o) {
        return true; 
    } 
    if (o instanceof ArraySet oas) {
        if (this.size != oas.size) {
            return false;
        }
        for (T x : this) {
            if (!oas.contains(x)) {
                return false;
            }
        }
        return true;
    }
    return false;
}

.of#

var arg (variable number of arguments)

new pattern of generic (of is a static method which can not access generic param T)

public static <Glerp> ArraySet<Glerp> of(Glerp... stuff) { // Glerp has nothing to do with T, it's just the declaration that this is a method which is generic
    ArraySet<Glerp> returnSet = new ArraySet<Glerp>();
    for (Glerp x : stuff) {
        returnSet.add(x);
    }
    return returnSet;
}

腰斩了，对不起我曾经成为算法高手的理想

CS61B Lecture