Array Lists in C

ARRAY– Stores multiple items[Series of characters, multiple strings].

Array is declared in the form of;

int a[3][2]={ {1,4}, {5,2}, {6,5}

};

Declared array is of size 3*2.

This declared array contains total of 6 elements. Row1:  {1,4}, Row2:  {5,2}, Row3:  {6,5}.

Thus the array can be initialized row wise as well as sequentially.

Arrays are formulated as:

Type of array: Defines the type of element- Such as char, int , structure ec..
Name of array: Defines the name given to an array.
Number of element: Value inside the subscript”[]” gives the number of element.
Example: char arr[5];

Initialization:

* Initializing each element seperately

Example:

int arr[10]; int i; for (i=0;i<=10;i++) {

arr[i]=i;// Each element is initializeed seperarately

}

* Initializing array at the time of decelaration

Example:

int arr[]={‘1′,’2′,’3′,’4′,’5’};

*Initializing array with a string

Type 1

Example:

char arr[]= {‘c’,’o’,’d’,’e’,”};

Type 2

Example:
char arr[] = “code”;

Accessing values in an array
Example:

int arr[10]; int i=0; for(i=0;i

int j = arr[5];//accessing the 5th element of integer array arr and assigning its value to integer j.

Types of array:

One dimensional array:

Its a structured collection of components.

syntax: DataType  ArrayName  [constIntExpression];

Example:

int number [50];

To store the values in the number array, we can formulate it as

for(int i=0;i<50;i++) { number[i]=i;

cout<<“number[“<

To use the stored values,

for (int i=0; i<50; i++) { number[i]=2*number[i];

cout<<“number[“<

Example for one dimensional array:

// Program arrays.cpp manipulates values in an array.

#include
using namespace std;

int main () { const int MAX_ARRAY = 5; int numbers[MAX_ARRAY]; int index;

int sum;

// Stored values in the array.

for (index = 0; index < MAX_ARRAY; index++)
numbers[index] = index * index;

// The values in the array are summed.

sum = 0; for (index = 0; index < MAX_ARRAY; index++) sum = sum + numbers[index];

cout << “Sum is ” << sum << endl;

// Add code to print out the values of all the array elements

return 0; }

Array used for maintaining multiple variable names using single name:

For

Example
int roll1,roll2,roll3,roll4,roll5;- This can be re formed as

int roll[5];

Array are also used for sorting elements

SORTING

Basically sorting are classified as Bubble sort Insertion sort Selection sort

Bucket sort

Array can perform matrix operation:

Matrix can performed using multi dimensional array.

One dimensional array

Example

#include

int main() { int num[] = {2,8,7,6,0};

int i;

for(i=0;i<5;i++) { printf(“\nArray Element num[%d] : %d”,i+1,num[i]);

}

return 0; }

Limitations of array in c programming:

1. Static Data

*Array is static data structure *Memory allocated during compile time

*once memory is allocated at compile time it cannot be changed during run time.

2.Can hold data belonging to same data types. 3.Inserting data in array is difficult. 4.Deletion operation is difficult. 5. Bound checking. 6.Shortage of memory

7.Wastage of memory.

Common mistakes:

1. Constant expression require

#include void main() { int i=10; int a[i];

}

In the above example, i is initialized to 10, and denoting as a[i] doesnot mean as a[10] because i is the integer variable whose value can be changed inside the program. so the above example can be rereturn as #include void main() { const int i=10; int a[10];

}

OR

int a[10];

2. Empty valued

#include void main() { int arr[]; } OR #include void main() { int a[]={};// This aso creates an error.

}

In this example, the size of the array must be specified as a constant value.

So, the correct form of writing this example is given as, #include void main()

{

int arr[]={2,2};
}

3. Does not checks bound checking

#include void main() { int a[5]; printf(“%d”,a[7]);

}

In this example, array size is specified as 5, so the array element is given by a[0], a[1], a[2], a[3] and a[4].

but accesing a[5] causes the garbage value to be used since c doesnt perform arrays bound check.

4. Case sensitive

#include void main() { int a[5]; printf(“%d”,A[2]); }

Tips for assigning array:

1. Use #define to specify array size

#include #define MAX 5 void main() { int a[MAX]; printf(“%d”,a[2]);

}

In this example, as MAX is replaced by 5 for every occurence, inorder to increase or decrease the size of array then the changes should be made in #define max 10

2.a[i] and i[a] are same

Standard

The examples in this and the subsequent two documents all part of the Java Application ListDeque. Download the source archive ListDeque.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details. Like others, the ListDeque project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to right-click the file and select Run File either in the file itself or from the listing in the Projects window.

ArrayList and other classes

The ArrayList implements these interfaces (and others):

