deletion in singly linked list

deletion in singly linked list

[Jagadeesh Bhaskar P]

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 <jbhaskar@hclinsys.com>

Re: deletion in singly linked list

[Justinas]

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

On Tue, 23 Nov 2004 13:54:10 +0530
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:

> 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 <jbhaskar@hclinsys.com>
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: deletion in singly linked list

[mikael-aronsson]

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" <jugu3479@uosis.mif.vu.lt>
To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
Sent: Tuesday, November 23, 2004 9:42 AM
Subject: Re: deletion in singly linked list


> 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).
>
> On Tue, 23 Nov 2004 13:54:10 +0530
> Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
>
> > 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 <jbhaskar@hclinsys.com>
> >
> > -
> > To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >
> -
> To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: deletion in singly linked list

[Bakki Srinivas]

[-- Attachment #1: Type: text/plain, Size: 2573 bytes --]

how is this--- 
copy the content of the next item and place it in the current pointed
item,check if the next item pointed by the next item is NULL if it is then
delete the next item else move the pointer till it reaches NULL finally
delete the last one.

Srinivas

-----Original Message-----
From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
Sent: Tuesday, November 23, 2004 2:25 PM
To: Justinas; Jagadeesh Bhaskar P
Cc: Linux C Programming
Subject: Re: deletion in singly linked list


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" <jugu3479@uosis.mif.vu.lt>
To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
Sent: Tuesday, November 23, 2004 9:42 AM
Subject: Re: deletion in singly linked list


> 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).
>
> On Tue, 23 Nov 2004 13:54:10 +0530
> Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
>
> > 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 <jbhaskar@hclinsys.com>
> >
> > -
> > To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >
> -
> To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

-
To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: disclaimer.txt --]
[-- Type: text/plain, Size: 1091 bytes --]

-----------------------------------------------------------------------------------------------------------------------------
Disclaimer
-----------------------------------------------------------------------------------------------------------------------------

"This message(including attachment if any)is confidential and may be privileged.Before opening attachments please check them
for viruses and defects.MindTree Consulting Private Limited (MindTree)will not be responsible for any viruses or defects or
any forwarded attachments emanating either from within MindTree or outside.If you have received this message by mistake please notify the sender by return  e-mail and delete this message from your system. Any unauthorized use or dissemination of this message in whole or in part is strictly prohibited.  Please note that e-mails are susceptible to change and MindTree shall not be liable for any improper, untimely or incomplete transmission."

-----------------------------------------------------------------------------------------------------------------------------

Re: deletion in singly linked list

[Jagadeesh Bhaskar P]

On Tue, 2004-11-23 at 14:25, mikael-aronsson wrote:
> That will break the list, the previous item has to be updated 

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 <jbhaskar@hclinsys.com>

Re: deletion in singly linked list

[mikael-aronsson]

Yeah, that would work if you can move items between the links, just make
sure there are no pointers in other places that rely on the contents of
linked list.

Mikael

----- Original Message ----- 
From: "Bakki Srinivas" <bakki_srinivas@mindtree.com>
To: "mikael-aronsson" <mikael-aronsson@telia.com>; "Justinas"
<jugu3479@uosis.mif.vu.lt>; "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
Sent: Tuesday, November 23, 2004 10:00 AM
Subject: RE: deletion in singly linked list


how is this--- 
copy the content of the next item and place it in the current pointed
item,check if the next item pointed by the next item is NULL if it is then
delete the next item else move the pointer till it reaches NULL finally
delete the last one.

Srinivas

-----Original Message-----
From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
Sent: Tuesday, November 23, 2004 2:25 PM
To: Justinas; Jagadeesh Bhaskar P
Cc: Linux C Programming
Subject: Re: deletion in singly linked list


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" <jugu3479@uosis.mif.vu.lt>
To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
Sent: Tuesday, November 23, 2004 9:42 AM
Subject: Re: deletion in singly linked list


> 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).
>
> On Tue, 23 Nov 2004 13:54:10 +0530
> Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
>
> > 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 <jbhaskar@hclinsys.com>
> >
> > -
> > To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >
> -
> To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

-
To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: deletion in singly linked list

[Jagadeesh Bhaskar P]

Sorry about my last reply. There is a small, subtle problem.Say the
nodes as A, B, C itself. Now if we make B=C, still the address to which
A->next will b pointing will be the address of B itself. Now wont that
make a seg fault????

