Searching Node in List

dl324

Joined Mar 30, 2015
16,846
I do not understand how to do it in delete function post number #16.

i have a Temp pointer. I want to delete second node in code i have to find the node i want to delete.
You can't do it that way. If you pass the delete function the node that you want to delete, you need a way to update the next pointer in the node before it. Since you don't have a doubly linked list, you can't determine the node before.

With the way you seem to want to delete, you have to start at the beginning and walk the list (remembering the address of the node you last visited) and update the next pointer of the previous node when you find the one you want to delete.

You'll have a memory leak if you don't free the space allocated to the nodes you delete.
 

dl324

Joined Mar 30, 2015
16,846
This is what i am trying to do in code. In my function List_Data i walk through the list from beginning to end.
Your list and delete functions are independent.

The method you're attempting to use is inefficient for large lists. A doubly linked list lets you update the next pointer in the previous node without having to walk the entire list.
 

Thread Starter

Kittu20

Joined Oct 12, 2022
463
The method you're attempting to use is inefficient for large lists.
Yes agree, this method will be insufficient if there are many nodes in the list. but now i have only 4 node in my list so i want to try this.

A doubly linked list lets you update the next pointer in the previous node without having to walk the entire list.
circular, double linked list are in my mind but i don't want to go on these topics till i complete singly linked list properly.
 

dl324

Joined Mar 30, 2015
16,846
double linked list are in my mind but i don't want to go on these topics till i complete singly linked list properly.
Then change your delete function to accept the address of the node you want to delete, walk the list from the beginning (remembering the address of the last node visited), update the next pointer of the previous node when you find the one you want to delete, then free the memory allocated to the node being deleted.
 

dl324

Joined Mar 30, 2015
16,846
i understood the logic but i don't understand how to convert the logic into code for delete function.
For some reason it was quite difficult for me to work with the list you constructed backwards.

Is this what you wanted?
Code:
Insert data
Display list
4 3 2 1
Delete 3rd node
Display list
4 3 1
 

dl324

Joined Mar 30, 2015
16,846
Just tell me code how do you search for the node with the value 2 in delete function
Code:
void delete(struct node **current, int value) {
  struct node *Temp = *current, *last;
  int i = 1;
  while (i < value) {
    i++;
    last = Temp;
    Temp = Temp->next;
    if (i == value) {
      last->next = Temp->next;
      free(Temp);
    }
  }
}
Output:
Code:
Insert data
Display list
4 3 2 1
Delete 2nd node
Display list
4 2 1
I changed the delete call to select element 2.
 

Thread Starter

Kittu20

Joined Oct 12, 2022
463
I changed the delete call to select element 2.
Thank you, I ran your code on my system and it delete node
C:
//Linked list code

#include<stdio.h>
#include<stdlib.h>

//structure for node in list
struct node
{
    int data;                              // first member of node in list
    struct node *next;                     // second member of node in list
};

// Add node to front of List
void insert ( struct node **current, int value)
{
    struct node *temp = malloc( sizeof( struct node));
    {
        if ( temp != NULL )               // Memory allocated successfully
        {
            temp -> data = value;         // assign value to first member of node
            temp -> next = *current;      // this member point to previous node in list
            *current = temp;              // temporary node becomes current node in list
        }
    }
}


void delete(struct node **current, int value) {
  struct node *Temp = *current, *last;
  int i = 1;
  while (i < value) {
    i++;
    last = Temp;
    Temp = Temp->next;
    if (i == value) {
      last->next = Temp->next;
      free(Temp);
    }
  }
}

void List_Data ( struct node **current)
{
       struct node *Temp = *current;         // Temp hold memory location of first node in list
    
    while ( Temp != NULL)                // check List is not empty
    {
        printf("%d ", Temp-> data);      // print data value of node
        Temp = Temp-> next;              // Temp point to next node in list
    }
    
}


int main()
{
 
  struct node *current = NULL;            // empty list
 
  insert(&current, 1);                   
 
  insert(&current, 2);                   
 
  insert(&current, 3);
 
  insert(&current, 4);   

  // Display List data
  List_Data(&current);   

  delete(&current, 2);                     
 
  printf("\n");
  // Display List data
  List_Data(&current);
    

   return 0;
}
Program output
C:
4 3 2 1
4 2 1
 

dl324

Joined Mar 30, 2015
16,846
Thank you, I ran your code on my system and it delete node
Do you understand how it works?

I should have put the increment of 'i' after the assignment of Temp to make it clearer. Using your backwards list must have fried some of my brain cells...

EDIT: And it can't delete the first node.
 
Last edited:

Thread Starter

Kittu20

Joined Oct 12, 2022
463
That's why I said the code I provided had a limitation. Do you know how to fix it?
code to delete first node
Code:
void delete(struct node **current, int value) {
 
  struct node *Temp = *current, *last;
 
    if ( Temp != NULL && Temp->data == value)
    {
        *current = Temp -> next;
        
        free(Temp);
    }
    }
 

dl324

Joined Mar 30, 2015
16,846
code to delete first node
A problem with your code is that you're specifying the data value for the node to be deleted. Not its position in the list.

To delete the first element, you'd need to know that the data at that node was 4. Using 4 to delete node 1 is counterintuitive. That will get messier when the list is longer and you've made more insertions and deletions.

Your code can only delete the first element in the list because there's no loop.
 