• Iterable, with method:
• Collection   (aggregate access, extends Iterable), with methods:

  boolean add(E e) int size() boolean isEmpty() void clear() boolean remove(Object o) boolean addAll(Collection extends E> c) boolean removeAll(Collection c) boolean retainAll(Collection c) boolean containsAll(Collection c) boolean contains(Object o) E[] toArray(E[] a) Object[] toArray()

• List   (positional access, extends Collection), with methods:

  E get(int index) E set(int index, E element) void add(int index, E element) int indexOf(Object o) int lastIndexOf(Object o) E remove(int index) List<E> subList(int fromIndex, int toIndex) ListIterator<E> listIterator() ListIterator<E> listIterator(int index) boolean addAll(int index, Collection extends E> c)

User-defined data structures

Why would we want to write our own implementations of data structures when Java already has everything we need? There are several goals:

• learn how to implement the operations
• gain some understanding of the cost of each operation
• understand the significance of one implementation choice versus another.
• use our versions to obtain counts of operation executions in order to create an empirical analysis of the effect of using these data structures in applications

In this document we will focus on the ArrayList class. We will follow a method suggested by these steps:

1. Create illustrative examples to see the Java Collections ArrayList member functions work.
2. Create a "dummy" class, called AListAdapter, which implements all the relevant interfaces and member functions that ArrayList implements, but with implementation functions which effectively say "not implemented."
3. Create an extension of AListAdapter called AList in which implements the member functions by overriding the AListAdapter definitions. Because AList is an extension of the "working" class, AListAdapter, there is no need to define every function, only those of interest to us.

ArrayList Demo

Start by observing and running the main class demo.AListDemo. Observe how we express the list declaration operation:

List<String> L = new ArrayList<>();

Abstractly, we might say the statement is of the form: Interface obj = new Implementation(); We conceivable could use this:

ArrayList<String> L = new ArrayList<>();

In general, the former declaration (using the List interface) is preferred because it allows the application to change the implementation very easily, since it is presumed that the only operations used are those specified by the interface. If we do use some ArrayList-specific operation we wish to use we would need to cast the object: ((ArrayList) L).operation Of course, by doing so would lose the implementation-independency of the code.

Explicit and Implicit operations

In the demo program, we see the usage of common list member functions:

add, size, get, set, remove, clear, isEmpty

Additionally, there are several operations which are used implicitly:

• String toString(): this is used when the list is printed: System.out.println(L);
• iterator(): this is used to run the enhanced for loop:

  for (String s: L) { System.out.println(s); }

  The equivalent explicit code is this:

  Iterator<String> iterator = L.iterator(); while (iterator.hasNext()) { String s = iterator.next(); System.out.println(s); }

We're going to construct our own implementation of ArrayList called AList. The basic idea is that it is simply a wrapper around an array which resizes as necessary in a manner transparent to the usage. The basis of our construction is an adapter class, AListAdapter. The idea of an adapter class is that it implements all the ArrayList functions, but only in a vacuous manner. The functions are all implemented in the sense that their only code is to throw an UnsupportedOperationException. Our user-defined AList class then will be an extension of AListAdapter and we can pick and choose the functions we want to implement. AListAdapter implicitly implements the Collection and Iterator interfaces as well because they super-interfaces of List. The Serializable interface requires no implementations and implies that an AListAdapter object can be written to a file or sent through the network. The RandomAccess interface also requires no implementations and is only used to guarantee for users of this class that "get/set" member functions are constant time, O(1).

AList Implementation

Here is the Java implementation class: Try it out by making the code change in main of the AListDemo program:

