结构，允许重复，维护插入顺序，并允许删除和插入

我找了一个数据结构，允许重复和维护插入顺序，这样，如果给定文件输入：a + a + b = c结构，允许重复，维护插入顺序，并允许删除和插入

所以，一旦正常分裂，我将获得：{a,+,a,+,b,=,c}

此数据结构也需要允许在正确的顺序删除和插入，例如，如果我更换一个与d，我应该得到{d,+,d,+,b,=,c}。

最后，结构还必须能够识别某个项目之前或之后的哪些项目。例如。直接在=之前的项目是b并且之后直接是c。

我知道列表允许重复项目和一些列表维护插入顺序，但我不确定哪些可以实现我的目标。

如果您知道某个结构会实现上述所有功能，请提供创建此类结构的语法。

问候

来源

2013-01-23 Digitalwolf

还没试过呢。从来不知道这样的事情存在。它能够做我想要的一切吗？ – Digitalwolf

我认为你需要一个平衡的树型数据结构。 –

我完全可以使用“分支因子”是否有链接指向您可以提供给我的示例，以及创建此类结构的语法是什么？ – Digitalwolf

似乎ArrayList与ListIterator将满足您的要求，对样品的使用，请参阅：http://www.java2s.com/Code/Java/Collections-Data-Structure/BidirectionalTraversalwithListIterator.htm

来源

2013-01-23 11:03:36

我的文件输入并不总是相同的，所以我将不得不删除的项目不会总是以相同的顺序，所以我不确定是否迭代通过数据是最好的选择。理想情况下，我想说** if（list.contains（“a”）{replace a with d} **）以获得我在我的问题中演示的输出结果。 – Digitalwolf

听起来像您的问题提出了算法，而不是找到一个合适的数据结构，具有ListIterator的'List'实现应该符合你的规定要求，否则你应该更新这个问题 –

只是在寻找一个可以存储重复数据和维护插入顺序的数据结构。我之前使用过一个arrayList，因为我的文件输入差异很大，我所能做的就是替换值，但是这些值始终放在列表的末尾。如果输入信息有很大差异，是否有可能通过listIterator完成我在我的问题中解释的内容？ – Digitalwolf

假设性能足够关注的，不要使用简单的Java List实现的一个（因为你希望避免迭代整个列表来搜索替换过程中的项目），那么您需要维护两个数据结构，一个用于跟踪令牌的顺序，另一个用作替换令牌位置的索引。

因此，像（我还没有经过编译运行这个，所以我们期待错别字）：

class TokenList 
{ 
    List<String> tokens; 
    Map<String,List<Integer>> tokenIndexes= new HashMap<String,List<Integer>>(); 

    TokenList(Iterable<String> tokens) 
    { 
    this.tokens = new ArrayList<String>(tokens); 
    for (int i = 0; i < this.tokens.size(); i++) 
    { 
     String token = this.tokens.get(i); 
     List<Integer> indexes = tokenIndexes.get(token); 
     if (indexes == null) 
     { 
     index = new List<Integer>(); 
     tokenIndexes.put(token, indexes); 
     } 
     indexes.add(index); 
    } 
    } 

    void replace(String oldToken, String newToken) 
    { 
    List<Integer> indexes = tokenIndexes.remove(oldToken); 
    if (indexes == null) 
     throw new IllegalArgumentException("token doesn't exist: " + oldToken); 
    for (int index : indexes) 
     tokens.set(i, newToken); 
    tokenIndexes.put(newToken, indexes); 
    } 
}

这种结构使得该令牌不会改变，一旦创建的索引假设（的tokenIndex地图需要将被重新创建，这是相对昂贵的操作）。

来源

2013-01-23 11:40:21 SimonC

已经尝试过。需要有重复的密钥。将重新审视这个问题 – Digitalwolf

我不确定我明白你的意思。这可以处理输入列表中令牌/密钥的多个实例。 – SimonC

结构，允许重复，维护插入顺序，并允许删除和插入

回答

相关问题