Etiket arşivi: linked list add in order

Linked List Addition In Order, C Language (automatically sorted )

Hi guys ,

Today ı will explain the AddInOrder function which is used for inserting item to linkedlist which will be  automatically sorted.

First of all , my function has two parameters.One of them is the list ı want to add new item and the other one is the data I desire to add. Function should return the new list .

linkedlist* AddinOrder(linkedlist* list, int data);

I am creating new item.İt will store the new data.

 linkedlist* newitem = malloc(sizeof(linkedlist));

    newitem->idata = data;
    newitem->pNext = NULL;

Then ı am checking if the list is NULL or the new data is smaller than the old one , Newitem should be the first element and second one will be the list . Because list would be sorted.

Here is the first If Visually.

if (temp == NULL || newitem->idata <= temp->idata) {
        newitem->pNext = temp;
        return newitem;
 }

first if

The other important part of code is While loop.In this loop we are defining ,where are we gonna add newitem on linkedlist.To do that, I have two while conditions. First temp->pnext != NULL ,  becouse if it will be equal the NULL , that’s mean we are the end of the List.There is no other adress to go on list. Secondly we are trying to find first bigger item than our new data.When ı see that data ,I have to stop going next linkedlist adress.Until these termination conditions are not supported , ı will keep going to the next adress.

 while (temp->pNext != NULL && newitem->idata >= temp->pNext->idata) {
        temp = temp->pNext;
    }

After while loop Finally ı found where ı will add item,Then  I have to make connections between the list and new item.

  newitem->pNext = temp->pNext;
    temp->pNext = newitem;

second

 

       Right now our function is ready.You can easly use it to add new element to linkedlist.

İf you want to compile this function , I am writing the function with all parts of it.

linkedlist* AddinOrder(linkedlist* list, int data) {

    linkedlist* temp = list
    linkedlist* newitem = malloc(sizeof(linkedlist));

    newitem->idata = data;
    newitem->pNext = NULL;

    if (temp == NULL || newitem->idata <= temp->idata) {
        newitem->pNext = temp;
        return newitem;
    }

    while (temp->pNext != NULL && newitem->idata >= temp->pNext->idata) {
        temp = temp->pNext;
    }

    newitem->pNext = temp->pNext;
    temp->pNext = newitem;

    return list;

}

You can see the result of function. I added random items to Linkedlist but when ı printed them , ı saw they are already sorted.

İf you want to calculate Big(0) of this function it will be “n” becouse there is only one loop which depends on item count.The other calculations has constant execution time. So BigO = T(n) = O(n)

Thanks for your time.

result

Reklamlar