Topics

• Data structures
• Containers
• Static and dynamic fixed capacity
• Arrays and vectors

Data Structures

From Wikipedia:

Is an int or double a Data Structure?

• They're composed of smaller bits in a format that is chosen for efficient access and operation
• However, the actual access and operation is performed at the hardware level — as opposed to being designed/implemented by the programmer — so we don't consider them data structures per se.

Is a Student, BankAccount, or Customer Class a Data Structure?

• Technically yes, and definitely more so than the above numeric types.
• They are constructed using the class mechanism which allows for the 'packaging' of various pieces of data (attributes) of a modelled object, and thus form a structure of data, corresponding to the information maintained for a student, a bank account, and a customer respectively.
  • As an aside, strictly speaking, the class is not a data structure, rather a specification for the creation of objects (instances) that form the structure.
    • We will often be pedantic in this manner; proper use of the terminology of classes and object is often important in our discussion
• However, these structures are 'boring' in the sense that their specification and methods are 'one-offs' in the sense that they are for a particular application,rather than having universal application.

Containers

Again, from Wikipedia:

• Containers are more interesting in that they have a universal application: storing (and subsequently retrieving) other objects.
• Furthermore, efficient storage/retrieval (and iteration) are both key and lead to very interesting algorithms and structures
• They are thus worthy of in-depth study

Thus, a course in data structures is typically an investigation into containers.

In some sense, this course is your first in studying computer science rather than simply a programming language. We will be taking most of the material you have covered in the previous courses and applying it to the study, design, and implementation of containers.

So an Array Must be a Container and a Data Structure

• Yes it is, and indeed, it is the fundamental homogeneous container/data structure found in hardware and most programming languages
  • Homogeneous means that all the elements of the array are of the same type
    • This is in contract with a heterogeneous container in which the various elements can be of different types (the class mechanism permits the creation of heterogeneous structures, e.g. a Person object with a string for a name and an integer for an age).
• However, like the numeric examples at the beginning of this discussion, the operations upon the array (subscripting) are performed below the level of the programmer.
• Thus, while definitely in the category of data structure/container, arrays are of little interest to us except as a foundational container upon which we will build other containers with various storage/retrieval properties.
  • We will see that the combination of homogeneous (e.g. array) and heterogeneous (e.g. class definition) provides us with the basic mechanism for creating arbitrary containers.

Arrays

Before we move on from the built-in array, let's examine it's basic properties, operations, and limitations.

• Element: an array, like all containers, holds other objects, known as the elements of the container
  • Each element has a unique position, known as its index or subscript within the array; most modern languages use 0 as the first position, and thus the last element is at index #elements - 1
• Homogeneous: the elements of an array are all of the same type; in Java the type is supplied at the time of declaration of the corresponding reference variable as well as when the array object is created., e.g. int [] arr = new int[100];
• Fixed size: the number of elements of an array is specified at object creation time, and cannot change (although the value can be calculated at run time), again new int[100]
  • however, the reference variable referring to the array can be made to refer to a different array object; this will be the basis of 'growable' containers, which we introduce in the next lecture.
• Contiguous memory: the elements of the array are guaranteed to follow each other in memory, with element 0 first, followed by element 1, etc
• Subscripting: the basic operation of storage and retrieval is subscripting, i.e., the specification of the element to be stored to and retrieved from. In most languages, this operator is written as [i] (upon occasion (i)) with i being the element in question.
  • It is the contiguous memory property of the array that makes subscripting a highly efficient operation; accessing the millionth element of an array is essentially as efficient as the first.

Specific to Java:

• length: the number of elements allocated to the array can be obtained via this integer value. Note this is not a method, but rather a read-only value field associated with the array
• Bounds-checking: attempting to access an element whose index is outside the range of the fixed-size of the array (i.e., 0 .. length-1) causes an exception to be thrown.

Arrays in Java

• The primitive array does not supply a length field, nor perform bounds-checking; these are both artifices provided by the Java runtime
  • For example, C/C++ provides neither of those two facilities for their array type .
