Click here to Skip to main content
15,921,774 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello everyone,
if i have a linked list and i want to remove and item, what i should do is first locate the element that need to be removed, and then if it is located in the middle of the chain free it and point its previous to its next.

the question is about locating the element, but first take a look at the following llist data structure
C++
struct node
{
   int32 index;  
   int32 data;
   struct node *next; 
};

typedef struct
{
   struct node *head;
   int32 count;
}llist;

the node structure has a member called index, now the index member can be used to find elements in 2 ways, first by making the head index equal zero, and then keep incrementing it, or by using its memory address which is incremented by a constant offset equal tosize of(struct node).

so my question is as follows,
when i remove an element of the list, after re-pointing the previous node the new element, how to correct the index without looping to the end of the list.

Thanks in advance,
z3ngew
Posted

a list with indicies is not usual. If you want an index you better use an array. Use some type of template class, so you need not to "reinvent the wheel".
 
Share this answer
 
Comments
z3ngew 7-Sep-13 15:06pm    
i use the index to access element at specified index, thanks
Stefan_Lang 9-Sep-13 4:28am    
That doesn't make sense. If you use a list, then you use references or pointers to elements for the purpose of accessing a specific element. An index value only makes sense for arrays.
Stefan_Lang 9-Sep-13 4:28am    
[...]
[edit] Sorry, I meant to reply to z3ngew
If there is a counter in the head object and an index in each node, then removing a node in the middle will cause inconsistency in at least 2 places. There is no way to come up with a situation or algorithm that will fix this. Your program and how you use the data will need to reconcile this issue.

You haven't said how the data is used, but the way I would most likely implement this is to go through the list from the head, find the node to delete, then update the 'previous' node pointer to skip over the node to be deleted. Then update the index fields for all nodes from there to the end. While doing all of this, maintain a cached counter of all nodes encountered (except the one being deleted). When you reach the end of the list, then update the counter in the head object. Then delete (in memory management context) the node being deleted (if appropriate). This will also fix any problems that may occur if the counter gets mangled, avoid grossly incorrect counter values and probably fix several other things that may go awry.

Doing it this way should maximize the consistency of your list if it is being used concurrently. If there is no concurrency, you can do it almost any other way.
 
Share this answer
 
Comments
z3ngew 7-Sep-13 16:01pm    
you are correct but in order to update every node index, that will cause big iterations in big lists, (take longer time), but please read my solution and tell me your opinion,

the index is concluded from memory address and the index member will no longer be used
z3ngew
H.Brydon 7-Sep-13 17:46pm    
The choices you have are:
- scan the entire list each time you delete a node and update all index values
- scan to the node to be deleted, and (as you say) abandon the in-node index value

The choice is up to you. If you don't use the index value any more, it should probably be removed from the node struct definition or somebody else will come along and try to use it and it will find out the hard way that it has incorrect info. [This is where big bugs come from.]
you dont need to adjust the node indexes. use a second chain for freed nodes to recycle the deleted nodes on the next insert operation. or you can merge all deleted nodes on a threshold value (delete count) at once.
regards.
 
Share this answer
 
The method you describe in solution 2 is not an option. You are not allowed to move nodes in memory, because all next pointers will be pointing to the wrong place. A single big memmove would also assume that the remaining nodes in your list are in a contiguous memory block, which they are generally not. After many insert and delete operations your list will we spread across memory.

Here is my advice. If you want to use the index member just to uniquely identify a node, then don't call it index but uniqueId or simply id. Then, whenever you add a new node you assign it a new uniqueId, which has not been used so far in that list. For example, use a member nextUniqueId in the llist structure which you increment each time you need a new uniqueId. You better use the longest int type you have, at least 64 bit, to avoid running out of uniqueIds in your lifetime. Now, when you delete a node, you don't have to adjust any existing uniqueIds. Each node receives its uniqueId when it is created and keeps it for the rest of its life.

If that doesn't work for you, then forget about the index field all together. If you want index to indicate the ordinal number of the node in the list, you will have to update a lot of nodes each time you insert or delete a new node. To be exact you will have to update an average of N/2 nodes, N being the list length. You thereby destroy the one and only advantage of a list: Short insert and delete times. If you need access by index then you should use an array, as KarstenK already said.
 
Share this answer
 
v2
I think i have found the solution, after freeing the desired node, i make memmove to the rest of the list to shift (sizeof(struct node)) left, now in order to get element at specific index we can use memory address and discard the index member, for example
the head is always the first and then add nxsizeof(struct node) to go to your desired element,

Please review my answer, Thanks
z3ngew
 
Share this answer
 
Comments
[no name] 8-Sep-13 6:13am    
This can't be right. What is your memmove doing? The elements are not contiguous. Why are you using linked list at all if you are going to move the elements around. The whole mechanism of linked list is that each element has a pointer to the next. This will break. Anyway as the list gets bigger this method would be very inefficient. Use an stl templated class which does all this for you without bugs. I dont' think this is an answer at all.
H.Brydon 8-Sep-13 14:50pm    
This won't work if the nodes are a non-contiguous list. For different reasons, it also won't work if the nodes are a contiguous list.

If the node pointers are truly pointers, you will end up with a botched list in both cases.
Others have made very valid points already.
You have not provided sufficient information in your question for a rigorous answer. This is a design issue and you have not said anything about how much data you have and why you chose a linked list in your design. This I fear was where your troubles began.
In general a linked list where elements are position sensitive and where elements can be inserted and removed from positions sounds less like a linked list and more like a circular buffer or some other construct.
Linked lists are very useful where the element size varies and where mostly elements are added or removed from the ends. This appears to be not the case in your requirement.
There are other ways of solving your problem using for example stl containers (vector maybe) which will stand up to scrutiny much better than your current approach.
I think you should reappraise your design.
 
Share this answer
 
v3

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900