链表删除项目和重新排序索引 [英] linked list remove item and reorder index

问题描述

大家好，

如果我有一个链表，我想删除和项目，我应该做的是首先找到需要删除的元素，然后如果它位于链中间释放它并将其前一个指向下一个。



问题是关于定位元素，但首先看看下面的llist数据结构

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

struct node
{
   int32 index;  
   int32 data;
   struct node *next; 
};

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

节点结构有一个名为index的成员，现在索引成员可用于以两种方式查找元素，首先通过制作头部索引等于零，然后继续递增它，或者使用其内存地址增加一个常量偏移量等于（struct node）的tosize。



所以我的问题如下所示，当我删除列表的一个元素时，在重新指向前一个节点的新元素之后，如何更正索引而不循环到列表的末尾。




在此先感谢，

z3ngew

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

推荐答案

带有标记的列表并不常见。如果你想要一个索引，你最好使用一个数组。使用某种类型的模板类，所以你不需要重新发明轮子。

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

如果头对象中有一个计数器，并且每个节点都有一个索引，那么删除一个节点中间会导致至少2个地方不一致。没有办法提出可以解决这个问题的情况或算法。您的程序以及如何使用数据需要协调此问题。



您还没有说明数据是如何使用的，但我最有可能实现的方式这是从头开始查看列表，找到要删除的节点，然后更新'previous'节点指针以跳过要删除的节点。然后将所有节点的索引字段从那里更新到结尾。在完成所有这些操作时，维护所有遇到的节点的缓存计数器（除了被删除的节点）。到达列表末尾时，更新头对象中的计数器。然后删除（在内存管理上下文中）要删除的节点（如果适用）。这也将解决计数器被破坏时可能出现的任何问题，避免严重错误的计数器值，并可能修复其他可能出错的其他事情。



这样做如果同时使用列表，则应最大化列表的一致性。如果没有并发性，你几乎可以用任何其他方式完成。

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.

你不需要调整节点索引。使用第二个链来释放节点，以便在下一个插入操作中回收已删除的节点。或者您可以立即合并所有已删除的节点的阈值（删除计数）。

问候。

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.

这篇关于链表删除项目和重新排序索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！