Notes by Lex Toumbourou

Project Overview

1. Create your own LinkedList.
2. Create a Markov Text Generator.

Abstraction, Interfaces and Linked Lists

• Data abstraction
  • fundamental concept of programming
  • Hide implementation details for the user.
• Abstract Data Type (ADT)
  • No implementation.
  • Just defines the methods and properties of a class; a promise.
• Data Structure
  • Actual implementation.
  • Eg ArrayList
• In the real world: data abstraction

Core: Linked Lists vs Arrays

• ADT: specifies behaviour, not implementation.
• ArrayList implements the List interface using an array.
  • Provides access to elements in constant time.
  • O(n) to add elements.
• LinkedList
  • Doubly Linked List usually stores a pointer to the head and tail.
  • Each node has a next and prev references.
  • Each node in the list is a ListNode element.
  • Alternate implementation: Sentinal nodes.
  • Have dummy nodes at start and end of list, which are buffers to keep you running off start and end of the list.
  • O(1) insertion time.
• Core: Generics and Exceptions

• Implementation of ListNode:

    class ListNode<E> {  // not a public class.
        ListNode<E> next;
        ListNode<E> previ;
        E data;  // E == parameterized types: makes ListNode "generic", replace with type when initing it.
  

• E is a paramterized type.

• Replace with an actual type then refer to type as E throughout class.
  • Refered to a "generics"
• Handling bad input
• Since we don't know about type, can't return -1 on bad input.
• Returning null is a bit yick.
• Raise an exception: throw new NullPointerException("Cannot store null pointers, yo")
• If exception is a "checked exception" then we will to declare in method header that it throws the exception.
• Core: Java Code for a Linked List
  • List node defined as follows:

class ListNode<E> {
    ListNode<E> next; // considered a "recursive class" - uses its own definition in it.
    ListNode<E> prev;
    E data;

      public ListNode(E theData)
      {
        this.data = theData;
      }
}

• Linked list class as follows:

public class MyLinkedList<E>
{
    private ListNode<E> head;
    private ListNode<E> tail;
    private int size;

    public MyLinkedList() {
        size = 0;
        head = new ListNode<E>(null);
        tail = new ListNode<E>(null);
        head.next = tail;
        tail.prev = head;
    }
}

Testing and Correctness

• Core: Testing and Confidence
  • Risk assessment of problem domain should be considered when decided on degrees of confidence for code (self-driving car vs blog).
• Core: Testing Practises
  • Standard Cycle: write code, write tests and test code.
• Test-Driven Development: write tests, write code and test code.
• Testing types: black box testing and clear box testing.
  • Black box
    • more representative of how users use the code.
    • easier to write by someone unfamiliar with the implementation.

Core: Markov Text Generation

• High-level idea: walk through text saving a sort of word count of the word at the next position for each word.
• Store in a map with word as the key and next word count as a list.
• Generate text by finding a next word randomly from the word count list for some word count.