On Tue, 2004-11-23 at 14:30, Bakki Srinivas wrote:
> how is this--- 
> copy the content of the next item and place it in the current pointed
> item,check if the next item pointed by the next item is NULL if it is then
> delete the next item else move the pointer till it reaches NULL finally
> delete the last one.
> 
> Srinivas
> 
> -----Original Message-----
> From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
> Sent: Tuesday, November 23, 2004 2:25 PM
> To: Justinas; Jagadeesh Bhaskar P
> Cc: Linux C Programming
> Subject: Re: deletion in singly linked list
> 
> 
> 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" <jugu3479@uosis.mif.vu.lt>
> To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
> Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
> Sent: Tuesday, November 23, 2004 9:42 AM
> Subject: Re: deletion in singly linked list
> 
> 
> > 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).
> >
> > On Tue, 23 Nov 2004 13:54:10 +0530
> > Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
> >
> > > 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 <jbhaskar@hclinsys.com>
> > >
> > > -
> > > To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > >
> > -
> > To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> -
> To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com>

Re: deletion in singly linked list

[Jagadeesh Bhaskar P]

As I said in my last mail, A->B->C. Now A->next is relying simply on the
address of B. Now wont changing that break the list???

On Tue, 2004-11-23 at 14:43, mikael-aronsson wrote:
> Yeah, that would work if you can move items between the links, just make
> sure there are no pointers in other places that rely on the contents of
> linked list.
> 
> Mikael
> 
> ----- Original Message ----- 
> From: "Bakki Srinivas" <bakki_srinivas@mindtree.com>
> To: "mikael-aronsson" <mikael-aronsson@telia.com>; "Justinas"
> <jugu3479@uosis.mif.vu.lt>; "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
> Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
> Sent: Tuesday, November 23, 2004 10:00 AM
> Subject: RE: deletion in singly linked list
> 
> 
> how is this--- 
> copy the content of the next item and place it in the current pointed
> item,check if the next item pointed by the next item is NULL if it is then
> delete the next item else move the pointer till it reaches NULL finally
> delete the last one.
> 
> Srinivas
> 
> -----Original Message-----
> From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
> Sent: Tuesday, November 23, 2004 2:25 PM
> To: Justinas; Jagadeesh Bhaskar P
> Cc: Linux C Programming
> Subject: Re: deletion in singly linked list
> 
> 
> 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" <jugu3479@uosis.mif.vu.lt>
> To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
> Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
> Sent: Tuesday, November 23, 2004 9:42 AM
> Subject: Re: deletion in singly linked list
> 
> 
> > 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).
> >
> > On Tue, 23 Nov 2004 13:54:10 +0530
> > Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
> >
> > > 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 <jbhaskar@hclinsys.com>
> > >
> > > -
> > > To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > >
> > -
> > To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> -
> To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com>

RE: deletion in singly linked list

[Bakki Srinivas]

[-- Attachment #1: Type: text/plain, Size: 3432 bytes --]

Until and unless u free the memory obtained by malloc,the address space is
still in the process address space.

Srinivas

-----Original Message-----
From: Jagadeesh Bhaskar P [mailto:jbhaskar@hclinsys.com]
Sent: Tuesday, November 23, 2004 3:00 PM
To: Bakki Srinivas
Cc: mikael-aronsson; Justinas; Linux C Programming
Subject: RE: deletion in singly linked list


Sorry about my last reply. There is a small, subtle problem.Say the
nodes as A, B, C itself. Now if we make B=C, still the address to which
A->next will b pointing will be the address of B itself. Now wont that
make a seg fault????

On Tue, 2004-11-23 at 14:30, Bakki Srinivas wrote:
> how is this--- 
> copy the content of the next item and place it in the current pointed
> item,check if the next item pointed by the next item is NULL if it is then
> delete the next item else move the pointer till it reaches NULL finally
> delete the last one.
> 
> Srinivas
> 
> -----Original Message-----
> From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
> Sent: Tuesday, November 23, 2004 2:25 PM
> To: Justinas; Jagadeesh Bhaskar P
> Cc: Linux C Programming
> Subject: Re: deletion in singly linked list
> 
> 
> 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" <jugu3479@uosis.mif.vu.lt>
> To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
> Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
> Sent: Tuesday, November 23, 2004 9:42 AM
> Subject: Re: deletion in singly linked list
> 
> 
> > 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).
> >
> > On Tue, 23 Nov 2004 13:54:10 +0530
> > Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
> >
> > > 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 <jbhaskar@hclinsys.com>
> > >
> > > -
> > > To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > >
> > -
> > To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> -
> To unsubscribe from this list: send the line "unsubscribe
> linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com>


[-- Attachment #2: disclaimer.txt --]
[-- Type: text/plain, Size: 1091 bytes --]

-----------------------------------------------------------------------------------------------------------------------------
Disclaimer
-----------------------------------------------------------------------------------------------------------------------------

"This message(including attachment if any)is confidential and may be privileged.Before opening attachments please check them
for viruses and defects.MindTree Consulting Private Limited (MindTree)will not be responsible for any viruses or defects or
any forwarded attachments emanating either from within MindTree or outside.If you have received this message by mistake please notify the sender by return  e-mail and delete this message from your system. Any unauthorized use or dissemination of this message in whole or in part is strictly prohibited.  Please note that e-mails are susceptible to change and MindTree shall not be liable for any improper, untimely or incomplete transmission."

-----------------------------------------------------------------------------------------------------------------------------

RE: deletion in singly linked list

[Jagadeesh Bhaskar P]

On Tue, 2004-11-23 at 15:05, Bakki Srinivas wrote:
> Until and unless u free the memory obtained by malloc,the address space is
> still in the process address space.

Even if i do free it, where will the address A->next point to. Since it is not inside the process address space, wont that segfault??

> 
> Srinivas
> 
> -----Original Message-----
> From: Jagadeesh Bhaskar P [mailto:jbhaskar@hclinsys.com]
> Sent: Tuesday, November 23, 2004 3:00 PM
> To: Bakki Srinivas
> Cc: mikael-aronsson; Justinas; Linux C Programming
> Subject: RE: deletion in singly linked list
> 
> 
> Sorry about my last reply. There is a small, subtle problem.Say the
> nodes as A, B, C itself. Now if we make B=C, still the address to which
> A->next will b pointing will be the address of B itself. Now wont that
> make a seg fault????
> 
> On Tue, 2004-11-23 at 14:30, Bakki Srinivas wrote:
> > how is this--- 
> > copy the content of the next item and place it in the current pointed
> > item,check if the next item pointed by the next item is NULL if it is then
> > delete the next item else move the pointer till it reaches NULL finally
> > delete the last one.
> > 
> > Srinivas
> > 
> > -----Original Message-----
> > From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
> > Sent: Tuesday, November 23, 2004 2:25 PM
> > To: Justinas; Jagadeesh Bhaskar P
> > Cc: Linux C Programming
> > Subject: Re: deletion in singly linked list
> > 
> > 
> > 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" <jugu3479@uosis.mif.vu.lt>
> > To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
> > Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
> > Sent: Tuesday, November 23, 2004 9:42 AM
> > Subject: Re: deletion in singly linked list
> > 
> > 
> > > 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).
> > >
> > > On Tue, 23 Nov 2004 13:54:10 +0530
> > > Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
> > >
> > > > 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 <jbhaskar@hclinsys.com>
> > > >
> > > > -
> > > > To unsubscribe from this list: send the line "unsubscribe
> > linux-c-programming" in
> > > > the body of a message to majordomo@vger.kernel.org
> > > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > > >
> > > -
> > > To unsubscribe from this list: send the line "unsubscribe
> > linux-c-programming" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > 
> > -
> > To unsubscribe from this list: send the line "unsubscribe
> > linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com>

RE: deletion in singly linked list

[Glynn Clements]

Bakki Srinivas wrote:

> copy the content of the next item and place it in the current pointed
> item,check if the next item pointed by the next item is NULL if it is then
> delete the next item else move the pointer till it reaches NULL finally
> delete the last one.

That fails if there is no next item, i.e. you're deleting the last
element from the list.

-- 
Glynn Clements <glynn@gclements.plus.com>

Re: deletion in singly linked list

[Glynn Clements]

Jagadeesh Bhaskar P wrote:

> 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!!

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 <glynn@gclements.plus.com>

RE: deletion in singly linked list

[Bakki Srinivas]

[-- Attachment #1: Type: text/plain, Size: 874 bytes --]

prior to copyin we need to check for NULL.

-----Original Message-----
From: Glynn Clements [mailto:glynn@gclements.plus.com]
Sent: Tuesday, November 23, 2004 3:30 PM
To: Linux C Programming
Subject: RE: deletion in singly linked list



Bakki Srinivas wrote:

> copy the content of the next item and place it in the current pointed
> item,check if the next item pointed by the next item is NULL if it is then
> delete the next item else move the pointer till it reaches NULL finally
> delete the last one.

That fails if there is no next item, i.e. you're deleting the last
element from the list.

-- 
Glynn Clements <glynn@gclements.plus.com>
-
To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: disclaimer.txt --]
[-- Type: text/plain, Size: 1091 bytes --]

-----------------------------------------------------------------------------------------------------------------------------
Disclaimer
-----------------------------------------------------------------------------------------------------------------------------

"This message(including attachment if any)is confidential and may be privileged.Before opening attachments please check them
for viruses and defects.MindTree Consulting Private Limited (MindTree)will not be responsible for any viruses or defects or
any forwarded attachments emanating either from within MindTree or outside.If you have received this message by mistake please notify the sender by return  e-mail and delete this message from your system. Any unauthorized use or dissemination of this message in whole or in part is strictly prohibited.  Please note that e-mails are susceptible to change and MindTree shall not be liable for any improper, untimely or incomplete transmission."

-----------------------------------------------------------------------------------------------------------------------------

RE: deletion in singly linked list

[Bakki Srinivas]

[-- Attachment #1: Type: text/plain, Size: 4132 bytes --]

it is a dangling pointer.ofcourse it gives a seg. fault

Srinivas

-----Original Message-----
From: Jagadeesh Bhaskar P [mailto:jbhaskar@hclinsys.com]
Sent: Tuesday, November 23, 2004 3:26 PM
To: Bakki Srinivas
Cc: mikael-aronsson; Justinas; Linux C Programming
Subject: RE: deletion in singly linked list


On Tue, 2004-11-23 at 15:05, Bakki Srinivas wrote:
> Until and unless u free the memory obtained by malloc,the address space is
> still in the process address space.

Even if i do free it, where will the address A->next point to. Since it is
not inside the process address space, wont that segfault??

> 
> Srinivas
> 
> -----Original Message-----
> From: Jagadeesh Bhaskar P [mailto:jbhaskar@hclinsys.com]
> Sent: Tuesday, November 23, 2004 3:00 PM
> To: Bakki Srinivas
> Cc: mikael-aronsson; Justinas; Linux C Programming
> Subject: RE: deletion in singly linked list
> 
> 
> Sorry about my last reply. There is a small, subtle problem.Say the
> nodes as A, B, C itself. Now if we make B=C, still the address to which
> A->next will b pointing will be the address of B itself. Now wont that
> make a seg fault????
> 
> On Tue, 2004-11-23 at 14:30, Bakki Srinivas wrote:
> > how is this--- 
> > copy the content of the next item and place it in the current pointed
> > item,check if the next item pointed by the next item is NULL if it is
then
> > delete the next item else move the pointer till it reaches NULL finally
> > delete the last one.
> > 
> > Srinivas
> > 
> > -----Original Message-----
> > From: mikael-aronsson [mailto:mikael-aronsson@telia.com]
> > Sent: Tuesday, November 23, 2004 2:25 PM
> > To: Justinas; Jagadeesh Bhaskar P
> > Cc: Linux C Programming
> > Subject: Re: deletion in singly linked list
> > 
> > 
> > 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" <jugu3479@uosis.mif.vu.lt>
> > To: "Jagadeesh Bhaskar P" <jbhaskar@hclinsys.com>
> > Cc: "Linux C Programming" <linux-c-programming@vger.kernel.org>
> > Sent: Tuesday, November 23, 2004 9:42 AM
> > Subject: Re: deletion in singly linked list
> > 
> > 
> > > 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).
> > >
> > > On Tue, 23 Nov 2004 13:54:10 +0530
> > > Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
> > >
> > > > 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 <jbhaskar@hclinsys.com>
> > > >
> > > > -
> > > > To unsubscribe from this list: send the line "unsubscribe
> > linux-c-programming" in
> > > > the body of a message to majordomo@vger.kernel.org
> > > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > > >
> > > -
> > > To unsubscribe from this list: send the line "unsubscribe
> > linux-c-programming" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > 
> > -
> > To unsubscribe from this list: send the line "unsubscribe
> > linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com>


