Delete the last node of a linked list. Each node has a data pointer as well that points to some data

Hi All I saw this question posted on a site asked in a technical开发者_开发问答 interview

Node has a data pointer as well as point to some data.

Can somebody help me understanding what this question mean in detail??

Does this mean that Node has pointer to another node and point to some other data node as well. And that data node does not point to any other node. In that case our node will have two pointers.

i am really confused. Please Help.

Thanks in advance

The node structure of your list is pretty clear. In C, it would look something along the lines of:

typedef struct list list;
struct list {
        list *next;
        void *data;
}

However, if your task is to delete the last node of a linked list, then the task is ambiguous. In single linked lists, you usually insert new nodes at the front, because this can be accomplished in constant time. So it remains unclear whether the "last node" refers to the node that has been inserted most recently (and is hence the front node) or whether it refers to the first node inserted (and is hence the last node that you would see when you traverse through the list).

In the first case, it's really easy to remove the "last" node of a list list, because it's the front node: list = list->next. You may want to incorporate the edge case of an empty list: list = list?list->next:NULL.

In the second case where you are supposed to delete the node that has been inserted first, it's a bit more tricky. You have to traverse through the list, maintaining a pointer to the current element and in addition a pointer to the element before that. Here's some code that you might find useful:

cur = list->next;
prev = list;

while (cur->next != NULL) {
        prev = cur;
        cur = cur->next;
}

prev->next = NULL;

free(cur->data);
free(cur);

This code iterates through the list and stops when cur points to the last node (the only list node whose next-pointer points to NULL). Then, we unlink the last node by setting the next-pointer of the previous element to NULL.

Note that you have two special cases:
- the list is initially empty (nothing to do here)
- the list only contains one element (i.e. the first element is the last element, switch to the method described earlier)

It should ideally read: Node has a "Next" pointer and the node-data itself is a pointer. Such kind of data structures are common where data itself can be huge and cannot be kept in-memory or within the same node.

Edit:

Looking at the question link: my assumption, mentioned above, seems to be what it is. All you need to do is pick up the pointer from the data field of the node and delete that before deleting the node.

Linked list representation: [data1, p1]->[data2, p2]->[data3, p3] (p3 points to nothing)

You would be expected to delete data3, p3, AND set p2 to null so that you don't have a lost pointer!

Maybe this will clear things up for you a little: http://en.wikipedia.org/wiki/Linked_list

Each node in a linked list has a pointer to the next node and some data. The data is never a pointer to nodes in the same list.

edit: So given a list, you should write a function that deletes the last node and ensures that the new last node points to NULL.