Studied by 0 people
Looks like no one added any tags here yet for you.
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.
