Transcript Data Structures - Long Island University

Arrays and Lists

Properties
◦ Contents are stored in contiguous memory
locations
◦ Elements of the array are of the same type
 (Perl allows for different types, but then Perl’s strange
that way)
◦ Direct access of elements possible using a cardinal
indexer
 Index is used as the “offset” from the beginning of the
array
◦ Operations
 Allocation
 Accessing

C#
◦ Initial declaration makes a “null” value array
 bool [] booleanArray;
 arrayName = new arrayType[allocationSize];
◦ Contiguous block of memory is allocated
 Which is why the allocation size is required up front
 Adding elements later cannot extend this memory “block”
 Each element in the array is of the “type”
 bool or int would be elements of that type value
 FileInfo is a reference, so the elements would be of that type, which
are references to the actual objects, and not the object per se
bool [] booleanArray;
FileInfo [] files;
booleanArray = new bool[10];
files = new FileInfo[10];
// Read an array element
bool b = booleanArray[7];
// Write to an array element
booleanArray[0] = false;

Running time is O(1)
◦ Constant, regardless of how many elements are stored
 In reality
 Managed code
 Lookup will take extra running time for integrity (indexbounds) check of element costing performance
 Possible to use unmanaged code for access

Make a larger array and then copy the old over array to the
new array
◦ Unassigned values in the new array have the default “0” value
◦ Don’t forget that the old array is still allocated in memory
// Create an integer array with three elements
int [] fib = new int[3];
fib[0] = 1;
fib[1] = 1;
fib[2] = 2;
// Redimension message to a 10 element array
int [] temp = new int[10];
// Copy the fib array to temp
fib.CopyTo(temp, 0);
// Assign temp to fib
fib = temp;

Good for
◦ storing homogeneous data types
◦ Only accessing them directly

Searching unsorted array
◦ Linear running time

If storing large arrays which are searched frequently
◦ Consider other structures

Sorted array
◦ Binary search can be used to search the array
 Running time is O(log N)


Array class has a BinarySearch() method
Multidimensional arrays
◦ Runtime is O(Nk) where “k” is the number of dimension

Customization of a structure for application
◦ Process array of class Employee with its methods
and properties
 might want extra functionality not present in array or
in order to resize the array if needed
 Create a custom data structure with of Employee
 Or.. The array can be of type object
 This can store any data type (all types derive from object in
.Net Framework)
 .Net Framework has such a structure
 System.Collections.ArrayList class
 Internal object array
 When reading value from ArrayList, cast it to data type
being stored

Flexibility is obtained at the expense of
performance
◦ Each array element is a reference to an object

Performance cost due to indirection and boxing/unboxing of data
◦ Boxing is the conversion a value type to a reference type

Allocate memory from heap

Amount of memory is size needed by the value type plus additional overhead to make this
an object

Pointer to virtual method table and pointer to a ‘sync block’


Copy value type’s bit to heap
Return address of the object (reference type)

Retrieve a reference to the value type in an object
◦ Unboxing



Array of objects
◦ Potential run time errors

Wrong data type is added to an element at run time



CLR checks reference type variable is not null and boxed value of the type desired
Pointer to the value is returned
This is not caught at compile time
Bug won’t be caught until testing or actual production run
Typing problem with ArrayList is fixed in .Net Framework with Generics
Type identifier (T) is defined.
specify a
as “T”).
public class TypeSafeList<T>
Requires developer to
{
SINGLE type (aliased
T[] innerArray = new T[0];
int currentSize = 0;
int capacity = 0;
public void Add(T item)
{ // see if array needs to be resized
if (currentSize == capacity)
{ // resize array
capacity = capacity == 0 ? 4 : capacity * 2;
// double capacity
T[] copy = new T[capacity];
// create newly sized array
Array.Copy(innerArray, copy, currentSize);
// copy over the array
innerArray = copy;
// assign innerArray to the new, larger array
}
innerArray[currentSize] = item;
currentSize++;
}
public T this[int index]
{
get
{
if (index < 0 || index >= currentSize)
throw new IndexOutOfRangeException();
return innerArray[index];
}
set
{
if (index < 0 || index >= currentSize)
throw new IndexOutOfRangeException();
innerArray[index] = value;
}
}
public override string ToString()
{
string output = string.Empty;
for (int i = 0; i < currentSize - 1; i++)
output += innerArray[i] + ", “;
return output + innerArray[currentSize - 1];
}
}
TypeSafeList<type> variableName;
 Sample code
TypeSafeList<int> fib = new TypeSafeList<int>();
fib.Add(1);
fib.Add(1);
for (int i = 2; i < 25; i++)
fib.Add(fib[i - 2] + fib[i - 1]);
Console.WriteLine(fib.ToString());

Benefits
◦ Type safety
 Can only add elements of “type” declare or derived
from declared type
 Adding a string to the “fib” example would result in a
compile time error rather than run time error
◦ Performance
 No type checking required at run time
 Boxing/unboxing is eliminated
◦ Reusable
 Break the coupling between the data structure and the
specific application for which it was created



Homogeneous array
Self-redimensioning array
List is a “wrapper” for array
◦ Provides read/write access to array
◦ Automatically resizes the array as required
◦ Utilizes Generics
 Type is specified at development time
 Specified in declaration and instantiation of List
 No size is required in declaration
 Can specify a default starting size in the constructor
 Can use the List.Capacity property to specify
 Add() method is used to add an item
 Items accessible via an ordinal index
// Create a List of integers
List<int> myFavoriteIntegers = new List<int>();
// Create a list of strings
List<string> friendsNames = new List<string>();
Sample
// Create a List of integers
List<int> powersOf2 = new List<int>();
// Add 6 integers to the List
powersOf2.Add(1);
powersOf2.Add(2);
powersOf2.Add(4);
powersOf2.Add(8);
powersOf2.Add(16);
powersOf2.Add(32);
// Change the 2nd List item to 10
powersOf2[1] = 10;
// Compute 2^3 + 2^4
int sum = powersOf2[2] + powersOf2[3];


To find an element in an array, you must process
each element in a loop
◦ unless the array is sorted

List has
◦
◦
◦
◦
◦
◦
◦

Contains() method
IndexOf() method
BinarySearch() method
Find()
FindAll()
Sort()
ConvertAll()
Running time of the List’s operations is the same
as the standard array’s running time