Joining nodes together, we can create a linked list
Each node points to the next, except the last, which has a null reference since there is no next node
Version 3.21
Handouts: probably none for this material (OLD: the List.java source files.)
Part 1
Part 2
Part 3
Part 4
ArrayList (ch. 7)Collections are objects that store other objects. They typically have services to insert, remove, and update elements in their storage.
The java.util.ArrayList class (chapter 7) is an example.
Look at java.util.ArrayList API.
ArrayList xs = new ArrayList();
xs.isEmpty();
xs.add(new Object());
xs.add("bananas");
xs.size();
xs.contains("bananas");
xs.indexOf("bananas");
xs.get(0);
xs.set(0, "apples");
xs.remove(0);List interfaceArrayList and LinkedList classesArrayList deals with this by making a new, bigger array and copying the old data into the new when needed
Dynamic structures are able to change their size and structure as needed.
See Node class, p. 619
class Node
{
Object info;
Node next;
}A recursive data type, with a reference to another Node.
Joining nodes together, we can create a linked list
Each node points to the next, except the last, which has a null reference since there is no next node
The MagazineList class defines a constructor, add method, and toString method; it uses an inner class, MagazineNode.
Carefully look at the code in the add method. How does it add the first element? How does it add later elements? What does the loop do? What is always true of left hand side (LHS) in statements of the form 'LHS = node'? (LHS == null)
How does toString work?
In MagazineNode, the instance variables are 'public' — this is okay, since it is a private inner class, and it will simplify the code that uses MagazineNode.
Other operations that could be defined include:
Inserting a node at a designated point in the list (instead of only at the rear) — Fig. 13.2
Deleting a specified element from the list — Fig. 13.3
These are like lists, but with restrictions on where items can be inserted and removed.
Show the contents of the queue, initially empty:
enqueue("A")
enqueue("B")
dequeue()
enqueue("C")
dequeue()
enqueue("D")
enqueue("E")
dequeue()
dequeue()Lewis and Loftus state there is no Java class implementing a queue, but that is not so. The java.util package documentation shows a Queue interface implemented by the LinkedList class. However, the queue operations have non-standard names: enqueue → offer, dequeue → remove.
In method calls, each method's local data (parameters and other local variables) are placed in an activation frame or call frame or environment and placed onto the call stack, then popped when the method returns. The call frame also includes the return address (of the next instruction in the caller).
Iterative solutions designed to replace recursive solutions typically must employ their own stack to "simulate" the recursive method calls. Thus they avoid some, but not all, of the overhead of a method call.
Show the contents of the stack, initially empty:
push("A")
push("B")
pop()
push("C")
pop()
push("D")
push("E")
pop()
pop()Listing 13.4 Decode
Uses a stack to decode a "secret message" (a sequence of words, each word written backwards). To translate a word, the program pushes its characters onto a stack until reaching a space or end of line. Then it pops the characters and outputs them in reverse order. This process is repeated for each word, stopping at the end of line.
"Non-linear" means non-sequential.
A tree consists of a root node and a set of subtrees
Subtrees are disjoint (no node belongs to more than one)
Example:
Terminology: root, parent, child, leaf (node without children), internal node (non-leaf)
Applications: hierarchical data, efficient storage structures
Trees represent hierarchical information, such as organization charts, family trees, and inheritance structures in OOP. In addition, they provide efficient structures for storage and retrieval of information.
Many of these storage structures are based on binary trees, in which each node can have at most two children. More precisely, a binary tree is either empty, or consists of a root node, a left subtree, and a right subtree, where the two non-overlapping subtrees are binary trees. So a binary tree is not exactly a tree, because it can be empty, but a tree cannot; and because left is distinguished from right, but in a tree it is not. Nevertheless we loosely refer to binary trees as "trees."
Example:
Applications: connected sets of entities, such as a network of roads, a subway, cities connected by airline flights, computer networks (the Internet!); social networks
Besides geographical data, graphs are good at representing social networks:
Exercises: 13.10–13.11
You know about these:
LinkedList<Book> books = new LinkedList<Book>();
LinkedList stuff = new LinkedList();The API documentation will show the class as LinkedList<E>, where <E> is the element tye parameter.
The default element type is Object.
Advantages:
Avoids errors of inserting wrong type object in a collection. E.g., a Magazine into a list of Books.
stuff.add(new Magazine()); // ok
books.add(new Magazine()); // compile-time errorElements removed from the collection are known to be of the declared element type (e.g., Book), where otherwise a type cast would be required.
Book book1 = books.get(0); // ok
Book book2 = stuff.get(0); // compile-time error
Book book2 = (Book) (stuff.get(0)); // maybe okDisadvantages:
More complex (sometimes).
LinkedList<Book> books = new LinkedList<Book>();
LinkedList stuff = new LinkedList();Static fields (class variables) can't be generically typed (e.g., a generic empty list class variable).
These topics are covered in C243 Introduction to Data Structures