• In fact, an array in Java is not considered a primitive type (as is the case for C/C++), but is rather an object, which implies runtime support.
• In this sense, we could say Java's array type is more of a data structure (in the sense we are using the term) that a primitive array.
• But again, as this support is coming below our radar (i.e., provided by the runtime rather than our own code, we will treat the array as a fundamental container
• As an aside, the properties of the array (in particular the mechanics of subscripting) are covered in more detail in an architecture course.

A Class Version of Java's Array

Here is the Java built-in array, implemented as a class. The idea here is:

• To present an example of a container class
  • In this case we use a familiar container … the array
• To emphasize the absence of operators when dealing with classes
  • Java does not support the definition of operators for classes, thus we have to replace the subscript operator with get/set methods
• To introduce the notion of capacity
• To show a toString method for a container

class Array {
	Array(int capacity) {arr = new int[capacity];}
	Array() {this(DEFAULT_CAPACITY);}

	int get(int index) {return arr[index];}

	void set(int index, int value) {arr[index] = value;}

	int length() {return arr.length;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < length(); i++)
			result += arr[i] + (i < length()-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr;
	static final int DEFAULT_CAPACITY = 10;
}

A Demo App for the Array Class

Here is a Java application (i.e., a class with a main method that uses the Arrayy class defined above:

public class ArrayApp {
	public static void main(String [] args) {
		Array a = new Array();
		System.out.println("length: " + a.length());

		for (int i = 0; i < a.length(); i++)
			a.set(i, i * 10);
		System.out.println("a: " + a);
		System.out.println("length: " + a.length());

		for (int i = 0; i < a.length(); i++)
			a.set(i, a.get(i)+1);
		System.out.println("a: " + a);
	}
}

Here is the output of the app:

length: 10
a: {0, 10, 20, 30, 40, 50, 60, 70, 80, 90}
length: 10
a: {1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

A First Container: Vector (Partially Populated Array)

Arrays are typically populated by reading in (or calculating) data items and adding them to the end of the array.

• Unless one knows in advance the number of items, one cannot allocate an array of the exact size.
  • Furthermore, even if one knows the exact number of initial items, it is often the case that one might wish to subsequently add or remove items.

To solve this problem, we usually employ partially-populated arrays rather than an array of the exact number of elements (i.e., a fully-populated array).

• A partially-populated array consists of an array together with an integer variable, often named size.
• An additional operation — let's call it add — append adds an element to the next available index of the array.
  • size is used to maintain the location of the next available element
    • size is also the number of elements placed into the array
• The only elements that are considered part of the container are those in the range 0 .. size-1
  • The semantics of the container thus uses both the array and the size variable. Packaging the two together in a class and supplying methods to achieve this semantics is what we mean by a data structure.

The above behavior is a subset of a more substantial container known as a vector, list, or sequence (In Java, the corresponding class is the ArrayList. We will be investigating it in more detail later.

Physical and Logical Size (Capacity vs Size)

• capacity/physical size: number of elements the array was created with
• size/logical size: number of elements assigned values
• We sometime refer to the physical container (the array as created) vs the logical container (the filled portion of the array.
  • The former has bounds 0 … arr.length-1; whereas the latter has bounds 0 … size-1
• The only elements that contain meaningful data are those in the range 0 … size-1.
  • Thus, one builds up the (logical) portion of the container by appending values (using add), and then is free to get and/or set anywhere in that range

Vector Version 1: Static (Compile-time) Capacity

We're actually going to take a step backwards here vis-a-vis the above Array class: we're going to start of with a container whose capacity is hardcoded into the class (rather than specified in the constructor as we did with Array).

• We're doing this to allow us to initiate a discussion about capacity, i,.e, the allocated size / number of elements of a container.

class Vector {
	int get(int index) {return arr[index];}

	void set(int index, int value) {arr[index] = value;}

	void add(int value) {arr[size++] = value;}

	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr = new int[CAPACITY];
	int size = 0;
	static final int CAPACITY = 10;
}

Here is the app:

public class VectorApp {
	public static void main(String [] args) {
		Vector v = new Vector();
		System.out.println("size: " + v.size());

		for (int i = 0; i < Vector.CAPACITY; i++) {
			v.add(i * 10);
			System.out.println(v + " (" + v.size() + ")");
		}

		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println("v: " + v);
	}
}

size: 0
{0} (1)
{0, 10} (2)
{0, 10, 20} (3)
{0, 10, 20, 30} (4)
{0, 10, 20, 30, 40} (5)
{0, 10, 20, 30, 40, 50} (6)
{0, 10, 20, 30, 40, 50, 60} (7)
{0, 10, 20, 30, 40, 50, 60, 70} (8)
{0, 10, 20, 30, 40, 50, 60, 70, 80} (9)
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10)
v: {1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

Vector Version 2: Dynamic (Runtime) Capacity

class Vector {
	Vector(int capacity) {arr = new int[capacity];}
	Vector() {this(DEFAULT_CAPACITY);}

	int get(int index) {return arr[index];}

	void set(int index, int value) {arr[index] = value;}

	void add(int value) { arr[size++] = value;}

	int getCapacity() {return arr.length;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr;
	int size = 0;
	static final int DEFAULT_CAPACITY = 10;
}

The app:

public class VectorApp {
	public static void main(String [] args) {
		doIt(new Vector(5));
		System.out.println();
		doIt(new Vector());
	}

	static void doIt(Vector v) {
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());

		for (int i = 0; i < v.getCapacity(); i++) {
			v.add(i * 10);
			System.out.println(v + " (" + v.size() + ")");
		}

		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println("v: " + v);
	}

And the output:

capacity: 5
size: 0
{0} (1)
{0, 10} (2)
{0, 10, 20} (3)
{0, 10, 20, 30} (4)
{0, 10, 20, 30, 40} (5)
v: {1, 11, 21, 31, 41}

capacity: 10
size: 0
{0} (1)
{0, 10} (2)
{0, 10, 20} (3)
{0, 10, 20, 30} (4)
{0, 10, 20, 30, 40} (5)
{0, 10, 20, 30, 40, 50} (6)
{0, 10, 20, 30, 40, 50, 60} (7)
{0, 10, 20, 30, 40, 50, 60, 70} (8)
{0, 10, 20, 30, 40, 50, 60, 70, 80} (9)
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10)
v: {1, 11, 21, 31, 41, 51, 61, 71, 81, 91}