C/C++ Program to create a Linked List [DEVCPP/GCC]

PROGRAM

//Program to create a Linked List and to insert and delete elements by value

#include <iostream>
#include <cstdlib>

using namespace std;

struct node
{
int val;
struct node *next;
};

struct node *temp,*stemp,*ttemp,*first;

void Insert(int item)
{
temp= new node;
temp->val = item ;
temp->next= NULL ;

if(first==NULL)
{
first=temp;
}
else
{
stemp = first;
while(stemp->next!=NULL)
{
stemp=stemp->next;
}
stemp->next=temp;
}
cout<<"\nELEMENT INSERTED: "<<item;
}

void Delete(int item)
{
bool found=false;

if(first==NULL)
{
cout<<"\nLINKED LIST IS EMPTY!";
}
else
{
ttemp=stemp=first;
while(stemp->next!=NULL)
{
if(stemp->val==item)
{
found=true;
break;
}
ttemp=stemp;
stemp=stemp->next;
}

if(found)
{
if(stemp->next != NULL)
{
ttemp->next=stemp->next;
stemp->next=NULL;
}
else
{
ttemp->next=NULL;
stemp->next=NULL;
}
delete stemp;

cout<<"\nELEMENT DELETED!";
}
else
{
cout<<"\nELEMENT NOT FOUND!";
}
}
}

void Display()
{
if(first==NULL)
{
cout<<"\nLINKED LIST IS EMPTY\n";
}
else
{
stemp = first;
cout<<"\n\nLINKED LIST\n";

                    while(stemp!=NULL)
{
cout<<stemp->val<<" ";
stemp=stemp->next;
}
cout<<endl;
}
}

int main()
{
Insert(1);
Insert(2);
Insert(3);

  Display();

Delete(2);
Display();

Insert(5);
Display();

return 0;
}

OUTPUT

C++ Program to sort elements using Quick Sort [DEVCPP/GCC]

QUICK SORT

It is also called Partition Exchange sort. As the name suggests Quick Sort sorts very quickly. When implemented in a proper way, it can be two or three times faster than its competitors mergesort and heapsort. It is based on the rule of Divide and Conquer. It was developed by Tony Hoare in 1959.

This algorithm divides the list into 3 parts:

1. Elements less than the pivot element.
2. Pivot element.
3. Elements greater than the pivot element.

Pivot (Special value) may be the first, middle or last element, pivot divides the array into two parts after each pass, values on the left hand side of pivot are less or equal to pivot and those on the right hand side are greater than the pivot value.

EXAMPLE

PROGRAM

#include <iostream>

using namespace std;

void Quick_sort(int a[], int lb, int ub)

{

                int L,R,X,temp; 

   

                if(lb>=ub)

                    return; 

                               

                L=lb;

                R=ub;

                X=a[lb]; 

               

                while(L<R)

                {

               

                    while(a[L]<=X && L<R)

                                    ++L;

                               

                     while(a[R]>X)

                                    --R; 

                                               

                      if(L<R)

                      {

                             temp=a[L];

                             a[L]=a[R];

                             a[R]=temp;

                       } 

                }        

               

                a[lb]=a[R];

                a[R]=X; 

               

                Quick_sort(a,lb,R-1);

                Quick_sort(a,R+1,ub);

}

int main()

{

                int a[10],i;

                cout<<"ENTER THE ELEMENTS:\n";

               

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

                {

                    cin>>a[i];

                } 

               

                Quick_sort(a,0,9);

               

                cout<<"SORTED ELEMENTS:\n"; 

               

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

                {

                    cout<<a[i]<<" ";

                } 

}

OUTPUT

C++ Dynamic Memory Allocation of Arrays

We have already discussed Dynamic Memory Allocation in C style through malloc, calloc and realloc : C++ Program to illustrate memory allocation with malloc, calloc and realloc .

The static memory allocation of array leads to inefficient use of memory. Moreover, it is statically bounded and can not be allocated on demand at runtime. Some programs require memory to be allocated based on user input. This leads to the need of dynamic memory allocation for arrays.

MEMORY ALLOCATION

In C++, Dynamic Memory Allocation takes place with the help of two operators i.e. new and delete. The general syntax for memory allocation goes as:

pointer = new datatype [ number_of_elements ] 

The above expression is used to allocate a block of elements of type datatype. The number_of_elements is an integer value which denotes the number of elements of the array. A pointer to the beginning of new memory block is returned.

For instance,

int *list;
list = new int [5];

In the above scenario, the system will dynamically allocate memory for 5 integer type elements and return a pointer to the beginning of this block to list.

Once the memory is allocated, list will behave similarly as a static array of 5 integer elements. The elements can be accessed as list[0], list[1], ... list[4].

The dynamic memory allocation takes place from the system heap memory. As we know that the system memory is limited and may exhaust, thus the request for dynamic memory allocation may fail. 

One way to identify whether memory allocation is successful or not is through the use of a special object nothrow defined in the <new> header. 

list = new (nothrow) int [5];

By using nothrow, if the memory allocation fails, a null pointer is returned to the pointer and the program continues its execution.

For instance,

int *list;
list = new (nothrow) int [5];

if( list == nullptr )
{
     // MEASURES IF ALLOCATION FAILS
}

// REST OF CODE

MEMORY DEALLOCATION

After the use of memory, the allocated memory can be freed so that is can be used for further requests of dynamic memory. For this purpose, delete operator is used whose syntax is as follows:

delete [] pointer;