Data Structures and Agorithm: DS 02 Array List.pptx

Data Structures and Agorithm: DS 02 Array List

1. Data Structure Lecture No. 2 Array List Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti International Islamic University H-10, Islamabad, Pakistan Video Lecture

2. We have designed the interface for the List; we now must consider how to implement that interface . Implementing Lists using an array: for example, the list of integers { 2 , 6, 8, 7, 1} could be represented as : insert(3,9) : The new list would thus be: {2 , 6, 8, 9 , 7, 1} We have to shift every element to the right of one place from current position to make space for the new element ‘ 9 ’. Implementing Array List Index No. 1 2 3 4 5 6 7 Size Data 2 6 8 7 1 8 Index No. 1 2 3 4 5 6 7 Size Data 2 6 8 7 7 1 8 Index No. 1 2 3 4 5 6 7 Size Data 2 6 8 9 7 1 8 Step 1: Step 2:

3. insert(3,9) : void insert ( int pos , int num ){ int i ; // Rigt Shift all numbers from pos position. for ( i = size - 1 ; i > pos ; i-- ) data[ i ] = data[ i - 1] ; // now place the data at pos position. data[ i ] = num ; } Implementing Array List

4. Remove(1) : R emoves the element at the index 1 . We have to shift every element to the left of one place from index number 1 to remove data . Implementing Array List Index No. 1 2 3 4 5 6 7 Size Data 2 6 8 9 7 1 8 Index No. 1 2 3 4 5 6 7 Size Data 2 8 9 7 1 8 Step 1: Step 2:

5. Remove(1) : remove ( int pos ) { int i ; // Left Shift all numbers from pos position. for ( i = pos ; i < size ; i++ ) data[ i ] = data[ i + 1] ; // Fill the right most number with 0 to avoid filling garbage vlaue data[ i - 1] = 0; } Implementing Array List

6. Find(9) : Find a Number 9 from Array List. void Find( int Data_to_Search ) { for ( int i=0 ; i < s ize ; i++ ) if ( Data[ i ] == Data_to_Search ){ cout << num << " is present at index No. " << i << endl ; return ; } cout << "\ nNot Found " << num << endl ; } Implementing Array List

7. Copy() : Copies a List. Clear(): clear a list (remove all elements) Get (?): Get element at a given position update ( int pos, int num ): replace the element at a given position with num ; Implementing Array List

8. # include < iostream > using namespace std ; class List { private : int size; int *data ; public : List (); List( int sz ); void create( int sz ); List copy (); void clear (); void insert ( int pos , int num ) ; void remove ( int pos ) ; int get( int pos ); 8 Example 1 : List Using an Array void update ( int pos, int num ); void find ( int num ) ; void reverse( ) ; void display( ) ; int length(); }; List :: List(){ data = nullptr ; size = 0; } List :: List( int sz ){ size = sz ; data = new int [size]; for ( int i=0 ; i<size ; i++) data[ i ] = 0; } 1 2

9. void List :: create( int sz ) { size = sz ; data = new int [size]; for ( int i=0 ; i<size ; i++) data[ i ] = 0; } int List::length(){ return (size); } List List::copy (){ List temp(size); for ( int i = 0 ; i<size ; i++){ temp.data [ i ] = data[ i ]; } return temp; } 9 Example 1 : List Using an Array void List::clear (){ if (data != nullptr ) delete [] data; } void List :: insert ( int pos , int num ){ int i ; for ( i = size - 1 ; i > pos ; i-- ) data[ i ] = data[ i - 1] ; data[ i ] = num ; } void List :: remove ( int pos ){ int i ; for ( i = pos ; i < size ; i++ ) data[ i ] = data[ i + 1] ; data[ i - 1] = 0; } 3 4

10. int List :: get ( int pos ){ return data[ pos ]; } void List :: update ( int pos , int num ){ data[ pos ] = num ; } void List :: find ( int num ){ int i ; for ( i = 0 ; i < size ; i++ ) { if ( data[ i ] == num ){ cout << "\ nThe element " << num << " is present at index No. " << i << endl ; return ; } } cout << "\ nThe element " << num << " is not present" ; } 10 Example 1 : List Using an Array void List :: display( ) { cout << endl ; for ( int i = 0 ; i < size ; i++ ) cout << " " << data[ i ] ; cout << endl ; } int main( ){ List l1,l2; l1.create(8 ); l1.insert(0,2 );l1.insert(1,6 ); l1.insert(2,8 );l1.insert(3,7); l1.insert(4,1 );l1.display(); l1.insert(3,9 ); l1.display(); l1.remove(1 ); l1.display(); return 0; } 5 6

11. Implementing Array List