CS61B, Lecture #9, 7/3/00 Michael Brudno Lists ----- We have already seen in lecture the basic List class: class List { public Object head; public List tail; public List(Object o, List l) { head=o; tail = l; } public List(Object o) { this(o,null); } } This class represents a linked list -- a collection of objects connected by pointers, and has the familiar box & pointer representation that you learned in 61a. You may wonder why I have made the head and Tail fields public: a good software engineering principle is that fields should be private. While this is often true, in some cases it is permissible to make fields public, especially if the end programmer will not use your List class explicitly, but only through other classes. Let us now implement a Team data type: class Team { private String name; private String nickname; private List players; private int funds; private List currentplayer; public Team(String name, int money) { this.name = name; funds = money; } public void setNickname (String nn) { this.nickname = nn; } public void addPlayer (Player P) { players = new List(P, players); } public Player removePlayer(Player P) throws NoSuchPlayerException { List l=null , prev=null; if (players == null) throw new NoSuchPlayerException(); if (players.head.equals(P)) { Player found = ((Player) players.head); players = players.tail; return found; } l=players.next; prev = players; for ( ; l != null; l = l.tail, prev = prev.tail) if (l.head.equals(P)) { prev.tail = l.tail; return ((Player) l.head); } throw new NoSuchPlayerException(); return null; } public void transferPlayer(Player P, Team T, int money) { try { T.addPlayer(removePlayer()); funds += money; T.funds -= money; } catch (NoSuchPlayerException e) { System.out.println("No such player on team " + name); } } class TeamEnumeration implements java.util.Enumeration { private List currplayer; public TeamEnumeration() { currplayer = Team.this.players; } public boolean hasMoreElements() { return currplayer != null; } public Object nextElement() { if (currplayer == null) throw new NoSuchElementException(); Player p = ((Player) currplayer.head); currplayer = currplayer.next; return p; } } } Because the List players in Team is declared private users will not be able to arbitrarily mutate the internals of our List, despite the fact that we give public access to head and tail of individual Lists. In the transfer function, the statement T.funds -= money is legal: although T is a different instance, it is still a Team, and hence we are able to access its funds variable from a different Team. Finally TeamEnumeration is declared as a non-static inner class because we want it to be able to access the players field of Team -- otherwise it won't be able to get the listing of players, and because it applies to a specific Team. Although we could make the constructor of TeamEnumeration take a Team argument, it is cleaner to make it non-static. Many variations to the generic List class are possible. Perhaps the most common is the doubly-linked list, where each List element will also have a previous pointer. Others have a special element (called a sentinel) indicating the end of a list instead of null. Abstract Data Types -------- ---- ----- Abstract data types are definitions that are independent of the actual implementation. To some extent this is similar to abstract classes: the definitions must be supported by all implementations (sub-classes) but the exact implementation is left up to the sub-class. You are already familiar with one abstract data type, a stack. In this lecture we will also introduce you to queues. Stacks ------ In the previous lecture we saw the definition of a stack: /** A stack is a LIFO data structure */ public abstract class Stack { /** A Stack that is initially an empty sequence. */ abstract public Stack(); /** True iff this is empty. */ abstract public boolean empty(); /** The first element of the sequence. Requires * that !empty(). */ abstract public Object peek(); /** Return the first item of the sequence and removes * it from the sequence. Requires that !empty(). */ abstract public Object pop(); /** Put ITEM at the beginning of the sequence. */ abstract public void push(Object item); } If you are going to be a user of a stack this is all you need to know about it. You just care that all operations work; how each one is implemented is none of your concern. If, however, your boss asks you to write a Stack class for your co-workers, you have to somehow implement all of these methods. One way is to use a List: public class ListStack extends Stack { private List elems = null; public boolean empty() { return nelems == null; } public Object peek() { return elems.head; } public Object pop() { Object o = elems.head; elems = elems.tail; return o; } public void push(Object item) { elems = new List(item, elems); } } Another is to use an array: public class ArrayStack extends Stack { private Object[] elems = new Object[0]; private int currindex = -1; public boolean empty() { return currindex < 0; } public Object peek() { return elems[currindex]; } public Object pop() { currindex--; return elems[currindex]; } public void push(Object item) { if (currindex < elems.length-1) { currindex++; elems[currindex] = item; } else { currindex++; elems = Arrays.insert(elems, item, currindex); //Arrays.insert() from hw1 } } } Note, that while in the first case all of the operations are instantaneous (constant time), this is no longer true in the second case, because the insert function takes linear time. Queues ------ If the Stack is a LIFO data structure, the queue is the corresponding FIFO (First In First Out) one. Instead of the pop and push methods, it defines the insert() and remove() ones. Here is the ADT: /** A queue is a FIFO data structure */ abstract public class Queue { /** A Queue that is initially an empty sequence. */ abstract public Queue(); /** True iff this is empty. */ abstract public boolean empty(); /** The first element of the sequence. Requires * that !empty(). */ abstract public Object peek(); /** Return the first item of the sequence and removes * it from the sequence. Requires that !empty(). */ abstract public Object remove(); /** Put ITEM at the end of the sequence. */ abstract public void insert(Object item); } Again, just as with the Stack several implementations are possible. We will implement it with both Lists and arrays. public class ListQueue extends Queue { private List begin = null; private List end = null; public boolean empty() { return begin == null; } public Object peek() { return begin.head; } public Object remove() { Object o = begin.head; begin = begin.tail; return o; } public void insert(Object item) { if (begin == null) begin = end = new List(item); else end = end.tail = new List(item); } } public class ArrayQueue extends Queue { private Object[] elems = new Object[] private int begin = 0; // begin is a pointer to the first used elem. private int end = 0; // end is a pointer to the first unused one. public boolean empty() { return begin == end; } public Object peek() { return elems[begin]; } public Object remove() { Object o = elems[begin]; begin++ return o; } public void insert(Object item) { if (end == elems.length) elems = Arrays.insert(elems, item, end++); //Arrays.insert() from hw1 else elems[end++] = item;; } } The implementation of ArrayQueue that we have here is very inefficient: once a piece of memory is used up at the beginning of the queue, it will never again be used. A good implementation would use a "circular array," one where elements that don't fit in the end go into the free space in the front. The implementation is left up to the reader. A related datatype is a dequeue (double-ended queue, pronounced "deck") are sequences that support the operations of both Stacks and Queues: push, pop, insert, remove. A Dequeue is hard to implement eficeintly with a singly linked list (why?), but the implementation with an array is very similar to the queue and stack implementation above.