Operation on Linked List for Data Structure in C Language

Operation on Linked List

Traversing: To visit all the node of a linked list, start from the ROOT and visit first element and from the first element with the help of link field visit the second element, similarly visit all the element till the last node. The last node is recognized by a NULL address in it link field. So, set a pointer variable PTR with ROOT. Process PTRINFO and update PTR by LINK of PTR i.e. PTRPTRLINK. Repeat till the PTR is NULL. The algorithm is as follow:

                    TRAVERSELL(ROOT)
                    [ROOT points to first node’s address of Linked List]
                    PTR<--ROOT
                    Repeat While PTR< >NULL
                      Apply process to PTR-->INFO
                      PTR<--PTR-->LINK
                    [End of while]
                    Exit.
Algorithm to print the contents of a linked list:
                   TRAVERSELL(ROOT)
                   [ROOT points to first node’s address of Linked List]
                   PTR<--ROOT
                   Repeat While PTR< >NULL
                     Write: PTR-->INFO
                     PTR<--PTR-->LINK
                   [End of while]
                   Exit
Recursive Algorithm to traverse a linked list:
                   REC_TRAV (ROOT)
                   [ROOT points to first node’s address of Linked List]
                   IfROOT< >NULL
                      Apply process to PTR-->INFO
                      REC_TRAV(ROOT-->LINK)
                  [End of it]
                  Eixt.

Searching: Searching is nothing but finding a node with the given information for the presence. If it is present search is successful otherwise unsuccessful. Only Linear Search is used to apply the  searching. Searching almost resembles Traversing except that if search is successful traversing is terminated otherwise the linked list is traversed till the end.  

      So, in order to do searching, get the information to be searching and set PTR with ROOT. Compare Information with INFO of PTR, if it is equal ‘search is successful’ and terminate traversing otherwise update PTR with LINK and repeat the process. Continue the operation till the end. The end is recognized by a NULL of PTR.

Algorithm for Searching:
              SEARCHLL (ROOT, IN)
               [IN is Information to search in Linked List]
               PTR<--ROOT
               Repeat While PTR< >NULL AND IN< >PTR-->INFO
                 PTR<--PTR-->LINK
              [End of while]
              If PTR-->INFO=IN Then:
                Write: ‘Search Successful’
              Else:
                Write: ‘Search Unsuccessful’
             [End of If]
             Exit.

Insertion: Adding a new node the linked list is called as Insertion. To insert a node in the linked list, first a NEW node is created. To create a NEW node, memory is requested and the memory is allocated dynamically from free pool. So NEW is made point to AVAIL and AVAIL is updated. To insert a node two situations arise. The list may be a non-ordered or an ordered non-empty linked list.

If the Linked List is non-ordered list, to insert a NEW node, an Information of a node after which the insertion is to be made is given. So that Information is compared with every node of the list for equality, and the location LOC is found. After finding the LOC, LINK of LOC is copied to the LINK of NEW  node and LINK of NEW node and LINK of LOC is copied with NEW i.e.
NEW-->LINK<--LOC-->LINK and LOC-->LINK<--NEW.

If the Linked List is an ordered list, to insert a NEW node, the Information of NEW node is compared with   the Information of every node of the list. When the Information of the node of the list is greater, it is the     location LOC. The NEW  node is to be placed at that LOC.So in this case a TEMP variable is used to store the previous node’s address so that LINK of TEMP gives LOC. Now to insert the node, LINK of  NEW is copied with LOC and LINK of TEMP is copied with NEW. i.e.
 NEW-->LINK<--LOC and TEMP-->LINK<--NEW.

Array Classification in C Language with Declaration

Array in computer programming is used to store data items in a list, that may of any type. The array can be classified based on how the data items are arranged for human understanding. We have discussed about the concept of array, in this article we will classify an array.

The following figure shows the classification of the array:

Single dimensional arrays

A single dimensional array (also called one dimensional array) is a linear list consisting of related and similar data items. In memory, all the data items are stored in contiguous memory locations one after the other. Pictorial representation of single dimensional array is shown below:

