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!\n");
    }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 \nBefore: ", pos);
PrintList(temp);

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

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

Solution 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. */
}

Solution 2

Removing a given node n from a singly-linked list can be boiled down to this operation:

• Set the pointer that points to n to point instead to n->next.

You can break this down into two operations:

• Find the pointer that points to n;
• Set that pointer to n->next.

The complication arises because the pointer that points to n might either be the p->next field of the previous node in the list, or the head pointer (if n is the first node in the list).

Your code does not appear to be complete - it doesn't ever set the ->next field of any node to anything, so it's hard to say what's actually wrong.

Solution 3

// Remove list's node located at specified position.
// Arguments:
//  head -- list's head
//  pos -- index of a node to be removed (1-based!!!)

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

    struct node* node;
    struct node* prev;
    int length;
    int i;

    printf("DeleteNode: position = %d \nBefore: ", pos);
    PrintList(head);

    // Check position's lower bound. Should be >= 1
    if(pos <= 0) { //node does NOT exist
        printf("ERROR: Node does not exist!\n");
        return head;
    }

    // Seek to the specified node, and keep track of previous node.
    // We need previous node to remove specified node from the list.

    for(i=1, prev = 0, node = head; i < pos && node != 0; i++) {
        prev = node;
        node = node->next;
    }

    // Out of range
    if(0 == node) {
        printf("ERROR: Index out of bounds!\n");
        return head;
    }

    // @node points to a list's node located at index pos 
    // @prev points to a previous node.

    // Remove current node from the list.
    if(0 == prev) {
        head = node->next;
    }
    else {
        prev->next = node->next;
    }
    free(node);

    return head;   
}

Solution 4

Your DeleteNode doesn't delete a node, it removes pos nodes from the front of the list. So you're trying to remove 9 items from a list that only contains 6, resulting of course in an empty list (NULL). Also, your code is overly complex and contains remnants of previous attempts. Please don't do that to yourself or to us; provide simple clean code and it will be easier to understand and to fix.

View more solutions

Comments

[Grant]

I appreciate your answer but it is unfortunately not helping me understand why the code I wrote isn't working...

[Clark Gaebel]

You're thinking about it wrong. The loop is not only ugly, it leads to more confusion than it's worth. Scrap it. This is best-represented with recursion, and leads to a three-line solution.

[Grant]

I understand that it is an ugly way to do it. But it would help me to understand why the loop isn't working. I know that in the recursive method we are moving the head pointer to the next pointer each time we pass to the recursive method in order to go through the list and when we get to where i finally == 0 we have found our position. I do understand that. Again just trying to understand why my loop isn't properly working

[Clark Gaebel]

I'll tell you, but you have to promise not to use the loop in your homework. My eyes are burning.

[Grant]

Alright deal. If you show me where my loop went wrong I will write my own recursive method since I typically don't use recursion! I'll even update the question to reflect what was wrong with my loop and how to fix it as well as use the better alternative

[caf]

@Clark Gaebel: Well, it's often the case that one wants to remove a node from the list, but retain the node itself for other purposes (perhaps to add to a different list). I consider disposing of the node itself to be a conceptually different operation.

[Alex Kotliarov]

No, it does not. The procedure disconnects node from the list, and returns this node to the caller. Caller will release the node. At least this is what original code does: returns the disconnected node. Anyway, the purpose was to demonstrate implementation of a loop.

[Clark Gaebel]

Look at the use case. The original code returns the updated list, not the newly-deleted node. Why else would he repeatedly assign llist from it?

[Clark Gaebel]

The name of the function is DeleteNode. I expect it to delete the node. Also, check the use case.

[Grant]

Ahh @Clark I see what you are saying about freeing the node. Hence your code using the free(). Didn't even think about needing to do that til now.

[Grant]

@Clark just noticed thanks. Now the first part about newNode->next; in my for loop I thought would be moving the pointer through because when I tried using temp = temp->next; then assigning the next pointer to temp it would come back with Null. The second code about newNode-> = Null is a typo and I didn't get that to compile haha.

[Clark Gaebel]

Are you, perhaps, looking for newNode = newNode->next? Try updating it and seeing if it works. I'm kind of remote-debugging this because I'm too lazy to open up a new tab in terminal.

[Alex Kotliarov]

@Clark: Right. Modified the code according to the "use case".

[Grant]

I tried that and I got the same problem as when I was only using temp = temp->next; and not using any NewNode. What happens when it prints it is that it takes the list ex: {1, 3, 5, 7, 9, 23} and moves 5 nodes to value 9 and deletes 1, 3, 5, 7, 9 and leaves 23, NULL. So somehow I am losing those other nodes...

[Clark Gaebel]

nitpick: You're writing in C. All indicies start at 0. Why would you start it at 1? Also, why is the position signed if unsigned values are just going to error out?

[Alex Kotliarov]

my example illustrates implementation of a loop in the context of a posted question. In the context of the question position index is 1-based.

[Jim Balter]

The OP's code removes pos elements from the front of the list (leaking them) and returns a pointer to the next node. It's pretty hard to reason something so broken to a "use case".

[Jim Balter]

@Grant I answered this below. Your so-called "DeleteNode" simply does not delete a node -- it strips pos nodes off the front of the list. To delete a node you would have to change the pointer to the pos'th node to point to the pos+1'th node, and return the head of the list -- which may have changed.