Class 24: The Design of Lists

Held Friday, March 5

Summary

• Introduction to lists
• Lists vs. arrays
• Unordered lists
• Ordered lists
• Sorted lists
• Reading: Java Plus Data Structures, Chapter 4 (Not available)

Contents

Notes

• Any final questions on assignment 6?
  • In question 2c, if we create an algorithm and bound the running time, is there a specific Big O time that we should be shooting for, or does this matter, as long as we can determine the running time of our algorithm and whether it is less than the time we found in part 2a? I'd hope that the new running time is significantly less than the old running time. There should be a ``natural'' new algorithm and running time.
  • If we've written a total of about 10 proofs in our lifetime, will that drastically reduce our grade for this assignment? Haven't you written less than a total of ten programs in your lifetime? I expect that that doesn't affect your ability to do programs.
• Due to some miscommunication between Mr. Flynt and myself, the exams won't be returned until Monday.
• The meeting with the consultants went surprisingly well, particularly given the horrors of that initial memo. Those stories had really been intended as one extreme view of technology. The consultants were also very good at showing that many of us naturally give up some privacy for clear benefits, and they were taking that to an extreme.
• We may have visitors in class today.

Lists

• Lists are among the simplest of data structures.
• Like arrays, they are used for collecting data. That is, lists can be used to store and reteive data.
• In effect, a list is an linearly-organized collection of information.
  • Every nonempty list has a unique first element.
  • Every nonempty list has a unique last element.
  • Every element except the last has a unique successor.
  • Each element except the first has a unique predecessor.
• Unlike arrays, lists do not necessarily guarantee constant time access to each element.
• However, lists do (usually) guarantee constant time insertion of elements at a few places in the list.
  • Some list implementations guarantee constant time insertion at the front of the list.
  • Some list implementations guarantee constant time insertion at the end of the list.
  • Some list implementations provide a ``current element'' (also called a cursor) and guarantee constant time insertion after/before the current element.

Describing Data Structures

• Before we consider the design of lists, we need to consider how we describe and define data structures.
• Just as in the design of objects, it is important to separate specification (what we can do with data structures) from implementation (how we do what we can do).
  • The specification is often referred to as the ``interface'', although I'll try to avoid that terminology since interface has a different meaning in Java.
• How do we specify data structures? Typically, in terms of the operations they permit, along with descriptions of those operations and preconditions and postconditions.
• We also often include an overview.
• Sometimes, we also discuss running time of the various operations.

Describing Arrays

• What are the key operations that you might use to describe arrays?
  • Don't read the next few lines until we've had a chance to discuss them.

• We want to create new arrays
  • Input: size of the array
  • Input: type of the elements in the array
• We want to set elements of arrays
  • Running time: O(1)
• We want to get elements of arrays
  • Running time: O(1)
• We want to get the size of arrays
  • Running time: O(1)
• What else?

Describing Lists

• As before, we can begin to define lists by the operations we permit. What are possible operations?
  • We won't include all of these, but they're some to consider.
• Creation of new, empty, lists.
  • Should we specify the type of elements?
• Insertion of elements in the list.
  • Where?
• Deletion of elements from the list.
  • Where?
• Determine size of the list.
• Test emptiness of the list.
  • Is this just related to the size?
• Test containment of objects in the list.
• Modification of elements in the list.
  • Is this just insertion and deletion?
• Iteration of the list
  • Stepping through the elements, perhaps as in map.

• There are also a number of list operations that might be described as ``Scheme-like list operations''
• Extract the first element of the list. This is often referred to as the head or car of the list.
• Extract all but the first element of the list. This is often referred to as the tail or cdr of the list.

• As we design various kinds of lists, we may choose different subsets of these operations, and fill in more details.

Kinds of Lists

• There are a number of different ``kinds'' of lists, relating, in part, to the way in which the user thinks of using them, adding to them, and getting elements from them.
• We'll consider three different ones. After a high-level overview, we'll return to each in more detail.
• The simplest lists simply provide the linear structure, but with no user control over that structure. The user can add and delete elements, but not determine where added elements go in the list (or what happens during deletion).
  • Iteration provides access to the elements.
  • The list cannot rearrange itself unless elements are added or removed.
• We add some complexity and usefulness by giving the user some control over where elements go in the list. Such lists might be called ordered lists.
  • The simplest control is simply to say ``new elements go at the end/front, and elements never change position''.
  • We might also add a ``current'' element and insert before or after it.
• We might also impose a predetermined order (a ``sort order'') on the list and require that it be iterated in that order.
  • Insertion and deletion ensure that the sort order is maintained.

More Design Issues

• Before we implement lists, we need to consider a number of other issues related to the design of lists.
• There are a number of ways in which we can implement lists, and these implementations govern the cost of the various operations.
  • Most programmers expect that insertion and testing for emptiness are constant time operations. Certain kinds of deletion are also constant time (e.g., delete the first element).
• There are a number of hidden issues to consider when designing implementations.
• We must also decide whether multiple lists can share structure. That is, if L is a list, can M be a list with an extra element at the front and L as the remainder and N be a list with an extra element at the front a L as the remainder? If so, does a change to the second element of M affect N?
• For example, when we ask for the tail of a list and then modify that tail, do we modify the original list?
• Here's one example in Java form

  // Assume l is the list 3,6,8,32
  lprime = l.tail();
  lprime.addToHead(new Integer(5));
  System.out.println(l.tail().head());
  

• Here's a similar example that might have different results (at least in terms of our understanding of what modifications mean)

  // Assume l is the list 3,6,8,32
  lprime = l.tail();
  lprime.remove(new Integer(8));
  System.out.println(l.contains(new Integer(8)));
  

• In designing our implementations, we will need to consider tradeoffs between efficiency, memory usage, simplicity of implementation, and ambiguity.

History

• Created Monday, January 11, 1999.
• Added short summary on Friday, January 22, 1999.
• Filled in the body on Thursday, March 4, 1999, taken from the already-prepared outline of the previous class (which took a very different course). Some details were based on outline 28 of CS152 98S, although most were new.