Here, all the items are arranged in a row. It is called 'row major' arrangement. Instead, they can also be arranged column wise. It is called 'column major' arrangement. The memory requirement for the array depends on the type of data items stored and number of items. Let us assume, data items are of type int and assume that int takes 2 bytes (in majority of PCs size of integer will be 4 or 8 bytes). Since 5 elements are stored and the size of int is 2 bytes, the memory required for the array is 10 bytes. If the size of integer is 4 bytes, the array uses 40 bytes of memory and so on in general

Memory for array – n * sizeof (data type)

Where

• n  is the number of data items
• data type  the data type of data items

An array has the following basic properties:

• The data items (called elements) stored in the array should be of the same data type. The data items are stored contiguously in memory with subscript of the first item always 0 (zero).
• Each data item is accessed using the same name long with different subscript.
• The subscript or index of the array is always an integer.

Declaration of single dimensional arrays:

We know that all the variables are declared before they are used in the program. Similarly, an array must be declared before it is used. During declaration, the size of the array has to specify. The size used during declaration of the array informs the compiler to allocate and reserve the specified memory locations. A single dimensional array in C can be declared using the following syntax:

data_typearray_name[expression];

where

• data_type – can be a basic data type such as int, float, char, etc.
• array_name – is the name of the array
• expression – should be evaluated to a positive integer only. It can also be an integer constant. The expression should be enclosed within square brackets ‘[]’.

Note: Expression such as 10 or 10+2 is allowed. No variables are allowed in expression, for example, 10+b is not allowed because b is a variable.

For example, consider the following declaration statement: int arr[10];
The compiler reserves 10 locations (i.e. 2 *10 bytes) for the array arr. In each of the location we can store an integer value. The memory allocated by the compiler is, pictorially represented as:

How to Perform Array Initialization in C language

After declaration of arrays, the process of initialization starts in computer programming. Array initialization in C may be perform in many ways will be discuss in this article. C programming provides to let the programmer initialize the array to specific values when it is declared, when it is required or etc. Each option have its own examples described in the article.

Initialization of all specified locations

Arrays can be initialized at the same time of declaration when their initial values are known in advance. Array elements can be initialized with data items of type int, char, float, etc.

int arr[5] = {15, 45, 85, 96, 69};

During compilation, 5 contiguous memory locations are reserved by the compiler for the array arr and all these locations are initialized as shown below:

If the size of an integer is 2 bytes, 10 bytes will be allocated for the array arr. Lets discuss another initialization

int arr[5] = {15, 58, 98, 89, 65, 54, 55, 25, 85};
This declaration will notify an error with a message Number of initial values are more than the size of the array arr

char str[7] = {'P', 'R', 'O', 'G', 'R', 'A', 'M'};

During compilation, 7 contiguous memory locations are reserved by the compiler for the variable str and all these locations are initialized as shown below:

In fact in place of character, ASCII values are stores in the memory. Since a character occupies 1 byte, 8 bytes will be allocated for the variable str.

Partial Array Initialization

C language also provides partial array initialization. If the number of values to be initialized is less than the size of an array, then the elements are initialized in order from 0th location. The remaining locations will be initialized to zero automatically. For example, consider the partial initialization shown below:

int arr[5] = {56, 76, 98};

Even though compiler allocates 5 memory locations, using this declaration statement, the compiler initialized first three locations with 56, 76 and 98. The next set of memory location are automatically initialized to 0's by the compiler as shown below:

Initialization without Size

Consider the declaration along with initialization shown below:
char str[] = {'P', 'R', 'O', 'G', 'R', 'A', 'M'};

In this declaration, even though we have not specified exact number of elements to be used in array str, the array size will be set to the total number of initial values specified. So, the array size will be set to 7 automatically. The array str is initialized as shown below:

String Initialization

Consider the declaration with string initialization:

char str[] = "PROGRAM";

The array str is initialized as shown below:

Even though the string "PROGRAM" contains 7 characters, because it is a string, it always ends with NULL character '\0'. So, the array size is 8 bytes i.e. string length + 1 byte for NULL character.

