Kurage Notes

Appearance

DLLists ​

SLLists fail when trying to delete the last node in O(1).

Looking Back ​

Add a previous pointer to each IntNode:

java
public class IntNode {
  public IntNode prev;
  public int item;
  public IntNode next;
}

dllist_basic_size_0.pngdllist_basic_size_2.png

Sentinel Update ​

Linear ​

dllist_double_sentinel_size_0.pngdllist_double_sentinel_size_2.png

Circular ​

dllist_circular_sentinel_size_0.png

dllist_circular_sentinel_size_2.png

Generic Lists ​

Generic data structures allow users to create structures that hold any type.

To declare a class of generic type:

java
public class DLList<Type> {
  private IntNode sentinel;
  private int size;

  public class IntNode {
    public IntNode prev;
    public Type item; // Notice the type of item
    public IntNode next;
    ...
  }
  ...
}

To use a generic type:

java
DLList<String> d2 = new DLList<>("hello");
d2.addLast("world");

DLList<Integer> d1 = new DLList<Integer>(5); // This is also OK
d1.insertFront(10);

Summary:

  • In the .java file implementing a data structure, specify your generic type name only once at the very top of the file after the class name.
  • In other .java files, which use your data structure, specify the specific desired type during declaration, and use the empty diamond operator during instantiation.
  • If you need to instantiate a generic over a primitive type, use Integer, Double, Character, Boolean, Long, Short, Byte, or Float instead of their primitive equivalents.