Have something to say? Contribute New Article Reply to this Article
Linked List
Hello,
Please i really need your help.
I am trying writing a code that will delete the last element of the list. However, i keep getting 0 or when i tweak it, i get a message asking me to abort what i am doing.
In this code, i append some values to the list and ask it to do some functions like get first, get last, remove first...these functions work fine. However, i cannot seem to get the remLast right.
thank you very much in advance.
Here is the code:
int LList::remLast()//this does not have parameters.
{
if(size==0){
cout<<"Empty List --- Removal is not";
cout<<"Possible --- Error"<<endl;
return -1;
}
Lnode *ptemp;
Lnode *temp=tail;;
if(size==1)
head=tail=NULL;
ptemp->next = temp->next;
size--;
if(tail==temp)
tail = ptemp;
delete temp;
}It looks like your code is a bit foggy on what it ought to be doing.
Get out a piece of paper and pencil and draw yourself a linked list, complete with little arrows pointing from node to node.
Then using the eraser and pencil change the drawing so that the last node is properly unlinked and deleted.
Do that exercise for a list of one node and a list of more than one node.
Hope this helps.
Hi,
Thank you for your help. what u wrote down is what i have been trying to do but i am having a problem expressing how to move the pointer to the node before the last node after deleting the actual last node.
I only know how to move forward in a list and not go backwards.
Any assistance is greatly appreciated
Thank you very much.
Hi Olams,
Respectfully there are some fundamental concepts you seem to be struggling with.
You said you needed help moving pointers - that you know how to move forward but not backward.
Break the ideas down into the machine level. Remember, a pointer is just a memory address - it's a number that identifies a place in memory. So a pointer itself does not advance forward or backward as such. You can increment the number (add 1) but that assumes that the memory you're dealing with is all together - contiguous blocks - as what happens when indexing through an array.
Perhaps you're working on a coding exercise (project from school?) and you're supposed to extend a single linked list class into a double linked list class.
If that's the case, your Lnode class should have forward going pointers - that point to the next Lnode in the list (it's really more like a chain) and there should be a backward pointer to the previous node. Using C++ structs this might look like this:
// A doubly linked-list node
//
struct ListNode {
ListNode * next_node;
ListNode * prev_node;
void * ptr_to_data;
};
As you can see, each node is really in a two-way chain. // A linked list.
//
struct List {
ListNode * head;
ListNode * tail;
int length;
};
Presumably the remove-last method you refer to is supposed to remove the last node and delete it.
So you first need to remove it from the list (like cutting the links in a chain).
Try using local variables to give you clear signs of what you're dealing with. That is, instead of worrying about tail -> prev why not assign a meaningful local var? if (size > 1) {
/////////////////
// This code deals with the case that the tail is not the only one in the list.
/////////////////
//
ListNode * new_tail = tail -> prev;
// Unlink new tail from the old tail.
new_tail -> next = NULL;
// We probably need to delete the data item the tail pointed to??
if ( tail -> ptr_to_data != NULL) {
delete tail -> ptr_to_data;
}
delete tail;
tail = new_tail;
}
Hope that helps. I'll let you figure out how to deal with the case where there is only one node in the list.
Remember - make your variable names as clear as you can. Names like "temp" aren't that useful. Use a few variables - they're free! Use them for specific purposes and give them names that indicate the purpose.
Don't tell someone to add complexity. There is no need to add more pointers. People delete the last element of singly-linked lists all the time.
Olams, assuming your list really is a singly-linked list, to delete the last node you will need to start at the head node and traverse the list until the next node is the last node. Then you can delete the last node. Make sense? You have to look ahead a little as you go.
Hope this helps.
Don't tell someone to add complexity. There is no need to add more pointers. People delete the last element of singly-linked lists all the time.
What? Did you read the original question?
He did indicate that he wanted to navigate bi-directionally in his list. I was reading between the lines that he was 'supposed' to extend a list because - let's face it - you'd only implement linked-lists in C++ as an exercise. Any commercial dev would use STL.Olams, assuming your list really is a singly-linked list, to delete the last node you will need to start at the head node and traverse the list until the next node is the last node. Then you can delete the last node. Make sense? You have to look ahead a little as you go.
Hope this helps.
Olam's code fragment did mention 'tail' ergo to remove the last item in a list he does not need to walk the list to find it. Don't be so quick to criticise other people's attempts to help - especially if you don't read the original posting's question.
What? Did you read the original question?
Yes, and I read every other post here also, including yours.He did indicate that he wanted to navigate bi-directionally in his list.
No, at no point did he indicate that. His original post at no time indicates that his list has 'back' pointers, nor did he ever say he needed to walk it backwards.
In fact, in post #4 he did sayI only know how to move forward in a list and not go backwards.
which is as close as he ever got to indicating anything about the directionality of his list.You go re-read stuff.
I was reading between the lines that he was 'supposed' to extend a list because
Oh, that's your problem. Requirements engineers don't like programmers who like to "read between the lines".because - let's face it - you'd only implement linked-lists in C++ as an exercise. Any commercial dev would use STL.
Bull. You are aware, perhaps, that the STL 'list' container is specifically a linked list? Oh, and that some others may be also? You may not care what I think of the laughable "one-size-fits-all" argument, but you should at least find out what people who are recognized experts think (That is but one example). Any commercial dev would use the most appropriate tool for the task, whether or not that involves the STL.
Olam's code fragment did mention 'tail' ergo to remove the last item in a list he does not need to walk the list to find it. Don't be so quick to criticise other people's attempts to help - especially if you don't read the original posting's question.
Oh, it did, did it? Well, that tells usreams about his code! Very convenient!
To delete the last node in a linked list you need to find the penultimate node, not the last.
Assuming his code is a singly-linked list (which, with what we have been given, is all we can safely assume) he will need to walk the list to find it. If, in fact, he does have a doubly-linked list, then by all means use last->previous.
Don't be so quick to return offense where none is given. And don't start personal attacks when you disagree.
I've been teaching people to program for a long time, and one of the most frustrating obstacles to new programmers is people who answer with all kinds of information about how to improve, or add to, or change their project when a more direct answer is available. The most common cause of this problem is that the helper thinks he has a better understanding of the helpee's problem with but a glance than is warranted. The first step is to be sure you understand the OP's constraints, then advise appropriately. Don't assume more than you've been given. Notice how brk235 kindly asked for more information?
In order to delete the last node of a singly linked list try this:
1.take two ptrs and assign to the head:
2.traverse down the list such that one ptr points to a node and the other points the previous node. Do this till you arrive to the last node
3.free the last node
In order to delete the last node of the singly linked list do this;
1.Take two pointers.
2.Assign 1st pointer to the head and 2nd to the next node.
3.traverse the list till the last node such that 2nd ptr points to last node and 1st ptr oints to the previous node.
4.assign NULL to the 1st ptr .
5.Free the 2nd ptr
I was reading between the lines that he was 'supposed' to extend a list because - let's face it - you'd only implement linked-lists in C++ as an exercise. Any commercial dev would use STL.
This is not true. The STL list implementation is not the only style of linked list. For starters, you can't make a new list with one extra element on the front without modifying the original or copying the whole thing. A reasonable alternative linked list implementation is a singly linked immutable list with reference-counted nodes. Or that could be implemented as a singly linked list with a custom allocator that handles garbage collection. Most of the STL containers are limited in that they're designed to be used in a single-threaded, stateful manner.
thank you to everyone who replied.
i figured it out. i only used one pointer.
thanks anyway
This article has been dead for over three months
You
© 2012 DaniWeb® LLC
