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.

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

Answer 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.

Answer 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;   
}

Answer 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.

Answer 5

Figured out your for loop isn't reaching the desired position you wanted. Better use equal to sign for the constraint it will work. e.g.

for (i=1;i<=position-1;i++)
{

}