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.