data structures - C programming Linked Lists delete node at position N

Question

EDIT: Figured out the problem. Also if you found this through google or another search engine here is where I went wrong and how to fix it.

My deleteNode() method was moving through the list properly with the correct temp and keeping the head untouched. Where I was going wrong was in what I was returning as the result of the method. I was returning either temp or newNode which is incorrect because it goes through the list until it finds defined position. Once it finds that defined position it it would reassign the ->next pointer to point to the next->next> pointer which is correct but again I was returning the wrong thing. Because we had moved through the list using temp/NewNode we lost the header and we were returning the position we found and whatever was still in the next positions of the list.

How we fix this is returning the head (which is what is passed into the method). The reason why this works is because we have to understand how LinkedLists work. The pointers of each node point to the next node. Ex. we have a linked list |A|| - |B|| - |C|| - |D|| - |E|| - |F||

If we want to delete Node C we move to node B using the temp pointer and then assign the B->next to temp->next->next Thus skipping over C node and assigning D node.

NOTE: (From what I know this does not actually free the memory of C node so it isn't best practice because you can cause memory leaks this way) You should use the free() method on the C node.

Here is the code I ended up using

struct node* DeleteNode(struct node* head, int pos) {

     struct node* temp = head;
     int length = LinkedListLength(temp);
     int i;

    if(pos <= 0 || pos > length){
        printf("ERROR: Node does not exist!
");
    }else{
        if(pos == 1){
            head = head->next; //move from head (1st node) to second node
        }else{
            for(i = 1; i < pos-1; ++i){ //move through list
                    temp = temp->next;
            }
            temp->next = temp->next->next;
        }
    }
    return head;
}

Hopefully that helps understand how I went out fixing it.

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
ORIGINAL POST
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

EDIT: Note: This is a homework assignment I have spent a few days (estimated 4 hours) programming it I am just stuck on this one part. You can view my attempt below

I've been able to insert and delete from begining/end however I can't seem to get my delete node at position N in linkedlist to work.

My psuedocode looks like this:

1. LinkedList: 1,3,5,7,9,23
2. Grab LinkedList
3. Create new struct node A = head
4. Move through linkedlist until position
5. Assign node to node->next
6. return linkedlist

EXAMPLE INPUT

Node structure 
int data;
struct node* next;

int values[] = {1,3,5,7,9,23};
struct node* llist = CreateList(values,6);

llist = DeleteNode(llist, 1);
llist = DeleteNode(llist, 5);
llist = DeleteNode(llist, 3);

Which should leave the llist with the values 3, 5, 9 once the code has been run However, It is replacing the first node with a 0

Actual Code:

struct node* DeleteNode(struct node* head, int pos) {

struct node* temp = head;
struct node* newNode = head;
int length;
int i;

printf("DeleteNode: position = %d 
Before: ", pos);
PrintList(temp);

if(pos <= 0){ //node does NOT exist
    printf("ERROR: Node does not exist!
");
}else{ //node DOES exist
    length = LinkedListLength(temp);

    if(length < pos){ //if length < position Node does not exist
        printf("ERROR: Node does not exist!
");
    }else{
        if(pos == 0){
            newNode = temp->next;
        }else if(pos == 1){
            newNode = temp->next;
        }else{
            for(i = 1; i < pos; i++){
                printf("i = %d
", i);
                temp = temp->next;
                newNode->next;
            }
            if(temp->next == NULL){
                newNode = NULL;
            }else{
                newNode = temp->next;
            }
        }
    printf("After: ");
    PrintList(newNode);
    printf("
");
    }
}
return newNode;
}

EDIT #2: Code typo

Thanks for any help in advance. From what I have concluded my problem is that I am not moving through the list properly but I am unsure as to why I am not.

Answer 1

In your code, you have the line

newNode->next;

in your for loop. That operation doesn't do anything.

You also have

newNode-> = NULL;

which is not valid C, and I have no idea how you got that to compile.

But really, don't use that loop. A linked list is one of the most basic recursive data structures. As a result, almost all algorithms manipulating them are most elegant as a recursive solution.

typedef struct node node_t;

node_t* delete_at_index(node_t* head, unsigned i)
{
    node_t* next;

    if(head == NULL)
        return head;

    next = head->next;

    return i == 0
             ? (free(head), next)                                 /* If i == 0, the first element needs to die. Do it. */
             : (head->next = delete_at_index(next, i - 1), head); /* If it isn't the first element, we recursively check the rest. */
}