public static void main(String[] args) { // List L = new ArrayList<>(); List<String> L = new AList<>();

The array has as certain capacity, but the actual content is controlled by the current size. The private data members used to handle that are these:

private int size = 0; private E[] data;

It is assumed that all member functions keep track of size correctly so that we can give these definitions:

public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { size = 0; }

The primary constructor is this:

public AList(int capacity) { data = (E[]) new Object[capacity]; }

Observe how we must deal with creating an array of the unknown generic type E. If a user doesn't care to specify the capacity, these are used:

private static final int DEFAULT_CAPACITY = 10;   public AList() { this(DEFAULT_CAPACITY); }

The most basic capacity handler is a private function which creates a new array and copies over the old one:

private void increaseCapacity(int new_capacity) { if (new_capacity <= data.length) { return; } E[] new_data = (E[]) new Object[new_capacity]; for (int i = 0; i < capacity; ++i) { new_data[i] = data[i]; } data = new_data; }

The most basic member function is the add function which adds to the array's end:

public boolean add(E elt) { if (size == data.length) { increaseCapacity( data.length * 2 ); } data[size++] = elt; return true; }

If an add operation does not increase the capacity, it has a constant-time cost, O(1). If, however, an add operation causes the capacity to increase, the cost is O(n) based on the size, n, of the array due to the overhead of copying over the old array contents to a new one. We want to argue that if the capacity is increased by doubling it, the average cost of an operation is still O(1). Consider the operation of filling an empty ArrayList with values by using the add operation. The initial capacity is 10 and whenever size would exceed capacity, we increase the capacity by calling: increaseCapacity( 2 * capacity ); // change array size and copy over Let overhead(n) be the total number of element copy operations which have taken place when the array size has just exceeded n elements. Consider the values n = 10, 20, 40, 80, 160 .... Observe that overhead(n) accumulates, and satisfies this recurrence relation: overhead(10) = 10 overhead(20) = overhead(10) + 20 = 30 overhead(n) = overhead(n/2) + n, n > 20 We can prove by induction that overhead(n) ≤ 2 * n Since this is the total overhead for n adds, the average overhead for a single add operation is: overhead(n)/n ≤ 2 Conclude that the average time to add is O(1) even with the overhead counted.

Search-related Operations

One of the key notions of a List is that it keeps track of the position of elements. The search operations use a linear searche front to rear or vice-versa since there is no presumed structure on the data.

public int indexOf(Object obj) { for (int i=0; i < size; ++i) { if (data[i].equals(obj)) return i; } return -1; }   public int lastIndexOf(Object obj) { for (int i=size; i > 0; --i) { if (data[i-1].equals(obj)) return i-1; } return -1; }   public boolean contains(Object obj) { return indexOf(obj) != -1; }

null values

We noted in the Analysis section that null values can cause probles using the equals operator. Our code above implicitly assumes that there are no null values in the list. To avoid this assumption, the gimmick is to treat obj==null as a special case, thus rewriting indexOf like this:

public int indexOf(Object obj) { if (obj == null) { for (int i=0; i < size; ++i) { if (data[i] == null) { return i; } } } else { for (int i=0; i < size; ++i) { if (obj.equals(data[i])) { return i; } } } return -1; }

An analogous thing would be done with lastIndexOf.

Equality in User-defined classes

If you want to use your own user-defined classes in Java Lists, the only catch is that you have to have a correctly defined equals method for the search-related operations. Here is a demo program which illustrates two classes, Person and User. The Person equals definition is correct, whereas the User equals definition is incorrect regarding searches of lists of these objects. The other operations are insertion or removal at a position which causes the data to the right of the insert or remove position to be shifted right or left, respectively.

public void add(int index, E elt) { if (index > size || index < 0) { throw new IndexOutOfBoundsException("Index: " + index + ", " + "Size: " + size); } if (size == data.length) { increaseCapacity(data.length*2); } for (int i = size; i > index; --i) { // shift these up data[i] = data[i-1]; } data[index] = elt; // insert this one ++size; }   public E remove(int index) { if (index >= size || index < 0) { throw new IndexOutOfBoundsException("Index: " + index + ", " + "Size: " + size); } E saved = data[size]; for (int i=index; i < size-1; ++i) { // shift elements down data[i] = data[i+1]; } --size; return saved; }   public boolean remove(Object o) { int i = indexOf(o); if (i == -1) { return false; } remove(i); return true; }

We mentioned above about the implicitly used member functions iterator and toString. In order to handle these situations we use the following functions:

public Object[] toArray() { return Arrays.copyOf(data, size); }   public String toString() { return Arrays.toString(toArray()); }   public ListIterator<E> listIterator() { return Arrays.asList( (E[]) toArray() ).listIterator(); }   public Iterator<E> iterator() { return listIterator(); }

The textbook goes to pains to illustrate how to define the iterator. We have side-stepped the issue by:

• using the Arrays.asList operator to define the listIterator function
• defining the iterator function as the result of the listIterator function

If we want to define these ourselves, we can either define the iterator function which returns an implementation of the Iterator interface using these functions:

public boolean hasNext() public E next() public void remove()

or, define the listIterator function which returns an implementation of the extended ListIterator interface with these additional functions:

public int nextIndex() public E previous() public int previousIndex() public void add(E elt) public void set(E elt) public boolean hasPrevious()

The add and remove operations are potentially the most difficult, but, according to the Java documentation, these operations are "optional", which means that we can implement them by saying that they're not implemented, which in Java terms means: throw new UnsupportedOperationException(); The other point noted in the textbook is that the implementation class needs to be an inner class so that it can access the private data. Since this class need never be reused, we'll make it an anonymous inner class, giving us a definition like this:

public ListIterator<E> listIterator() { return new ListIterator<E>() { private int index = 0;   public boolean hasNext() { return index < size; } public E next() { return data[index++]; }   public int nextIndex() { return index+1; } public int previousIndex() { return index-1; } public E previous() { return data[--index]; } public void set(E elt) { data[index] = e; } public boolean hasPrevious() { return index > 0; }   public void remove() { throw new UnsupportedOperationException(); } public void add(E elt) { throw new UnsupportedOperationException(); } }; }