How would you find the size of structure without using sizeof()?

struct MyStruct
{
int i;
int j;
};

int main()
{
struct MyStruct *p=0;
int size = ((char*)(p+1))-((char*)p);
printf("\nSIZE : [%d]\nSIZE : [%d]\n", size);
return 0;
}

program to check if the stack grows up or down

Try noting down the address of a local variable. Call another function with a local variable declared in it and check the address of that local variable and compare!.


#include < stdio.h >
#include < stdlib.h >

void stack(int *local1);

int main()
{
int local1;
stack(&local1);
exit 0;
}

void stack(int *local1)
{
int local2;
printf("\nAddress of first local : [%u]", local1);
printf("\nAddress of second local : [%u]", &local2);
if(local1 > &local2)
{
printf("\nStack is growing downwards.\n");
printf " Stack is growing to Lower address" );
}
else
{
printf("\nStack is growing upwards.\n");
printf " Stack is growing to Higher address" );
}
printf("\n\n");
}

How do you reverse a single linked list without using any C pointers?

One way is to reverse the data in the nodes without changing the pointers themselves. (push the elements into the stack and copy the elements into the linked list in sequential order i.e., nothing but reversing a single linked list without using pointers)

The other way is to create a new list from the existing list in the reverse order.

to implement the heterogeneous linked list in C language, what pointer type will you use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

C program to free the memory allocated to the nodes of a linked list

This is the wrong way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = listptr->next)
{
free(listptr);
}


If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can cause unpredictable results!



This is the right way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = nextptr)
{
nextptr = listptr->next;
free(listptr);
}
head = NULL;


After doing this, make sure you also set the head pointer to NULL!

Is Binary search possible on a linked list?

The answer is yes, you can write a C program to do this. But here the question is, do you really think it will be as efficient as a C program which does a binary search on an array? 

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loose the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

C program to return the nth node from the end of a linked list.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)


STEP 1 : 1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2 : 1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10



Now, start the second pointer (ptr2) and keep on incrementing it along with the first pointer (ptr1) until first pointer(ptr1) reaches the end of the LL.


STEP 3 : 1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)


So here you have  the 6th node from the end pointed to by the ptr2



c code for the above algorithm:

struct node
{
int data;
struct node *next;
}mynode;


mynode * nthNode(mynode *head, int n /*pass 0 for last node*/)
{
mynode *ptr1,*ptr2;
int count;

if(!head)
{
return(NULL);
}

ptr1 = head;
ptr2 = head;
count = 0;

while(count < n)
{
count++;
if((ptr1=ptr1->next)==NULL)
{
//Length of the linked list less than n. Error.
return(NULL);
}
}

while((ptr1=ptr1->next)!=NULL)
{
ptr2=ptr2->next;
}

return(ptr2);
}

C program to remove duplicates from a linked list

First sort the linked list.

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be noted before the deletion.

// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head) 
{
struct node* current = head;
if (current == NULL) return; // do nothing if the list is empty

// Compare current node with next node
while(current->next!=NULL) 
{
if (current->data == current->next->data) 
{
       struct node* nextNext = current->next->next;
       free(current->next);
       current->next = nextNext;
}
else 
{
       current = current->next; // only advance if no deletion
}
}
}

How to read a singly linked list backwards (or) how to reverse a single linked list

solution1--reverse the list and read it..

struct node* reverseList(struct node* head)
{
struct node *ptr1,*ptr2,*first,*last;
if(head==NULL)
    return NULL:
first=head;
while(head!=NULL)
{
    ptr1=head;
    ptr2=head->link;
    if(first==head)
         ptr1->link=NULL;
  
    ptr2->link=ptr1;
    head=ptr2;
    if(head->link==NULL)
        first=head;
}
return first;
}


solution2 : push the elements into the stack and then read the elements

C program to determine the number of elements in a tree (or) size of the tree

//address of root node of the tree is passed to this function

int treeSize(struct node* node) 
{ 
if (node==NULL) 
{ 
return 0; 
} 
else 
{ 
return (treeSize(node->left) + treeSize(node->right) + 1); 
} 
}

C function to delete a tree

deleteTree(struct node* pNode)
{
if (pNode != NULL)
{
clear(pNode->left);
clear(pNode->right);
free(pNode);
}
}

C function to determine whether the given two trees are identical or not

//where a and b are the pointer to the root nodes of the two trees

int identical(struct node* a, struct node* b) 
{ 
  if (a==NULL && b==NULL)
  {
    return 1;
  } 
  else if (a!=NULL && b!=NULL) 
  { 
  return (a->data == b->data && identical(a->left, b->left) && identical(a->right, b->right)); 
  } 
  else return 0; 
}

//if the return value is 1 then the trees are identical otherwise not

C function to find the maximum value in a binary search tree.

//many will have confusion in the below pointer declaration
//int *ptr and int* ptr both are same


int maxValue(struct node *root) 
{ 
struct node *current = root; 

while (current->right != NULL) 
{ 
current = current->right; 
}
return(current->data); 
} 

C function to find the mininum value in a binary search tree.

int minValue(struct node* node) 
{ 
struct node* current = node; 

while (current->left != NULL) 
{ 
current = current->left; 
}

return(current->data); 
} 

C function to compute the maximum depth in a tree

int maxDepth(struct node* root) 
{ 
int leftDepth = 0;
int rightDepth = 0;
if (root==NULL) 
{ 
return 0; 
} 
else 
{ 
leftDepth = maxDepth(root->left); 
rightDepth = maxDepth(root->right); 
if (leftDepth > rightDepth)
              return(leftDepth+1); 
else
              return(rightDepth+1); 
} 
}

C program to create a mirror copy of a tree (left nodes become right nodes and right nodes become left nodes as well)

//The structure for the following code

typedef struct tree
{
int value;
struct tree *left,*right;                           //known as self-referential pointers
} mynode;



//The following C code will create a new mirror copy tree.

mynode *copy(mynode *root)
{
mynode *temp;

if(root==NULL)return(NULL);

temp = (mynode *) malloc(sizeof(mynode));
temp->value = root->value;

temp->left = copy(root->right);
temp->right = copy(root->left);

return(temp);
}


//The following C code will only print the mirror of the tree

void tree_mirror(mynode *node) 
{ 
mynode *temp;

if (node==NULL) 
{ 
return; 
} 
else 
{ 
tree_mirror(node->left); 
tree_mirror(node->right); 

// Swap the pointers in this node 
temp = node->left; 
node->left = node->right; 
node->right = temp; 
} 
}

//after execution of above method, print the tree