C programming Related lists delete node at position N

Question

EDIT: Revealed the problem. In addition, if you found this through Google or another search engine, here I made a mistake and how to fix it.

The deleteNode () method moved correctly through the list with the correct temperature and did not touch the head. Where I was wrong, I returned as a result of the method. I returned either temp or newNode, which is incorrect because it goes through the list until it finds a specific position. As soon as he finds that a certain position, he reassigns the next pointer -> next pointer next-> next>, which is correct, but again I returned the wrong thing. Since we moved through the list using temp / NewNode, we lost the title and we returned the position we found and everything that remained in the following positions of the list.

As we fix this, return the head (this is what is passed to the method). The reason for this is that we need 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 remove node C, go to node B using the tempo pointer, and then assign B-> next to temp-> next-> next. Skipping the C node and assigning the D node.

NOTE. (From what I know, this does not actually free up C node memory, so this is not best practice because you can cause a memory leak in this way). You should use the free () method on 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; } 

Hope this helps to understand how I fixed it.

//////////////////////////////////////////////////// //////////////////////////////////////////////////
//////////////////////////////////////////////////// ////////////////////////////////////////////////// <br > ORIGINAL POST

//////////////////////////////////////////////////// ////////////////////////////////////////////////// <br > ///////////////////////////////////////////////// /////////////////////////////////////////////////

EDIT: Note. This is homework that I spent several days (estimated 4 hours), programming that I was just stuck in this part. You can view my attempt below.

I managed to insert and delete from the beginning / end, but I can not get my delete node at position N in the linked list to work.

My psuedocode is as follows:

• LinkedList: 1,3,5,7,9,23
• LinkedList Capture
• Create a new node A = head structure
• Move through linked list to position
• Assign node node → next
• 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 a list with the values ​​3, 5, 9 after running the code. However, it replaces the first node 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 No. 2: Typo code

Thanks for any help in advance. From what I did, my problem is that I am not going through the list properly, but I'm not sure why I am not doing this.

Answer 1

In your code you have a line

 newNode->next; 

in your for loop. This operation does nothing.

You also have

 newNode-> = NULL; 

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

But in fact, do not use this loop. A linked list is one of the most basic recursive data structures. As a result, almost all algorithms that manipulate 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 this node n from a singly linked list can be reduced to this operation:

• Set a pointer that points to n , instead of n->next .

You can break it down into two operations:

• Find the pointer pointing to n ;
• Set this pointer to n->next .

The complication arises because the pointer pointing to n can be either 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 look complete - it never set the ->next field of any node to anything, so it's hard to say what it really is.

Answer 3

Your DeleteNode does not delete the node; it removes the pos nodes from the front of the list. Thus, you are trying to remove 9 items from a list containing only 6, which will naturally be in an empty list (NULL). In addition, your code is too complex and contains the remains of previous attempts. Please do not do this for yourself or for us; provide simple clean code, and it will be easier to understand and fix.

Answer 4

 // Remove list node located at specified position. // Arguments: // head -- list 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 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 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 5

Find out that your for loop does not reach the desired position. It is better to use an equal sign for the constraint with which it will work. eg.

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