char str[8] = "PROGRAM"; is Correct, size of the array is string length + 1 byte for NULL character.
char str[7] = "PROGRAM";  is Wrong, size of the array should be minimum 8.

For string initialization, usually the programmer prefer the following declaration:
char str[] = "PROGRAM";

Reading and Writing Single Dimensional Array

How to Read and Write Single Dimensional Array in C Language

In Computer Programming, it is very easy to read or write variables by following some of the syntaxex listed in the rules. While programming in C, as discussed in earlier article, single dimensional array have such a simple declaration, initialization and now read and write syntax.

Consider the declaration shown below:

int arr[5];

Here, 5 memory locations are reserved and each item in the memory location can be accessed by specifying the index as: arr[0] through arr[4], we can access 5 data items. What, if there are n no. of items to be stored in the array.

Note: In general, using arr[0] through arr[n-1] we can access n data items of an array.

The n data items are read from the keyboard using the scanf() function as shown below:

scanf("%d", &arr[0]);

scanf("%d", &arr[1]);

scanf("%d", &arr[2]);

……………………………

……………………………

scanf("%d", &arr[n-1]);

In general syntax of scanf("%d", &arr[i]) i may be valued as 0, 1, 2, 3, ……., n-1. So, in C language, if we want to read n data items from the keyboard, the following looping statement can be used:

for(i=0; i<n; i++)

{

   scanf(“%d”,&arr[i]);

}

Similarly, to display n data items stored in the array, replace scanf() by printf() statement as shown below:

for(i=0; i<n; i++)

{

   printf(“%d”,arr[i]);

}

Now, write a small C program to read n elements from the keyboard and to display those same n elements on to the screen.

main()

{

  int n, i, arr[10];

  clrscr();

  printf("Enter the value of n:");

  scanf("%d",&n);

  printf("Enter n elements here:\n");

  for(i=0; i<n; i++)

    {

       scanf("%d",&arr[i]);

    }

 for(i=0;i<n;i++)

   {

       printf("The entered elements are :%d\n", arr[i]);

   }

getch();

}

The above program, when run, will show the following output screen:

Linear Linked List for Data Structure in C language

  Linear Linked List

Creation:

           External pointer ROOT is used to store  the address of the first node of the Linked List. So initially when the list is empty the ROOT contains a NULL (0) address.

  

When the first node is created dynamically memory is allocated to it. The address of that first node is store in ROOT. Another pointer variable TEMP is also used to store the address of first node. The pointer variable TEMP is used to point every time to the current node created so that to store the address of first node all the

time.

 

            When next node is created, the LINK of the FIRST node is stored with its address. As TEMP points to FIRST node TEMP’s LINK field is copied with new node’s address and TEMP is updated to point to new node.

Similarly all the node are added to the linked list.

Algorithm to create a linear linked list.

      CREATELL
      ROOT<--  NULL
      CHOICE<--‘Y’
      Repeat While CHOICE=’Y’
        If AVAIL=NULL Then:
          Write:’Memory Allocation Error’; Exit.
        Else:
         NEW<-- AVAIL
         NEW--> LINK<-- NULL
         NEW--> INFO<-- Information
         [Information is the data to be stored in linked list]
         AVAIL<-- AVAIL--> LINK
       [End of it]
       If ROOT=NULL Then:
         ROOT<-- NEW
         TEMP<-- NEW
      Else:
        TEMP--> LINK<-- NEW
        TEMP<--  NEW
      [End of it]
      Write: ‘Do you want to add another node?(Y/N)’
      Read: CHOICE
  [End of while]
Exit.

