Closed Lists and Related Data Structures closedLists

Open vs. Closed Lists

		Two list models are described in the text:
			Open lists:
				Elements and sublists can be shared
				Mutation of lists is discouraged
				Mathematically elegant
			Closed lists:
				Sharing generally not done
				Mutation of lists is ok, because they are encapsulated
				Mathematically less attractive
			Closed lists can be built by wrapping open lists

Purpose of Closed Lists

	A closed list is used for its identity as an object, rather than purely for its value as a sequence.
	Several ÒclientsÓ can access the same closed list; modifications made by one will be seen by all.
	In some cases, this is the desired behavior.
	In some cases, more space-efficient due to in-place modification.

Closed List Implementation

	A closed list can be implemented as an Òopen list in a boxÓ.
	Cells in the list are typically not shared from the outside, so they can be mutated at will.
	Outside access is through a mutable reference called the ÒheadÓ.

An Empty Closed List

Possible Java implementation

How to Add and Remove Elements?

	To add, must specify:
		Item to be added
		To where it should be added
	To remove, must specify
		From where it should be removed

Some Typical Choices

	Always add and remove from the head.
	Always add and remove from the tail.
	Add to the tail, remove from the head.
	Add and remove at random places (how to identify where?)

Common Closed List Usages

	Stack
		remembers elements in reverse order of entry, i.e. last-in element is first-out (ÒLIFOÓ)
	Queue
		remembers elements in order of entry, i.e. first-in element is first-out (ÒFIFOÓ)

Stack Abstraction

	Stack s = new Stack();
	s.push(ÒaÓ);
	s.push(ÒbÓ);
	s.push(ÒcÓ);
	value = s.pop(); // value will be ÒcÓ
	value = s.pop(); // value will be ÒbÓ
	value = s.pop(); // value will be ÒaÓ

Stack Implementation (push)

Stack Implementation (pop)

Reading Code containing References and Pointers

	Suppose s and t are references.
	Read the assignment statement s = t; as Òmake s point to where t pointsÓ.
	To see why, consider

Figurative Code for Push/Pop

	s.push(Object x): s.head = new Cell(x, s.head);
	s.pop(): Object top = s.head.value; s.head = s.head.next; return top;

Push -> Shove

	Define shove to be an operation that adds the contents of an entire open list to a stack, with the first item in the list being the last item to be added.
	How could this be coded?

Queue Abstraction

	Queue r = new Queue();
	r.enqueue(ÒaÓ);
	r.enqueue(ÒbÓ);
	r.enqueue(ÒcÓ);
	value = r.dequeue();   // value will be ÒaÓ
	value = r.dequeue();   // value will be ÒbÓ
	value = r.dequeue();   // value will be ÒcÓ

Queue Implementation

	For a queue, we usually add another reference, to the last element, for convenience.  This element is called the tail.

Enqueue/Dequeue

	enqueue adds a new element to one end of the internal open list.
	dequeue removes an element and returns it.
	But which end is used for which?

Homework

	Write the code for enqueue and dequeue.

Related Topics

	Lists of lists: No problem with OpenList, or in any framework in which lists contain Objects and are objects.
	Otherwise, need to define special type of list, tailored to the type of element being listed.

Doubly-Linked Lists

	An implementation concept
	Could use to implement double-ended queues:
		ÒdequesÓ (pron. ÒdeckÓ)
		not to be confused with ÒdequeueÓ

Deque Abstraction

	void  pushFront(Object)
	Object popFront()
	void pushBack(Object)
	Object popBack()
	boolean isEmpty()

General Doubly-Linked Lists

	Extend usage in Deque by allowing insertion and removal at arbitrary points
	Can access the object before any object, as well as after, unlike singly-linked lists.
	Disadvantages:
		More storage is used for the extra pointer per cell.
		Sharing is extremely tricky; better not done.
	Applications?

Doubly-Linked Lists as an Implementation Concept

	In the implementation (as opposed to an appropriate abstraction), we realize that the list is composed of cells.
	Cells make it easy to talk about various operations

Doubly-Linked Lists as an Implementation Concept

	Cells make it easy to talk about various operations:
		void insertAfter(Cell, newCell)
		void insertBefore(Cell, newCell)
		void remove(Cell)
		Cell getNext()
		Cell getPrevious()

Possible Abstractions for Doubly-Linked Lists

	A problem is that Cell, an implementation concept, does not make an attractive abstraction.
	A preferable view is to think in terms of a list Iterator (or Cursor), which maintains a position within a list and can move backward or forward.
	The Iterator determines an insertion point for a new value, or point before/after a value is removed.

Example: ListIterator (in java.util)

	If L is a List, then L.listIterator() returns a ListIterator positioned at the start of the list.
	For a ListIterator:
		Object next() returns the next element, if any
		boolean hasNext() tells whether there is a next element
		Object previous() returns the previous element, if any
		boolean hasPrevious() tells whether there is a previous element
		void set(Object) sets the value at the current position
		void remove() removes the value at the current position
		void add(Object) adds a value at the current position

Example, part 1 (complete source file)

Example (contÕd)

Example (contÕd)

Iterators as Interfaces

Review of Interfaces in Java

	A principal abstraction mechanism in Java is the formal concept of interface.
	An interface is like a class, except that it only declares methods, it does not implement them.
	A given class may implement the interface by giving concrete methods for each of the ones declared in the interface.
	The class definition must assert that it implements the interface. The compiler checks that this is the case.

Interface vs. Implementation

Use of an Iterator

Recall Important Aspects of Interface Concept

	An interface is a type, just as a class is.
	When a variableÕs type is that of an interface, a variable of any implementing class type may be used.
	Any number of distinct classes can implement a given interface.

Implication of second point

Reemphasis: Power of Interface

	The interface abstraction is powerful, because it does not require the user to know which implementation is being used.
	The user of a method that specifies an interface argument can thus pass an object of any class that implements the interface.

Value of Interfaces

	Interfaces force the provider of a service to give a clear specification of what the service is, independent of how the service is implemented.

Enumerations

	An Enumeration is the name given, in early Java, for a special one-way Iterator.
	hasMoreElements() is used instead of hasNext()
	nextElement() is used instead of next()
	no remove() is specified
	Typically, an enumeration is obtained from an Object by the elements() method.

Example: Enumerating a Vector

More Interface Examples with some Implementations (see Java API)

	List
		Interface: List
		Implementations: LinkedList, Vector, ArrayList
	Set
		Interface: Set
		Implementations: HashSet, TreeSet
	Comparable interface
		Character, Double, Long, String, BigInteger, Date, etc.

More Interface Examples with some Implementations

	ListIterator interface
		listIterator() returned by a LinkedList
	Enumeration interface: read-only version of Iterator
		elements() returned by a Vector, HashTable, or OpenList
		StringTokenizer
	Cloneable interface
		Many classes