# Linear linked list node delete

**URL:** <https://community.unix.com/t/linear-linked-list-node-delete/271007>\
**Category:** Programming\
**Created:** [August 6, 2010, 1:13pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007 "2010-08-06T13:13:31Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![rupeshkp728](https://community.unix.com/letter_avatar/rupeshkp728/32/5_5575768a8748004e209b776fc1b2916d.png) [@rupeshkp728](https://community.unix.com/u/rupeshkp728)\
**Post date:** [August 6, 2010, 1:13pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/1 "2010-08-06T13:13:31Z")

</div>

Given an in-between(any node not at the start and end of the linked list) node within a singly linear linked list, how to delete that node, when head pointer of list is not given?

---

<div class="post-metadata">

**Author:** ![Corona688](https://community.unix.com/letter_avatar/corona688/32/5_5575768a8748004e209b776fc1b2916d.png) [@Corona688](https://community.unix.com/u/Corona688)\
**Post date:** [August 7, 2010, 11:53am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/2 "2010-08-07T11:53:18Z")

</div>

If the list is doubly-linked, you can seek backwards to find it if necessary. If not, it may not always be possible to find the node you want.

---

<div class="post-metadata">

**Author:** ![rupeshkp728](https://community.unix.com/letter_avatar/rupeshkp728/32/5_5575768a8748004e209b776fc1b2916d.png) [@rupeshkp728](https://community.unix.com/u/rupeshkp728)\
**Post date:** [August 7, 2010, 12:51pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/3 "2010-08-07T12:51:07Z")

</div>

thanks coronaa for the reply.  
actually this was an interview question

---

<div class="post-metadata">

**Author:** ![achenle](https://community.unix.com/letter_avatar/achenle/32/5_5575768a8748004e209b776fc1b2916d.png) [@achenle](https://community.unix.com/u/achenle)\
**Post date:** [August 7, 2010, 2:51pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/4 "2010-08-07T14:51:54Z")

</div>

In theory, if you have a pointer to node N, you can save the pointer to the next node (node N+1), then just copy the contents of node N+1 into the memory space occupied by node N. Then free the original node N+1. Like this, for a simple C structure:

```nohighlight
void deleteNode( struct data *node )
{
    struct data *next = node->next;
    *node = *next;
    free( next );
    return;
}

```

That ignores any complications that could be caused by copying data, references to node N+1 from outside the list, and any side effects of freeing the original node N+1.

So, in practice, in all but trivial cases you'd never do that.

---

<div class="post-metadata">

**Author:** ![Corona688](https://community.unix.com/letter_avatar/corona688/32/5_5575768a8748004e209b776fc1b2916d.png) [@Corona688](https://community.unix.com/u/Corona688)\
**Post date:** [August 7, 2010, 6:47pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/5 "2010-08-07T18:47:24Z")

</div>

Ah, vague and impractical. A perfect interview question. :rolleyes:

---

<div class="post-metadata">

**Author:** ![tene](https://community.unix.com/letter_avatar/tene/32/5_5575768a8748004e209b776fc1b2916d.png) [@tene](https://community.unix.com/u/tene)\
**Post date:** [August 9, 2010, 1:40am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/6 "2010-08-09T01:40:58Z")

</div>

If you are in the Nth node and you want to delete it, just copy the (N+1)th node contents to N, link N to node N+2 and delete N+1.

---

<div class="post-metadata">

**Author:** ![Praveen\_218](https://community.unix.com/letter_avatar/praveen_218/32/5_5575768a8748004e209b776fc1b2916d.png) [@Praveen\_218](https://community.unix.com/u/Praveen_218)\
**Post date:** [August 10, 2010, 8:18am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/7 "2010-08-10T08:18:15Z")

</div>

😕

I'm thinking about what if when node numbered (N + 1) == NULL

??

i.e. when the current node itself is the last node of the chain and the list is a singly linked; does the same algorithm hold true ?

Its going to produce dangling pointers at (N - 1) th location, isn't it ?

---

<div class="post-metadata">

**Author:** ![Corona688](https://community.unix.com/letter_avatar/corona688/32/5_5575768a8748004e209b776fc1b2916d.png) [@Corona688](https://community.unix.com/u/Corona688)\
**Post date:** [August 10, 2010, 1:35pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/8 "2010-08-10T13:35:25Z")

</div>

Of course; that's the impractical bit of the question. The vague part is that they don't tell us whether it's doubly linked. Even in a doubly-linked list you'll hit a similar problem when n's the only node in the list though.

---

<div class="post-metadata">

**Author:** ![Praveen\_218](https://community.unix.com/letter_avatar/praveen_218/32/5_5575768a8748004e209b776fc1b2916d.png) [@Praveen\_218](https://community.unix.com/u/Praveen_218)\
**Post date:** [August 11, 2010, 12:43am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/9 "2010-08-11T00:43:01Z")

</div>

True.  
Its failling with even doubly linked when N == 1, making the list-pointer itself a dangling one.

---

<div class="post-metadata">

**Author:** ![tene](https://community.unix.com/letter_avatar/tene/32/5_5575768a8748004e209b776fc1b2916d.png) [@tene](https://community.unix.com/u/tene)\
**Post date:** [August 11, 2010, 6:09am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/10 "2010-08-11T06:09:35Z")

</div>

Always check whether N+1 node is Null before doing any logic.

---

<div class="post-metadata">

**Author:** ![Praveen\_218](https://community.unix.com/letter_avatar/praveen_218/32/5_5575768a8748004e209b776fc1b2916d.png) [@Praveen\_218](https://community.unix.com/u/Praveen_218)\
**Post date:** [August 12, 2010, 12:35am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/11 "2010-08-12T00:35:55Z")

</div>

> [@tene](#):
>
> Always check whether N+1 node is Null before doing any logic.

Even though you know that N+1 == NULL; what you can do in the same algorithm to protect node pointer at (N - 1) from becoming a dangling pointer ?

Apart how would your function written besed on that algorithm would ever know that N == 1; and how you would protect the list-pointer pointing to the first node from becoming dangling?

A similar algorithm holds trure in binary tree node deletion; wherein the data is copied from the leaf node which is located on the branch one move either left or right of the node to be deleted logically and the actual deletion happens at the leaf node whose data is copied. This alters the data organisation but preserves the properties of the tree.

But moreover this worked there because of the deletion always happen at the leaf node and is travelled (this travel is missing in your algorithm) to be found via the entire branch and while the travel you pass through the second last node whose pointer you get and this node doesn't become a dangling one.

The TRAVEL is important.

---

<div class="post-metadata">

**Author:** ![tene](https://community.unix.com/letter_avatar/tene/32/5_5575768a8748004e209b776fc1b2916d.png) [@tene](https://community.unix.com/u/tene)\
**Post date:** [August 16, 2010, 12:50am UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/12 "2010-08-16T00:50:30Z")

</div>

But the question was how to delete the node you are currently in.  
So there is no point in thinking of other consequences, because you cant do anything to node N-1 when you are in Nth node.

This interview question just tests your logical thinking not the algorithm efficiency.

---

<div class="post-metadata">

**Author:** ![Corona688](https://community.unix.com/letter_avatar/corona688/32/5_5575768a8748004e209b776fc1b2916d.png) [@Corona688](https://community.unix.com/u/Corona688)\
**Post date:** [August 16, 2010, 3:09pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/13 "2010-08-16T15:09:39Z")

</div>

There's plenty of reason to think about consequences, but we've already been over most of those.

---

<div class="post-metadata">

**Author:** ![Praveen\_218](https://community.unix.com/letter_avatar/praveen_218/32/5_5575768a8748004e209b776fc1b2916d.png) [@Praveen\_218](https://community.unix.com/u/Praveen_218)\
**Post date:** [August 20, 2010, 2:43pm UTC](https://community.unix.com/t/linear-linked-list-node-delete/271007/14 "2010-08-20T14:43:18Z")

</div>

> [@tene](#):
>
> But the question was how to delete the node you are currently in.  
> So there is no point in thinking of other consequences, because you cant do anything to node N-1 when you are in Nth node.
> 
> This interview question just tests your logical thinking not the algorithm efficiency.

If consequences are not to be thought, a deletion of a node is as simple as free(node\_ptr).