Lab 3

IntDLists and Debugging

Announcements

  1. Project 0 due next Friday 2/11 - start early!
  2. Lab 3 due Friday 2/4 (Git checkoff on Gradescope)
  3. HW 2 due next Tuesday 2/8
  4. Topical Review Session run by CS 61B tutors, Friday 2-3:30 PM (see Week 3 Announcements)
  5. AIs can answer setup / lab questions, but not project / hw questions. GSIs can answer all questions, but will prioritize lab questions

Review: Linked Lists

A linked list (IntList) is a data structure consisting of individual nodes that each contain two fields:

  • head holds a value
  • tail holds a pointer to the next IntList 
            
              IntList L = IntList.list(4, 1, 8);

L: int head 4 IntList tail int head 1 IntList tail int head 8 IntList tail <IntList obj> <IntList obj> <IntList obj> L: 1 h t 8 h t 4 h t Sho r thand

Doubly Linked Lists: DNode

A doubly linked list is a data structure consisting of individual nodes (DNodes) that each have three fields:

  • head holds a value
  • prev holds a pointer to the previous DNode
  • next holds a pointer to the next DNode

D: 4 DNode next 1 DNode next 8 DNode next <DNode obj> <DNode obj> <DNode obj> DNode prev DNode prev DNode prev int value int value int value D: 4 v n Sho r thand p 1 8 v n p v n p

Doubly Linked Lists: IntDList

IntDList is a class that wraps DNodes. An IntDList has two fields:

  • front holds a pointer to the first DNode
  • back holds a pointer to the last DNode

DL: 4 v n p 1 8 v n p v n p DNode head DNode tail <DIntList obj> DL: 4 v n Sho r thand p 1 8 v n p v n p b f

IntDList: insertFront

            
              IntDList DL = new IntDList(4, 1, 8);
              DL.insertFront(7);

DL: 4 v n p 1 8 v n p v n p b f 7 v n p

Edge case: what if the IntDList was empty before this?

IntDList: deleteFront

            
              IntDList DL = new IntDList(7, 4, 1, 8);
              int x = DL.deleteFront();

DL: 4 v n p 1 8 v n p v n p b f 7 v n p 7 ret: 7 x: No references, so will be automatically “garbage collected”

Edge case: what if we are deleting the only element of the IntDList?