Array data structure

##
##  linear VS non-linear
##

array, LL, stack, queue are considered linear.
tree, hash, graph are non-linear.

##################
###   array   ####
##################

an array strucutre is the most basic data structure.

- used for handling a series of data.
- indexed in contiguous memory space. useful for random access. but not suitable when you need to resize, or insert/remove elements in the middle, etc. (more discussion to follow in comparision with linked list)
- need to make sure the access is within the allocated scope. otherwise null ptr exception aka segmentation fault.
- often used as an underlying structure for more complex data structure like stack, queue, hash, tree, etc.

there are a few ways to declare, and initialize. but ultimately this sort of detail comes down to the nuance of each language's syntax/standards.

e.g.
--------------------
int arr[5];

for (int i = 0; i < 5 ;i++)
arr[i] = i;
--------------------
int arr[5] = {1,2,3,4,5};
--------------------
int arr[] = {1,2,3,4,5};  // this will automatically make arr size 5
int arr2[5] = {3};        // this will only initialize the first elem
--------------------
int* arr = new int[5];                // C++
for (int i = 0; i < 5 ; i++, arr++ )
*arr = i;                          // since arr is essentially just a pointer to a contiguous chunk of mem, we can treat it as such and do *arr, arr++
--------------------

###################################
###   multi dimensional array   ###
###################################

int arr[5][3];

this means, we have a size=5 array, and each element is a size=3 array.

----------------------
arr [0][1][2][3][4]
[1][1][1][1][1]
[2][2][2][2][2]
----------------------

still it is just a contiguous chunk.

arr[0][0]
arr[0][1]
arr[0][2]
arr[1][0]
arr[1][1]
...        // and so on.

------------------ // test.cpp
#include <iostream>
using namespace std;

int main()

int arr[5][3];
for(int i =0; i< 5; i++)
for(int j =0; j< 3;j++)
cout << &arr[i][j] << endl;

------------------

======>  will print the below. notice it's all 4bytes increment.
( int = 4bytes in this case. would be 1-byte increment if we used char.)

0x7fff26242d60
0x7fff26242d64
0x7fff26242d68
0x7fff26242d6c
0x7fff26242d70
0x7fff26242d74
0x7fff26242d78
0x7fff26242d7c
0x7fff26242d80
0x7fff26242d84
0x7fff26242d88
0x7fff26242d8c
0x7fff26242d90
0x7fff26242d94
0x7fff26242d98

=========> this means, depending on the cache scheme, accessing row-by-row is faster than column-by-column.

if you wanna initialize, do it like below

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

====> three dimensional array is essentially the same.

########################
###   jagged array   ###
########################

there may be a situation in which you may want to declare non-recutangular array like below.
it is called a jagged array.

---------------------
arr [0][1][2][3][4]
[1][1][1][1][1]
[2]   [2][2][2]
[3]   [3]   [3]
[4]
---------------------

===>  the most common usage is when you have an array of names.

e.g.

--------------------------------  //  jagarr.cpp
#include <iostream>
#include <cstring>     // needed for strcpy
using namespace std;

int main()

char* name[2];

name[0] = new char[4];
name[1] = new char[5];

name[0][0] = 'k';
name[0][1] = 'e';
name[0][2] = 'n';
name[0][3] = 0;

strcpy(name[1],"will");

cout << name[0] << endl;    //  ken
cout << name[1] << endl;    //  will

return 0;

--------------------------------

#################################
####    vector/ArrayList     ####
#################################

an array that grows(shrinks) as you add(del) elements is called vector(in C++) or ArrayList(in java).
it is convenient. a single add/del operation can be O(n) but amortized complexity can be O(1) if you double up/down the size as you resize.

shrink(resizing down) is not mandatory, and in fact, it doesnt have to happen when LF<0.5, maybe resize only when LF<0.25, to avoid too much thrashing between resizing up and down.

##########################
####  size of array   ####
##########################

int input[] = {2,4,8,1,23,5,2,7,3,9};  // 10 elems

int asize = sizeof(input);              // 40
size      = sizeof(input)/sizeof(int);  // 10

NOTE: this sizeof() trick can only be used within the immediate scope of the array declaration. e.g. below code is illegal.
-------------------------
#include <iostream>
using namespace std;

void print(int a[])                      // int a[] will be interpreted as (int* a)

int size = sizeof(a)/sizeof(a[0]);   // sizeof(a) will be the size of a pointer to an interger, which is 4 or 8
for(int i = 0; i< size; i++)         // so int size will be always 1
cout << arr[i] << ' ';
cout << endl;

int main()

int arr[5] = {11,22,33,44,55};
cout << sizeof(arr) << endl;      // 20
cour << sizeof(arr[0]) << endl;   // 4   (on 32-bit machine)
print(arr);
return 0;

-------------------------

unfortunately, there is no certain way to determine the array size. so you have to pass the size as a parameter if you are passing an array to a function.

e.g.
-----------------------------------
#include <iostream>
using namespace std;

void print(int a[],int size)

for(int i = 0; i< size; i++)
cout << arr[i] << ' ';
cout << endl;

int main()

int arr[5] = {11,22,33,44,55};
int size = sizeof(arr)/sizeof(arr[0]);
print(arr,size);
return 0;

---------------------------------------------

(ref)
http://za.toypark.in/html/2009/12-22.html
https://www.jpcert.or.jp/sc-rules/c-arr01-c.html
http://www.pickatutorial.com/tutorial/csharpprogramming/csharp_arrays.htm  // c# but a very simple example of jagged array

1. 2014-06-06 00:51:21 |
2. Category : data_structure
3. Page View: