linked list remove item and reorder index

Question

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 7-Sep-13 6:53am

z3ngew

Add a Solution

6 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

KarstenK · Answer 1 · 2013-09-07T08:52:00

Solution 1

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

Posted 7-Sep-13 8:52am

KarstenK

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

H.Brydon · Answer 2 · 2013-09-07T09:57:00

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.

mbue · Answer 3 · 2013-09-07T11:35:00

Solution 4

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.

Posted 7-Sep-13 11:35am

mbue

nv3 · Answer 4 · 2013-09-07T23:09:00

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.

z3ngew · Answer 5 · 2013-09-07T09:52:00

Solution 2

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

Posted 7-Sep-13 9:52am

z3ngew

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.

User 59241 · Answer 6 · 2013-09-08T15:44:00

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.