Week 4

Return Quizzes

Collect Homework 2.

·        Discuss it.

·        Have someone show working version.

Quiz

·        Using HW2

Chapter 4 – Linked lists

·        What is a linked list?  Draw one.

·        found in real world, similar usage to arrays

.      discuss ADTs

        .   example of bags using arrays and linked lists

·        Show in Java

public class Node

{

      private int data;

      private Node next;     // in book called “link”

…

}

·        Head and tail nodes, references, why you need them

Node head;

Node tail;

·        The null reference

·        Manipulating nodes

·        constructor (may or may not create a node)

·        getting and setting data and link of a node

·        public vs. private members – semi-religious

·        adding a node at the head

newnode.next = head;

head = newnode;

·        removing a node at the head

head = head.next

·        discuss garbage collection from the heap from objects with no references

·        adding a node not at the head (add node after)

newnode.next = current.next

current.next = newnode;

·        removing a node not at the head

next = next.next;

·        “traversing” a list

for(cursor = head; cursor != null; cursor=cursor.next)

            …

or

cursor = head;

while (cursor != null)

{

            …

            cursor = cursor.next;

}

·        searching for an item in a list

·        traverse the list, test for value, return cursor or null

·        copying a list

·        reversing a list

Pick the data structure that matches the environment being modeled!

·        images import java.awt.Image;

import java.awt.Grapics;

private Image im;

public void init()

{

            URL codebase = getCodeBase();

im = getImage(<URL>, “<graphic>.gif);  // can URL be a local

       //  file? and string?

                        }

public void paint(Graphics g)

{

            g.drawImage(im, 0, 0);

}

Homework

Project 3