C Program to create unordered Singly Linked List:
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct node
{
int info;
struct node *link;
};typedef struct node sn;
main()
{
 sn *root, *temp, *new; char choice=’y’;
 root=NULL;
 while(choice==’y’)
 {
 new=(sn*)malloc(sizeof(sn));
 if(new==NULL)
 {
 printf(“Memory allocation error…”); exir(0);
 }
 new->link=NULL;
 printf(“\nEnter node information :”);
 scanf(“%d”,&new->info);
 if(root==NULL)
 {
  root=new;      temp=root;
  }
else
 {
  temp->link=new;  temp=new;
 }
  printf(“Do you want to continue…(y/n)”);
  choice=getche();
 }
 printf(“\nThe Singly linked list is:\n\n”);
 temp=root;                /*temp pointer is reused */
 while(temp!=NULL)
 {
 printf(“%d”,temp->info);   temp=temp->link;
 }
}

Introduction of Free Pool Data Structure in C Language

Free Pool

         Dynamically the memory is allocated to the requesting data structure from an area of the main memory called Free Pool. If no cell is free, then no memory is allocated, results in memory allocation error. The dynamically created memory, when it is deleted, is periodically collected by the Operating System and added to the Free Pool. This process of adding deleted, unwanted, memory is called as “Garbage Collection”.

        The free pool in the main memory is treated as an empty linked list and it is called as AVAIL linked list. AVAIL is an external pointer similar to ROOT of a linked list, contains the address of the first free node of the AVAIL linked list. AVAIL address is allocated to NEW node when a new node is created means when memory for a new node is allocated i.e. when memory is requested. After the allocation of AVAIL address to NEW node, AVAIL is updated to point to the next free node of the AVAIL linked list. It can be shown by means of the below algorithmic notation’s statements.
                                       NEW <--- AVAIL
                                      AVAIL<--- AVAIL---> LINK
                AVAIL--->  LINK mean the LINK part of AVAIL node(---> is an arrow operator to access field of a struct pointer). INFO, the information part of node to be created or added to the list is copied to the INFO part of NEW node, NEW     INFO. Then the NEW node can be used for the purpose.

If a node is to be allocated with a new address, NEW is allocated with the address 402 pointed by AVAIL. So NEW points to 402 and INFO part of it is copied with the information to be stored in the node. The LINK part of it is initially copied with 0, an invalid address. In the mean time the AVAIL is updated to point to the next free node i.e. AVAIL  is incremented to point to the location (address)505.

How to Use and Declare Two Dimensional Array in C Language

Introduction

The elements of the arrays that explain or represent two characteristics are called two dimensional arrays in context of computer programming. Arrays with one set of square brackets '[]' are single dimensional arrays. Arrays with two sets of square brackets '[][]' are called two dimensional arrays and so on. Arrays with two or more dimensions are called multi-dimensional arrays. It is responsibility of the programmer to specify the number of elements to be processed within square brackets. For example,

int arr[5];       
int arr1[5][5];
int arr2[5][5][5];

In the above declaration the array named with arr is declared as one dimensional array, the array named with arr1 is declared as two dimensional arrays and the array named with arr2 is declared as three dimensional arrays.

A two dimensional array is used when data items are arranged row-wise and column-wise in a tabular form. Here, to identify a particular item or element, we have to specify two indices (also called subscripts). The first index identifies the row number and second index identifies the column number of the item or element.

Declaration of two dimensional arrays

A two dimensional array must be declared before it is use along with row-size and column-size of the array. The size used during declaration of the array, is useful to reserve the specified memory locations. A two dimensional array in C can be declared using the following syntax:

data_type array_name[exp1][exp2];

Where

• data_type – can be a basic data type such as int, float, char etc.
• array_name – is the name of the array
• exp1 and exp2 – are constant or ordinal expression. The expression should be enclosed within square brackets ‘[]’. No variables are allowed inside the brackets. Should be evaluated to a positive integer only. It can also be an integer constant.

Note: exp1 specifies rows to be accessed using first index or subscript and exp2 specifies columns to be accessed using second index or subscript.

Consider the following declaration:
int arr[3][3];

The array arr has two sets of square brackets '[][]' and hence it is a two dimensional array with 3 rows and 3 columns. This declaration informs the compiler to reserve 9 locations (3 x 3 = 9) contiguously one after the other. Total memory reserved is 9 x 2 = 18 bytes. The pictorial representation of this arr array is shown below:

Initialization of Two Dimensional Array