Thread Starter

Kittu20

Joined Oct 12, 2022
463
This is complete code for delete function

C:
//Linked list code

#include<stdio.h>
#include<stdlib.h>

//structure for node in list
struct node
{
    int data;                              // first member of node in list
    struct node *next;                     // second member of node in list
};

// Add node to front of List
void insert ( struct node **current, int value)
{
    struct node *temp = malloc( sizeof( struct node));
    {
        if ( temp != NULL )               // Memory allocated successfully
        {
            temp -> data = value;         // assign value to first member of node
            temp -> next = *current;      // this member point to previous node in list
            *current = temp;              // temporary node becomes current node in list
        }
    }
}


void delete(struct node **current, int value) {
 
  struct node *Temp = *current, *last;
 
    if ( Temp != NULL && Temp->data == value)
    {
        *current = Temp -> next;
        
        free(Temp);
        return;
    }
      
    while (Temp != NULL && Temp->data != value)
    {
        last = Temp;
        Temp = Temp->next;
    }
    
    last->next = Temp->next;
 
    free(Temp); // Free memory
}

void List_Data ( struct node **current)
{
       struct node *Temp = *current;         // Temp hold memory location of first node in list
    
    while ( Temp != NULL)                // check List is not empty
    {
        printf("%d ", Temp-> data);      // print data value of node
        Temp = Temp-> next;              // Temp point to next node in list
    }
    
}


int main()
{
 
  struct node *current = NULL;            // empty list
 
  insert(&current, 1);                   
 
  insert(&current, 2);                   
 
  insert(&current, 3);
 
  insert(&current, 4);   

  // Display List data
  List_Data(&current);   

  delete(&current, 4);                     
 
  printf("\n");
  // Display List data
  List_Data(&current);
    

   return 0;
}
 

WBahn

Joined Mar 31, 2012
29,979
Look at your code carefully:

Code:
void delete(struct node **current, int value) {
 
  struct node *Temp = *current, *last;
 
    if ( Temp != NULL && Temp->data == value)
    {
        *current = Temp -> next;
        
        free(Temp);
        return;
    }
      
    while (Temp != NULL && Temp->data != value)
    {
        last = Temp;
        Temp = Temp->next;
    }
    
    last->next = Temp->next;
 
    free(Temp); // Free memory
}
[CODE]

If the item you are looking for happens to be the first item in the list, then you set current to the next item, free the first item, and return.

Fine so far.

But now consider what happens if the value you are looking for is not the first node.

What if the list is NULL (i.e., an empty list, which has a lot of uses)?

Your Temp pointer is NULL and the while() loop test fails immediately and you drop down and immediately dereference a NULL pointer and try to assign it to something being pointed to by 'last', which isn't even initialized, and then follow that up by freeing a NULL pointer.

What if your list isn't empty, but the value you are looking for isn't in it? You while loop continues until your Temp pointer is NULL and ditto the above, except at least 'last' is pointing at something.
 

WBahn

Joined Mar 31, 2012
29,979
You are quickly ending up with spaghetti code that is going to get harder and harder to maintain.

A good place to start is with a failing test, such as

Code:
#include <stdio.h>
#include <stdlib.h>

#include "LIST.h"

int main(void)
{
    LIST *mylist;
    
    mylist = LIST_new();
    
    printf("Adding nodes to list\n");
    LIST_insert(mylist, 1);
    LIST_insert(mylist, 2);
    LIST_insert(mylist, 3);
    LIST_insert(mylist, 4);
    LIST_insert(mylist, 5);
    LIST_insert(mylist, 6);
    
    LIST_print(mylist);
    printf("\n");
    
    printf("Removing nodes from list\n");
    LIST_remove(mylist, 6);  // Delete first item in list
    LIST_remove(mylist, 1);  // Delete last item in list
    LIST_remove(mylist, 4);  // Delete item in middle of list
    LIST_remove(mylist, 9);  // Delete item not in list
    
    LIST_print(mylist);
    printf("\n");
    
    LIST_del(mylist);     // Delete entire list
    
    return 0;
}
Now you have an end goal (or at least an initial end goal).

This won't compile, of course (and hence is a failing test), because the header files don't exist and none of the functions are even declared, let alone defined.

So next write the header files with the typedefs and function prototypes.

Code:
// LIST.h

#ifndef LIST_DOT_H
#define LIST_DOT_H

typedef struct LIST LIST;

LIST *LIST_new(void);
void LIST_del(LIST *p);

void LIST_insert(LIST *p, int value);
void LIST_remove(LIST *p, int value);

void LIST_print(LIST *p);

#endif
We've talked (in another thread) about the use of #ifndef to avoid multiple header file inclusions. Here's an example.

With this, your program should now compile (it just won't link).

Next you start writing these functions in the file LIST.c.

Along the way, you will get to the point where you need to work with objects called NODEs. So you do the same thing.
1) Go ahead and call the functions you want to have.
2) Add the function prototypes to NODE.h.
3) Implement the functions in NODE.c.

As you go, you can stub out functions and either just have then return, or have them print a message that is just the function name (so that you can see that it was called and when it was called).

A few minutes implementing the functions and when you run it you will get something like:

Code:
Adding nodes to list
[ 6][ 5][ 4][ 3][ 2][ 1]
Removing nodes from list
[ 5][ 3][ 2]
 
Top