Transcript Hashing in Computer Science

Abstract Data Types
Linked Lists
Abstract Data Type(ADT)




4
ADT--a specification, in abstract terms
only, without reference to programming
language or machine dependent
terminology.
ADT--contains two parts:
description of the data together with any
internal structure that thedata has
description of the valid operations that
can be performed on this data
ADT


2
Because abstract--can not be used
directly in a program, but can be
implemented into concrete instances,
which can be used in programs
To insure conditions that will lead to
successful application, ADT should
make use of the exception mechanism
Ideal properties for ADT List
structure




4
should occupy exactly as much memory
as necessary
should be able to grow at any time, and
accomplish growth quickly
should be able to shrink at any time and
return unused memory to the JVM
should be ordered so that every
element has a well-defined location.
ADT List--definition


2
List--an ordered structure of elements
such that it is either empty or has a
unique first element, every element
except for the last one has one
immediate successor, and the last
element is that one without a successor.
One element in a non-empty List is
always designated as the current
element.
ADT List--operations




4
Create an empty List
Designate the first element of a nonempty List as the current element
Move the current element to the
successor of the current element in a
non-empty List, unless the current
element is last
Insert an element into the List
ADT List--operations (cont.)





Retrieve the element designated as
current, unless the List is empty
Remove the element designated as
current, unless the List is empty
Replace the element designated as
current, by another element unless the
List is empty
Check if the List is empty
Check if current element is last
5
List class--definition



3
A List is either an empty or sequential
structure of elements such that one
element is always designated as current
List supports the following methods:
constructor: creates an empty List
containing no elements
public void first(): make first element
current, can only be used on a
nonempty List
List class--definition (cont.)



3
Public void next(): makes the element
after the current one the (new) current
one
public void insert (Object o): inserts an
element, or object, into the List
public Object retrieve():returns current
element , can only be used on a
nonempty List
List class--definition (cont.)




4
public void remove (): deletes current
element from the List, only on nonempty
public void replace (Object o): replaces
current element by another one, can
only be used on a nonempty List
public boolean isEmpty():true if List
empty, false otherwise
public boolean isLast():true if element
last, false otherwise
Node



3
A utility class used to create lists and
other list-like sequential structures
Need inside a List--a smart obect that
can store data and knows who its
immediate successor, if any, is
Hence, Node has two pieces: one piece
to store a Java object, and another
piece to store a reference to another
Node
Node (cont.)



3
A node can return and replace the
Object stored
A node can contain a reference to
another node called the successor
Implementation: a node can contain two
non-private fields, one called data that
stores the actual object and another
called next that stores either a reference
to another node or “null”.
Node


GO TO node code.
Draw on board
2
Circular node







(put picture on board)
Node A = new Node();
Node B = new Node();
Node C = new Node();
A.next=B;
B.next=C;
C.next=A;