Arrays , Link Lists, Stacks and Queues

Arrays , Link Lists, Stacks and Queues

Deliverables

Arrays Link Lists Stacks Queues

6/5/2012 7:14 PM

Copyright@

2

Arrays

Arrays are stored in contiguous memory locations and contain similar data. Position of any array element can be accessed from its index position with help of array's starting address.

An element can be accessed, inserted or removed by specifying its position (number of elements preceding it)

Vector is abstraction of array data structure, where we can access by rank.

6/5/2012 7:14 PM

Copyright@

3

Array operations

? Deletion: In operation removeAtPosition(r), we need to fill the hole left by the removed element by shifting backward n-r-1 elements A[r + 1], ..., A[n - 1]. In the worst case (r = 0), this takes O(n) time. In the average case also it is O(n).

? A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

3

10 0

-135 2

21 41 6

87 11

? Is it necessary to shift the array elements after deletion?

6/5/2012 7:14 PM

Copyright@

4

6/5/2012 7:14 PM

Deletion of -34

5 23 -34 1 81 9 123 45 2 -31

After deletion of -34

Copyright@

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download