CMSI 2120: Welcome to Week 04
This Week's Agenda
For this week, here's the plan, Fran…
- Homework Assignment #2 checked into your repo by Wednesday at the start of class
- Discuss readings
- Structures made of other structures
- Linked lists
- Abstract Data Types [ADT's]
- Iterators
- Discuss Bloch reading Items 16 & 17 ~ interfaces
- Finish Java Basics
- Introduction to the Java API
- Linked Lists
- Iterators
- More on Linked Lists
Book Discusion: LaFore Chapter Four
Lafore chapter four presents Stacks, Queues, and Priority Queues. We'll look at the first two, and save the last one for later. You should have read all of chapter four last week. Be sure when you do, to look through the code. What do you think of it? [Show chapter four highlights from Lafore]
Book Discusion: Bloch Items 16 & 17
Item 16 consists of advice about Abstract Classes contrasted with Interfaces. We've seen Java interfaces already, noting that they define a Data Type just like a class does, but [most often] only defining the methods that must be defined by any class that implements that interface [type].
An Abstract Class is very similar, with the most significant difference being that these classes are expected to have fully-defined methods, and any class that will use that abstract class must EXTEND the class. You cannot use an Abstract Class by itself, it MUST BE EXTENDED BY A SUBCLASS.
Any class that defines all of the required methods and obeys the general contract is permitted to implement an interface, regardless of where the class resides in the class hierarchy. But because Java permits only single inheritance, this restriction on Abstract Classes limits their use as type definitions.
Item 17 of Bloch also concerns the use of interfaces, but in this case provides a warning. Since a Java
Interface allows you to define fields just like any other user-defined data type, there is a tendency to
define an interface that consists of ONLY constants, defined with static final.
When a class implements an interface, the interface serves as a type that can be used to refer to instances of the class. It is therefore inappropriate to define an interface for any other purpose.
One kind of interface that fails this test is the so-called constant interface. Such an interface contains no methods; it consists solely of static final fields, each exporting a constant. Classes using these constants implement the interface simpy to avoid the need to qualify constant names with a class name. It may seem like a good idea [in fact, Java has several interfaces that break this rule which are considered anomalies], but if in a future release the class is modified so that it no longer needs to use the constants, it still must implement the interface to ensure binary compatibility. If a nonfinal class implements a constant interface, all of its subclasses will have their namespaces polluted by the constants in the interface.
Finish Java Basics
Next up, we'll 'get back to basics': Java Basics
and hopefully will finish up with that [if we haven't already] so we can take a look at the documentation
that Java provides for us with respect to its Application Programming Interface or
API
.
The Java API
There are literally TONS of things in the Java API that are already build for us to use. We've already had a look at some of them in our journey so far:
- String
- Array
- Integer
- Double
- [some others as well]
If you take a look at the Java API
web page, you don't really get much indication of how many thousands of things are included. If you
look back several versions though, to Java 10's page, you have a frames
option which shows you much
more dramatically how many things there are.
[Here is a link
to the frames version of that page.]
We'll explore the API in class.
Linked Lists
Last week we learned about and implemented an ordered list, or sequential list, for which we used
an array as the underlayerment for holding the data. Remember we had to implement a lot of the operations
we needed, so we had to do some heavy lifting
ourselves. However, fear not!
This week we will learn about another type of list, which uses objects instead of an array, and which is ultimately MUCH more flexible than the array-based version: the Linked List.
OK, so what IS a Linked List?
Linked Lists are an implementation of the |
|
|
There are two types of linked lists. The first [and simplest] shown above is the
singly-linked list. In this case, each node has the data storage area, and a
link to the next node in the list. It also has an idea of a A doubly-linked list is similar to the single variety, but it contains TWO
references [pointers,] as shown in the second picture – one to the |
One advantage that either linked list has over an array-based list is that because the data field of the
list node can be of any type, a linked list can store any kind of data type in the same list. You
don't need separate lists for ints, Cars, doubles, Strings, or anything else like we had to do for the
sequential list based on an array [unless you use a different class that supports generics
].
Linked lists are thus called heterogeneous data structures. Here's some code to
illustrate:
public class ListNode {
private Object data;
private ListNode next;
public ListNode( Object o ) {
data = o;
next = null;
}
…
}
Linked lists support all the operations of sequential lists, meaning you will write methods to
insert() [put something into the list where it belongs], remove() [find and
take an item OUT of the list, usually returning its data], findValue() [find and return
a specified data item from the list WITHOUT removing it], append() [add a new item to the
end of the list], and prepend [add a new item to the FRONT of the list]. You can also
sort() the list, but we'll get into that later in the semester.
One thing about linked lists, though, is that because they are not indexed like a sequential
array-based list, you can't access a specific item just by using its index. Instead, you have to go
find it based on its value or some value in the data field, which takes longer. [We'll find out the
difference between constant time
and linear time
in a few weeks.]
So, inserting into a list is easy if you are appending – just like a sequential list, you
find the last item, make a new node with the new data, and point the next field of the
current last node at the new node, which makes it the NEW last node. Since the new node has the value
null as ITS next value, that becomes the tail
. A similar operation can be done to
prepend to the list; it's simple, because you can make a new node, and point its next
reference to the first node in the existing list. However, what if we want to support inserting
something in an existing list that is ordered in some way? That means we need to walk our
way down the list
until we find the proper spot, THEN make the new node, point the new node at the
successive node, and the previous node at the new node. See the diagram below.
One thing that can help with such operations is a thing called an iterator.
Iterators
Iter... what now?!?
An iterator is an object which is defined specifically for efficient access to the
elements of a collection or data structure by maintaining a sliding
reference internally that
refers to [points
to] each of the elements in the collection. What this really means is,
there's another object which is defined on the collection that knows how to efficiently
handle moving back and forth in the collection [read list
]. Typical Iterators support methods
such as hasNext(), remove(), next(), and
forEachRemaining(). You can refer to the
Iterator API page
as well as the
Collection API,
the ListIterator
API, and the
Iterable API web
pages for complete information. Well see how to implement and use them in a bit.
More on Linked Lists
So, now with an iterator
Likewise, the deletion operation becomes simpler with an iterator, too:
|
|
Note that in both these cases, we use the iterator on the list [collection] to scan through the nodes
to find the one in which we are interested. Note also, that if we are inserting or deleting at the
head of the list, there may be some additional record-keeping
operations that need to occur.
Further, if this is a doubly-linked list the previous
field references are updated
as well as the next
field reference; however, since these are usually atomic operations, the
amount of extra time taken is trivial.
OK, so let's build one of these blasted things!
This will be a simple singly-linked list that stores only integer primitives, since we won't need any really sophisticated data for this example. Bear in mind, though, that the principles that we develop can apply to ANY type of data, even Objects. We will build three classes:
- the
IntLinkedListclass itself which contains the list representation - the
private Nodeinner
class to hold the data of the linked list - the
public IntLinkedList.Iteratorinner
class to define the iterator on our linked list
QUICK QUIZ: Why is the Iterator public? Why is the Node private? Why are they not the same visibility?
Here is the beginning code:
public class IntLinkedList {
private class Node {
// we gotta fill this in!
}
public class Iterator {
// this, too....
}
}
Nice of Java to let us do things like this…
OK, so the Node private inner class has two fields in it: the data field, and the
pointer to the next Node object in the list. We'll also need a constructor with which to build
new Node objects. Another nice thing about Java [and many other languages] is that it lets you
define self-referential
classes, meaning we can define a class that has another of itself
as part of its definition. Hey, here comes the code, NOW, in fact!
public class IntLinkedList {
private class Node {
int data; // remember this is an IntLinkedList
Node next; // here's the self-referential part
// constructor
Node( int d ) {
data = d;
next = null;
}
}
public class Iterator {
// this, too....
}
}
Now that we have a Node class defined, we are ready to design the rest of our
IntLinkedList class. First off. we will need a couple of methods to do things like
find the size of the list and add a node to the head of the list. These will be done with the
methods getSize() and prepend(). We will also need an Iterator, which
will be created by the method getIteratorAt(). Let's take the easy stuff first:
public class IntLinkedList {
private Node head;
private int size;
// the constructor
public IntLinkedList() {
head = null;
size = 0;
}
public int getSize() {
return size;
}
private class Node {
int data; // remember this is an IntLinkedList
Node next; // here's the self-referential part
// constructor
Node( int d ) {
data = d;
next = null;
}
}
public class Iterator {
// this, too....
}
}
The prepend() method needs some careful record-keeping
, which requires dealing
with 1) the case when the list is empty; and 2) the case when there is at least one item in the
list. It turns out we can handle both cases with the same code, by setting a third variable to the
current head, no matter what it is [either a Node or null], then making a new Node, setting the head
to that node, and then seting head.next to the node in the third variable we made, like so:
public class IntLinkedList {
private Node head;
private int size;
// the constructor
public IntLinkedList() {
head = null;
size = 0;
}
public int getSize() {
return size;
}
public void prepend( int dataToAdd ) {
Node currentHead = head;
head = new Node( dataToAdd );
head.next = currentHead;
size++;
}
private class Node {
int data; // remember this is an IntLinkedList
Node next; // here's the self-referential part
// constructor
Node( int d ) {
data = d;
next = null;
}
}
public class Iterator {
// this, too....
}
}
Finally, we need to implement our Iterator inner class, which will allow us to visit
the
linked list nodes efficiently. It will also facilitate some list manipulations like insert and
delete. First we need a Node to hold what the Iterator is currently pointing to, then we will
require three methods: public boolean hasNext(), public void next(),
and publid int getCurrentInt()::
public class IntLinkedList {
private Node head;
private int size;
// the constructor
public IntLinkedList() {
head = null;
size = 0;
}
public int getSize() {
return size;
}
public void prepend( int dataToAdd ) {
Node currentHead = head;
head = new Node( dataToAdd );
head.next = currentHead;
size++;
}
private class Node {
int data; // remember this is an IntLinkedList
Node next; // here's the self-referential part
// constructor
Node( int d ) {
data = d;
next = null;
}
}
public class Iterator {
private Node currentNode;
Iterator() {
currentNode = head;
}
public void next() {
if( currentNode == null ) {
return;
} else {
currentNode = currentNode.next;
}
}
public boolean hasNext() {
return ((currentNode != null) && (currentNode.next != null));
}
public int getCurrentInt() {
return currentNode.data;
}
}
}
OK, so what does this Iterator thing actually *DO*??
Well, first, it keeps track of whatever Node in the list we are currently looking at. When the
constructor is called, the currentNode gets initialized to the head of the list. Then
for every call to next() the next node in the list becomes the current node that the
Iterator is pointing at [or looking at]. This gives us an efficient way to move down the list, at
the same time keeping track of what node in the list we are currently looking at [this what all
of that record-keeping
talk was about.] Next, we have a method to see if we have actually
visited ALL of the elements in the list; the hasNext() method checks to see if there
are any nodes AFTER the current node. CAUTION: the way this is structured, you need to remember
the idea of short-circuiting evaluation
!! Finally, the Iterator provides us with a way,
via the getCurrentInt() method, of getting the value of the data [int in this case]
of what is contained in the current Node!
DANG!! …that's so cool!
And here is where we need to observe: this is fine and dandy if we only care about traversing the list from the head to the tail. But what about if we need to back up? [uh-oh....] We'll get to that in a bit.
Gosh, what's left? Well, we need a way for the IntLinkedList class to CREATE its Iterator so it
can be used. Since the Iterator class is internal, and since the Iterator's constructor gets
defined on an IntLinkedList object, we can simply create a method to return a new Iterator object
at the given position. This might be the head, but it might be somewhere further down the list
as well. Be that as it may, this is where we define the final method we haven't addressed yet, the
getIteratorAt() method:
public class IntLinkedList {
private Node head;
private int size;
// the constructor
public IntLinkedList() {
head = null;
size = 0;
}
public int getSize() {
return size;
}
public void prepend( int dataToAdd ) {
Node currentHead = head;
head = new Node( dataToAdd );
head.next = currentHead;
size++;
}
private class Node {
int data; // remember this is an IntLinkedList
Node next; // here's the self-referential part
// constructor
Node( int d ) {
data = d;
next = null;
}
}
public Iterator getIteratorAt( int index ) {
if( (index > size) || (index < 0) ) {
throw new IllegalArgumentException();
}
Iterator it = new Iterator();
while( index > 0 ) {
it.next();
index--;
}
return it;
}
public class Iterator {
private Node currentNode;
Iterator() {
currentNode = head;
}
public void next() {
if( currentNode == null ) {
return;
} else {
currentNode = currentNode.next;
}
}
public boolean hasNext() {
return ((currentNode != null) && (currentNode.next != null));
}
public int getCurrentInt() {
return currentNode.data;
}
}
}
…and that's the name of THAT tune…
Now we need to test things, so here is a test main that will do so.
public class IntLinkedListTester {
public static void main( String[] args ) {
IntLinkedList myList = new IntLinkedList();
myList.prepend( 23 );
myList.prepend( 19 );
myList.prepend( 17 );
myList.prepend( 13 );
myList.prepend( 11 );
myList.prepend( 7 );
myList.prepend( 5 );
myList.prepend( 3 );
myList.prepend( 2 );
IntLinkedList.Iterator myIt = myList.getIteratorAt( 0 );
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 2
myIt.next();
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 3
myIt.next();
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 5
myIt.next();
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 7
myIt = myList.getIteratorAt( 3 );
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 7
myIt.next();
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 11
myIt.next();
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 13
myIt.next();
System.out.println( "Current Node is: " + myIt.getCurrentInt() ); // 17
}
}
In-class Assignment This Week
Your assignment for the week is to implement two methods. One,
insertAt()takes an integer index location and a data value and inserts a node with that data value BEFORE the node at that index. Two,removeAt()takes an integer index location ONLY, and removes the noce at that index.
You will need to error check the parameters, much like is done with the code above.
Remember that the linked list is zero-based, meaning that the head node is element zero of the list, not element 1. Structure your code accordingly.
You will need to use parts [or all] of the IntLinkedList.Iterator to find the correct spot
in the list. Remember that when you give it an index, the iterator will stop when it has found the node
AT THAT INDEX. For this exercise, assume you will always want to insert the new node AFTER the current
node.
For insertion, you will locate the proper place, make a new node, point the new node at the node with the index, then point the node at the index-1 at the new node. For this exercise, don't worry about sorting or ordering. We'll learn that later.
For removal, you will need to use the IntLinkedList.Iterator to find the correct spot in the list, then point the previous node at the next node. The garbage collector will take care of erasing the node you are removing, but you should return it's data value to the caller.
Homework Assignment #3
I know this isn't due for a while, but i wanted to give you a heads-up on the homework assignments that you will be doing this semester. They are all available from the syllabus page, but just to make sure …
Week Four Wrap-up
That's probably enough for the this week. Next week, we'll get into Algorithm Analysis! Oh!