Delete node of a singly linked list

[lastbencher]

I made the following functions for deleting a node of a singly linked list.
1. Can these functions be improved furthur?
2. Is it necessary to free the memory of the node that is deleted?

nodep deleteByValue(nodep p, int value) {
    nodep temp = p;

    if(temp->data == value) return temp->next;

    while(temp->next) {
        if(temp->next->data == value) {
            temp->next = temp->next->next;
            return p;
        }
        temp = temp->next;
    }
    printf("\nError: Node not found!\n");
    return p;
}


nodep deleteByPosition(nodep p, int pos) {
    nodep temp = p;
    int i = 1;

    if(pos > countNodes(p)) {
        printf("Error: Input position > Total nodes.\n");
        return p;
    }

    if(pos == 1) return p->next;

    while(i < pos-1) {
        temp = temp->next;
        i++;
    }
    temp->next = temp->next->next;
    return p;
}

I have defined the linked list as

typedef struct listNode * nodep;
typedef struct listNode {
    int data;
    nodep next;
}node;

[deceptikon]

I wouldn't include print statements in these functions, as that limits flexibility. Rather, they should return some sort of error status (NULL is a common option).

Is it necessary to free the memory of the node that is deleted?

Yes.

[Ancient Dragon]

The code you posted doesn't really delete anything, all it does is return one of the nodes in the linked list. You need to post the code that calls those two functions so that we can see what it does with the pointers. And yes, if you used malloc() to allocate memory for the nodes you will have to call free() to release that memory.

[Sokurenko]

Is it necessary to free the memory of the node that is deleted?

What do you mean deleted then ? In c if you loose pointer to some data it is called memmory leak, cause no automatic garbage collection is implemented in c. In java if all references lost then free is called, you should do it manually before loosing this pointer. For example save address of some data you whant to free to tmp variable then make previous element to point to next after tmp after your linked list is ready (does not cointain this element anymore) you let go - free(tmp). Also should check if it is first and stuff..

and yes you can return this tmp pointer bot then you haveto rename this function to cutByPosition and then use this pointer to insert somewhere else.

please whole code

[lastbencher]

Okay, thanks!

You need to post the code that calls those two functions so that we can see what it does with the pointers.

Here's the complete code.

 #include<stdio.h>

typedef struct listNode * nodep;
typedef struct listNode {
    int data;
    nodep next;
}node;


nodep insertBeg(nodep p, int val) {
    nodep temp;
    temp = (nodep)malloc(sizeof(node));
    temp->data = val;
    temp->next = NULL;

    if(p==NULL) {
        p=temp;
        return p;
    }
    temp->next = p;
    p = temp;
    return p;
}


nodep insertEnd(nodep p, int val) {
    nodep temp, P = p;
    temp = (nodep)malloc(sizeof(node));
    temp->data = val;
    temp->next = NULL;

    if(p==NULL) return temp;
    while(P->next) P = P->next;
    P->next = temp;
    return p;
}


nodep insertNode(nodep p, int val, int pos) {
    nodep temp, P = p;
    temp = (nodep)malloc(sizeof(node));
    temp->data = val;
    temp->next = NULL;

    if(pos > countNodes(p)) {
        printf("Error: Input position > Total nodes\n");
        return;
    }

    if(pos==1) {
        temp->next = p;
        p = temp;
        return p;
    }

    int i=1;
    while(i!=pos-1) {
        P = P->next;
        i++;
    }
    temp->next = P->next;
    P->next = temp;
    return p;
}


int countNodes(nodep p) {
    int count = 0;
    nodep temp = p;

    while(temp) {
        count++;
        temp = temp->next;
    }
    return count;
}


nodep deleteByValue(nodep p, int value) {
    nodep temp = p;

    if(temp->data == value) return temp->next;

    while(temp->next) {
        if(temp->next->data == value) {
            temp->next = temp->next->next;
            return p;
        }
        temp = temp->next;
    }
    printf("\nError: There is no such node.\n");
    return p;
}


nodep deleteByPosition(nodep p, int pos) {
    nodep temp = p;
    int i = 1;

    if(pos > countNodes(p)) {
        printf("Error: Input position > Total nodes.\n");
        return p;
    }

    if(pos == 1) return p->next;

    while(i < pos-1) {
        temp = temp->next;
        i++;
    }
    temp->next = temp->next->next;
    return p;
}


nodep reverseList(nodep p) {
    nodep P = NULL, N = NULL, C = NULL;
    nodep temp = p;

    while(temp) {
        C = temp;
        N = temp->next;

        C->next = P;

        P = C;
        temp = N;
    }
    return C;
}


void printList(nodep p) {
    nodep temp = p;

    printf("\n");
    while(temp) {
        printf("%d -> ", temp->data);
        temp=temp->next;
    }
    printf("NULL");
}


