deletion in singly linked list

I am having the address of a single node of a singly linked list. All I know about that node is that it is not the head of the list. Now say, I want to delete this node. I can infer its next node, but not its predicissor. Is there any way to delete that node, without breaking the whole linked list down!!

Jagadeesh Bhaskar P <[email protected]>

Hello,

i think You can. For instance n is a pointer to curent node and n->next is pointer to next node. lets say we like this tmp = n, and n = n->next. After that free(tmp).

That will break the list, the previous item has to be updated so you will need to get the first item of the list and walk through the list until you find the item in front of the one you want to delete and change the "next" pointer in that item to point to the one in the "next" pointer in the item you are deleting.

Then you can delete the item you started with. There is no other way to do it without a double linked list.

Mikael

----- Original Message -----
From: "Justinas" <[email protected]>
To: "Jagadeesh Bhaskar P" <[email protected]>
Cc: "Linux C Programming" <[email protected]>
Sent: Tuesday, November 23, 2004 9:42 AM
Subject: Re: deletion in singly linked list

pointer to next node. lets say we like this tmp = n, and n = n->next. After that free(tmp).

linux-c-programming" in

linux-c-programming" in

But according to the solution by Justinas, say, the nodes be A, B and C. Now C's address is assigned to B's address. So shouldnt any link, like A->next, point to C automatically?

Jagadeesh Bhaskar P <[email protected]>

In general, no.

If you want to be able to delete elements, you normally require an extra level of indirection, i.e. a pointer to the pointer.

E.g. if the node structure is:

	struct node {
		struct node *next;
		/* other fields */
	};

and you have a list:

	struct node *the_list;

you can traverse the list for reading with:

	struct node *l;

	for (l = the_list; l; l = l->next)
	{
		...
	}

But if you want to be able to delete an element, you would use e.g.:

	struct node **p, *l;

	for (p = &the_list; l = *p; )
	{
		if (want_to_delete(l))
		{
			*p = l->next;
			free(l);
		}
		else
			p = &l->next;
	}

The same applies if you want to insert a new element before the current element.

Glynn Clements <[email protected]>

sorry, my mistake, i wrote it in a hurry, before lectutes:).

i wanted to write like tris:
*n = *(n->next).

So, You must have something like following structure typedef struct _mylist {
int id; /*I'm usually use it - you may don't including it*/ void *data; /*pointer to data*/
struct _mylist *next; /*pointer to the next list member*/ } mylist;

For deletion from this list use something code like that -
mylist * DelItem(mylist *ptr,int id) /*id of member that you want to delete*/ {
mylist *prev=NULL;
mylist *curr;
curr=ptr; /*save pointer address*/

while(curr!=NULL && curr->id!=id){ /*search for member with pointed id*/

    prev=curr;
    curr=curr->next;
  }
  if(curr==NULL) /*nothing to delete NOTE!: don't make `curr' unsigned!*/
    return ptr;
  if(curr==ptr) /*just see what the member*/
    ptr=curr->next;
  else
    prev->next=curr->next;

free(curr->data); /*if you need to free some data that pointer by void* */ free(curr); /*free member*/
return ptr; /*return pointer to the start of linked list*/
}

use this function -
MyList=DelItem(MyList,2);

This function's algorythm working very well and stable. It can delete anything item - in start of list, middle if list, or at end of list ;-)

Best wishes.

/************* start of code ***********/
#include <stdio.h>

typedef struct _node{
	int data;
	struct _node *next;
}node;

void printList(node* head){
	node *temp;
	temp = head;
	while(temp){
		printf("%d\n", temp->data);
		temp = temp->next;
	}
	return;
}

int main(void){

	node *a, *b, *c;
	a = (node*)malloc(sizeof(node));
	b = (node*)malloc(sizeof(node));
	c = (node*)malloc(sizeof(node));
	
	a->data = 1;
	a->next = b;

	b->data = 2;
	b->next = c;

	c->data = 3;
	c->next = NULL;

	node *head;
	head = a;
	
	printList(head); //prints 1, 2, 3 -- its OK

	//deletion of b
	printf("Attaching node with data = %d\n", (b->next)->data);
	b = b->next;
	free(b);
	
	
	printList(head); //prints 1, 2, 0 -- NOT OK -- still a->next points to the location of b, even if its freed!! And also making b = b->next and free(b) removes the link b->next pointing to c. So finally c->data is not obtained!!
	return 0;
}

/********** end of code ************/

It is exactly in the same track as Kaanoken mentioned. But the linked list is broken.

Now how can this be fixed???

With regards,

Jagadeesh Bhaskar P

On Thu, 25 Nov 2004 09:19:37 +0530 Jagadeesh Bhaskar P <[email protected]> wrote:
ok, you made some mistakes

/*it's can't be worked! I'm usually write a simple function for this and it's working*/

/*it's not true way - use my function*/

So, I'm write a functions- for deletion from list ypu will see in my prevous message for add mamber to the end of list use something like this function:
mylist * AddItem(mylist *ptr,void *data)
{
mylist *lp=ptr;
int id=0;

  if(ptr!=NULL){
    ++id;
    while(ptr->next!=NULL)
      {
        ptr=ptr->next;
        ++id;
      }
    ptr->next=(app_list*) malloc(sizeof(app_list);
    ptr=ptr->next;
    ptr->next=NULL;
    ptr->id=id;
    ptr->data=data; /*see how you will be work with pointers*/
    return lp;
  }
  else{
    ptr=(app_list*) malloc(sizeof(app_list);
    ptr->next=NULL;
    ptr->id=id;
    ptr->data=data;
    return ptr;

}
}
it's worked with my singly linked list structure example in prevous message
If you need to insert/add to start of list, just rewrite this function it's simple.
In addition just imagenate you linked list structure in mind and understand that
is very simple
in linked list you have "members" with pointer to the next member,
if you need to remove member in any place you must do following things
- find member to remove
- take a pointer of prev member and change him to the next member that following after removeing member
- free memory that malloced for removing member
it's all
also if you need to make addition to the end of list faster you can create
a pointer to the end of list, in this case you don;t need to go for the end of list when you want to add the new member.

Best wishes

--
System Developer of
SoftMine Corp.
Alphex Kaanoken

Thanks for the reply. Adding my comments below:

But I had explained previously, that this is a special case. I dont know which is the head and which is the tail of a singly linkedlist. All I know is that this is a node of the linked list and say the format of the node. So from this I can get only the pointer to its next node. How can I find its previous node? Is there a way to find it out?

Otherwise its simply linkedlist manipluation, and thatz not what I asked for :-(

With regards,

Jagadeesh Bhaskar P
R&D Engineer
HCL Infosystems Ltd
Pondicherry
INDIA

I'm afraid that's not really, because You have pointer only for next member of single linked list and all members usually defragmented in memory and you can't determine the preview member address.Of couse you can determine the end of list, the `next' pointer at last member points to NULL, but the first or middle members don't.
This is not the good side of singly listed list.

So, you need to rewrite the code ;-(

--
System Developer of
SoftMine Corp.
Alphex Kaanoken