Scribd
Upload
3 views

DS 02 Array List

Array List ppt

Uploaded by

kinshahra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
3 views

DS 02 Array List

Array List ppt

Uploaded by

kinshahra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

Data Structure

Video Lecture

Lecture No. 2

Array List
Engr. Rashid Farid Chishti
http://youtube.com/rfchishti
http://sites.google.com/site/chis
hti International Islamic University H-10, Islamabad, Pakistan
Implementing Array List
 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:
Index No. 0 1 2 3 4 5 6 7 Size
Data 2 6 8 7 1 8

 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’.
Index No. 0 1 2 3 4 5 6 7 Size

Step 1: Data 2 6 8 7 7 1 8

Index No. 0 1 2 3 4 5 6 7 Size


Step 2: Data 2 6 8 9 7 1 8
Implementing Array List
 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
 Remove(1): Removes 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 .

Index No. 0 1 2 3 4 5 6 7 Size

Step 1: Data 2 6 8 9 7 1 8

Index No. 0 1 2 3 4 5 6 7 Size


Step 2: Data 2 8 9 7 1 8
Implementing Array List
 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
 Find(9): Find a Number 9 from Array List.

void Find(int Data_to_Search)


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

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

List List::copy (){ void List :: remove ( int pos ){


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

You might also like