int main(void) {
    int choice=10;  //random value
    int pos;
    nodep head = NULL;

    printf("LINKED LIST");

    while(1) {
        printf("\n\nWhat do you want to do?\n");
        printf("1. Insert new node at beginning\n");
        printf("2. Insert new node at end\n");
        printf("3. Insert new node at a specific position\n");
        printf("4. Count the number of nodes\n");
        printf("5. Delete a node (input: value)\n");
        printf("6. Delete a node (input: position)\n");
        printf("7. Reverse the linked list\n");
        printf("0. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch(choice) {
            case 0:
                return;

            case 1:
                printf("Enter data: ");
                scanf("%d", &choice);
                head = insertBeg(head, choice);
                printList(head);
                break;

            case 2:
                printf("Enter data: ");
                scanf("%d", &choice);
                head = insertEnd(head, choice);
                printList(head);
                break;

            case 3:
                printf("Enter data and position(starting from 1): ");
                scanf("%d %d", &choice, &pos);
                insertNode(head, choice, pos);
                printList(head);
                break;

            case 4:
                choice = countNodes(head);
                printf("\nNumber of nodes = %d\n", choice);
                break;

            case 5:
                printf("Enter value: ");
                scanf("%d", &choice);
                head = deleteByValue(head, choice);
                printList(head);
                break;

            case 6:
                printf("Enter position: ");
                scanf("%d", &pos);
                head = deleteByPosition(head, pos);
                printList(head);
                break;

            case 7:
                head = reverseList(head);
                printList(head);
                break;

            default:
                printf("\nError: Wrong input!\n");
                break;
        }
    }
}

[Ancient Dragon]

Just before doing line 111 for example you need to call free() to release the memory for the deleted node.

[lastbencher]

Just before doing line 111 for example you need to call free() to release the memory for the deleted node.

If I do that, I won't be able to execute

temp->next = temp->next->next;

Did you mean to say something like this?

nodep deleteByPosition(nodep p, int pos) {
    nodep temp = p, x;
    int i = 1;

    if(pos > countNodes(p)) {
        printf("Error: Input position > Total nodes.\n");
        return p;
    }

    if(pos == 1) return p->next;

    while(i < pos-1) {
        temp = temp->next;
        i++;
    }
    x=temp->next;
    temp->next = temp->next->next;
    free(x);
    return p;
}

Just before doing line 111 for example you need to call free() to release the memory for the deleted node.

[lastbencher]

This is the function for deleting the linked list and freeing the memory.

void deleteList(nodep p) {
    nodep temp = p, x;

    while(temp) {
        x = temp->next;
        free(temp);
        temp = x;
    }
    p = NULL;
}

in main()

deleteList(head);
printList(head);

The program prints address values infinitely. I am unable to find the error. Please help.

[Sokurenko]

your head is not null ?

[lastbencher]

your head is not null ?

No. I defined the linked list in main() first, then executed the function.

nodep head = NULL;
int i = 1;

    while(i<10) {
        head = insertEnd(head, i*i);
        i++;
    }

Looks like you are assuming that head is passed by reference to deleteList() when it isn't. You're just passing a pointer to a node. If you wanted to have deleteList(x) set x=NULL after it was finished, you'd have to pass a nodep* not just a nodep. Obviously there would be some other changes to the function internally too.

void deleteList(nodep p) {
     nodep temp = p, x;
     ...
}

I am assuming that's why you are using temp as a 'copy' of p here instead of just using p itself as an iterator because you are thinking, erroneously, that that would alter the p passed to the function originally (again I mean you assume its passed by reference), but that is not the case.

So, I'm assuming you expect deleteList(head) and then printList(head) to print nothing because head should =NULL after the deleteList()? If so, then change your code like this:

void deleteList (nodep *p) {
    nodep tmp = *p;
    while(tmp) {
        nodep next = tmp->next;
        free(tmp);
        tmp = next;
    }
    *p = NULL;
}

then in your main code:

deleteList(&head);
printList(head);

Of course, that is a lot of PT for something that just needs to NULL a value. Easier to just:

deleteList(head);  /* your version */
head = NULL;  /* The list should be empty now, so head MUST be null. */
printList(head);

[sethlahaul]

Try something like this .....

void del_pos(node **ptr)
        {
            int nd,x;
            node *current,*prev=NULL;
            current=*ptr;
            printf("Enter the element to delete : ");
            scanf("%d",&x);
            if(*ptr==NULL)
                printf("\nList is empty !!!!");
            while(current!=NULL)
            {   
                if(current->info==x)
                {
                    if(current==*ptr)
                    {
                        *ptr=current->next;
                        free(current);
                    }
                    else
                    {
                        prev->next=current->next;
                        free(current);
                    }
                }
                else
                {
                    prev=current;
                    current=current->next;
                }
            }                   
            printf("\nElement deleted \n");
        }