[-- Attachment #2: disclaimer.txt --]
[-- Type: text/plain, Size: 1091 bytes --]

-----------------------------------------------------------------------------------------------------------------------------
Disclaimer
-----------------------------------------------------------------------------------------------------------------------------

"This message(including attachment if any)is confidential and may be privileged.Before opening attachments please check them
for viruses and defects.MindTree Consulting Private Limited (MindTree)will not be responsible for any viruses or defects or
any forwarded attachments emanating either from within MindTree or outside.If you have received this message by mistake please notify the sender by return  e-mail and delete this message from your system. Any unauthorized use or dissemination of this message in whole or in part is strictly prohibited.  Please note that e-mails are susceptible to change and MindTree shall not be liable for any improper, untimely or incomplete transmission."

-----------------------------------------------------------------------------------------------------------------------------

RE: deletion in singly linked list

[Bakki Srinivas]

[-- Attachment #1: Type: text/plain, Size: 1123 bytes --]

ya we cant delete the last item this way.very true
Srinivas

-----Original Message-----
From: Bakki Srinivas 
Sent: Tuesday, November 23, 2004 3:53 PM
To: 'Glynn Clements'; Linux C Programming
Subject: RE: deletion in singly linked list


prior to copyin we need to check for NULL.

-----Original Message-----
From: Glynn Clements [mailto:glynn@gclements.plus.com]
Sent: Tuesday, November 23, 2004 3:30 PM
To: Linux C Programming
Subject: RE: deletion in singly linked list



Bakki Srinivas wrote:

> copy the content of the next item and place it in the current pointed
> item,check if the next item pointed by the next item is NULL if it is then
> delete the next item else move the pointer till it reaches NULL finally
> delete the last one.

That fails if there is no next item, i.e. you're deleting the last
element from the list.

-- 
Glynn Clements <glynn@gclements.plus.com>
-
To unsubscribe from this list: send the line "unsubscribe
linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: disclaimer.txt --]
[-- Type: text/plain, Size: 1091 bytes --]

-----------------------------------------------------------------------------------------------------------------------------
Disclaimer
-----------------------------------------------------------------------------------------------------------------------------

"This message(including attachment if any)is confidential and may be privileged.Before opening attachments please check them
for viruses and defects.MindTree Consulting Private Limited (MindTree)will not be responsible for any viruses or defects or
any forwarded attachments emanating either from within MindTree or outside.If you have received this message by mistake please notify the sender by return  e-mail and delete this message from your system. Any unauthorized use or dissemination of this message in whole or in part is strictly prohibited.  Please note that e-mails are susceptible to change and MindTree shall not be liable for any improper, untimely or incomplete transmission."

-----------------------------------------------------------------------------------------------------------------------------

Re: deletion in singly linked list

[Justinas]

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

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

On Tue, 23 Nov 2004 10:42:46 +0200
Justinas <jugu3479@uosis.mif.vu.lt> wrote:

> 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).
> 
> On Tue, 23 Nov 2004 13:54:10 +0530
> Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
> 
> > 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 <jbhaskar@hclinsys.com>
> > 
> > -
> > To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: deletion in singly linked list

[Alphex Kaanoken]

On Tue, 23 Nov 2004 13:54:10 +0530
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:

> 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 <jbhaskar@hclinsys.com>
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
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.

Re: deletion in singly linked list

[Jagadeesh Bhaskar P]

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

Re: deletion in singly linked list

[Alphex Kaanoken]

On Thu, 25 Nov 2004 09:19:37 +0530
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:
ok, you made some mistakes
> 
> 
> /************* start of code ***********/
> #include <stdio.h>
> 
> typedef struct _node{
> 	int data;
> 	struct _node *next;
> }node;
> 
> void printList(node* head){ /*this is ok, but you make pointer to unsiged*/
> 	node *temp;
> 	temp = head;
> 	while(temp){ /*! make for safetly while(tmep!=NULL)*/
> 		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;
/*it's can't be worked! I'm usually write a simple function for this and it's working*/
> 	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);
/*it's not true way - use my function*/
> 	
> 	
> 	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???
> 
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
> 
> -- 
> With regards,
> 
> Jagadeesh Bhaskar P
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
--
System Developer of
SoftMine Corp.
Alphex Kaanoken

Re: deletion in singly linked list

[Jagadeesh Bhaskar P]

Thanks for the reply. Adding my comments below:

On Thu, 2004-11-25 at 15:41, Alphex Kaanoken wrote:
> 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
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

Re: deletion in singly linked list

[Alphex Kaanoken]

On Thu, 25 Nov 2004 15:56:31 +0530
Jagadeesh Bhaskar P <jbhaskar@hclinsys.com> wrote:

> Thanks for the reply. Adding my comments below:
> 
> On Thu, 2004-11-25 at 15:41, Alphex Kaanoken wrote:
> > 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
> 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?
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. 
> 
> Otherwise its simply linkedlist manipluation, and thatz not what I asked
> for :-(
So, you need to rewrite the code ;-( 
> 
> -- 
> With regards,
> 
> Jagadeesh Bhaskar P
> R&D Engineer
> HCL Infosystems Ltd
> Pondicherry
> INDIA
> 
--
System Developer of
SoftMine Corp.
Alphex Kaanoken