Blog

Data Structures — 1 Types

What are Data Structures? What are the types of Data Structures.

The simplest data structure is a variable and it holds a single value at any given time, How is it declared?

The C syntax is
typename variablename [= initial value]; The typename and variablename is compulsory. The initialization part is optional. What happens if we do not initialize. The value is ‘garbage’.

A concrete example of a variable declaration is

int x=0;

int is the type name, x is the variable name and 0 is the value.

What happens when we declare int x=0,y=1;

An entry is made into the variable table.

Variable Name        Variable Type     Variable Address   Variable Value
x                                   int                         1000                          0

y                                   int                          1002                          1 

 

Variable address is some location in the RAM(Random Access Memory) of the computer. The addresses given here are symbolic.

What happens if I write x=10;? The value at address 1000 is changed to 10.

What happens if I write y=x; The value at address 1000 is copied into memory location 1002.

What is x=x+10; The value at address 1000 is copied into a temporary location. 10 is added and the new value is written back to address 1000.

What happens with x+y=10; The compiler will signal an error. The LHS in an assignment statement must always be a single memory address. The RHS can be any expression.

 

Multivalued Data Structures

A variable can hold a single value at any time. That value can be read, changed or used in some expression. What happens if we need to use many variables in a program? Processing the results of 50 students in a class. We can have 50 variables. int m1,m2,m3,….m50;
Not a very good idea. First of all its too many variables. Second, we cannot operate on these using some higher level control statement(loops for instance).

Arrays

Arrays are a collection of data of the same type stored in consecutive memory locations.

An array of 50 integers would be defined as

int a[50];

or int a[]={22,33,4,55,….};

or int a[50]={33,4,3,0,4}; We allocate space for 50 integers. Initialize if you want or leave it as garbage. The storage would look like this.

ArrayName       Index   Value  Address

a                          0            33        1000

a                           1             4          1002

a                           2             3          1004

a                            3            22        1006

a                            n            value     1000 + 2*Index

a[0],a[1], etc can be thought off as being individual variables. Writing a[0] will return 33, a[1]=10 will change the value stored at address 1003 to 10.

What happens when we access an array location, a[3] or a[n]; The address is calculated according to the formula

Address of a[n] = Base Address + Index X Size per element.

For a[3] it would be 1000 + 3 X 2 = 1006.

This  requires two constraints.

  1. All elements must have the same size. This means we must have elements of the same type.
  2. All elements must be stored contiguously.

 

Benefits of Arrays

  • Provide fast searching facility using Binary Search

Problems

  • Insertion, Updations and Deletions keeping the sorted status intact requires big data movement. This is costly in terms of Space Complexity and Time Complexity.

What type of data should be stored in arrays?

Data that is searched extensively but not modified as often.

Examples

  • List of Trains in the Indian Railways. Huge number of searches, very few changes.
  • List of branches of a bank.

 

Linked List

What is a Linked List?

There is a hostel somewhere in which a few students of Varanasi are studying. They are scattered across the hostel and do not occupy consecutive rooms. All students of Varanasi know each other and their rooms. The situation could be like this.

Room No     Name

1                     Pappu,Delhi

2                     Popat,VNS

3                      Champak, VNS

4                       Rahul, BLR

5                        Vinayak, VNS

 

Somebody, wants to meet all the Varanasi students in the hostel.

He inquires and finds that Vinayak is from Varanasi. What next?

5         Vinayak, VNS      Next:3

Vinayak tells him that the next room to be visited is 3.

3          Champak, VNS     Next:2

Popat says that there are no more students.

2          Popat, VNS           Next:None

 

This is a linked list. What happens if a new student were to come and start staying at room no 10.

20        Priyanka, VNS

Popat would point  to Priyanka
2           Popat,VNS      Next:20

Priyanka would be

20       Priyanka,VNS     Next:None

If somebody is to be inserted between Vinayak and Champak. Vinayak points to the ne entry, who then points back to Champak.

No data movement is ever needed, deletions and changes are very easy. This is perfect for situations where changes are common searches are rare.

Ideal for

  • The Reservation list of Indian Railways.

To be continued.

 

Leave a Reply

Your email address will not be published. Required fields are marked *