CSI 2310 Test 2

addAll

Use insatnceof

When typing IntNode

ex.) answer.head = IntNode.listCopy(head);

IntArrayBag union

Uses instanceof

IntLinkedBag union

Does not use instanceof

clone method

Create local variable

Where cursor = head in for loop

listSearch, listLength

Where cursor and i is used in for loop

listPosition

ADT

Encapsulates data with a set of operations which form the interface

of the type. An ADT can be implemented as a Java class.

Collection

Object that contains a collection of elements that may be objects as well. Such object is called a container.

Ex.) bags, sets, sequences

Collection ADT called IntBag

Specification

public interface IntBag

{ void add(int element);

boolean remove (int target);

int size();

int countOccurrences(int target);

void addAll(IntBag addend);

IntBag union(IntBag addend); // different from book;}

Invariant

A class is a property of objects of

the class. It must hold of the state of the object before and after each public method. Each public method (except constructors) can assume the invariant holds before execution and must make sure the invariant holds after execution.

Linked List

Dynamic dynamic sequential data

structure that is comprised of nodes that have data and link to next node. Used to implement collections or list of elements in some type of order.

IntNode class

private int data;

private IntNode link;

head

Not a node, a reference to a node. Store as null.

Insert Node at front

public static IntNode insertAtFront(IntNode head, int entry)

return new IntNode(entry, head);

Remove head Node

head = head.getLink(); Now goes into garbage collection.

Insert Node at front

head = IntNode.insertAtHead(head, entry);

New Node not at front

previous.link = IntNode.insertAtHead(previous.link, entry);

Add Node after

public void addNodeAfter(int item) {

link = new IntNode(item, link); }

Remove Node after

public void removeNodeAfter( ) {

link = link.link; }

Computation on entire list

Length, copying, locating

Traversal

Visiting a node in a list and performing an action on it.

for (cursor = head; cursor!=null; cursor=cursor.link) {

do computation with the node referred to by cursor }

Sequence class on LL

public class DoubleLinkedSeq implements DoubleSeq {

private DoubleNode head;

private int manyItems;

private DoubleNode current; }

add element to bag

1.) Create new node

2.) Increment total elements

addAll elements from addend

1.) Create node array

2.) instance of

3.) new must be > 0

4.) create new node w/ tail

5.) link to head

6.) set head to head of copy

7.) add to manyNodes

8.) else throw exception

Node

Places each element together with links.