标签: circular-list

为什么我们需要一个"循环链接列表"(单一或双重)数据结构？

通过简单的链接列表(单独或双重)可以解决哪些问题？

我想使用循环列表.

没有实施我自己(像这个人一样)我的选择是什么？

具体来说,我想做的是迭代一个对象列表.当我的迭代器到达列表的末尾时,它应该自动返回到开头.(是的,我意识到这可能很危险.)

请参阅Vladimir对a的定义circular_iterator:"circular_iterator永远不会与CircularList :: end()相等,因此您始终可以取消引用此迭代器."

引用@dfeuer对这个问题的回答:在Haskell中构造循环列表的最便宜的方法,它说使用循环列表"击败"垃圾收集器,因为它必须保留你从循环列表中分配的所有内容,直到你删除引用列表中的任何缺点单元格.

显然在Haskell中,循环列表和无限列表是两个独立的事物.这篇博客(https://unspecified.wordpress.com/2010/03/30/a-doubly-linked-list-in-haskell/)说如果你实现cycle如下:

cycle xs = xs ++ cycle xs

它是一个无限列表,而不是循环列表.要使它循环,你必须像这样实现它(如Prelude源代码中所示):

cycle xs = xs' where xs' = xs ++ xs'

这两种实现之间究竟有什么区别？为什么如果你在循环列表中的某个地方持有一个cons小区,垃圾收集器必须在分配之前保留所有内容？

所以我的程序需要一种圆形ArrayList.

关于它的只有圆形的东西必须是get(int index)方法,这是原始的:

    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */ 
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

如果index为-1,则应该获取索引为ArrayList.size() - 1的元素,如果index为ArrayList.size(),则应获取索引为0的元素.

我想到的最简单的实现方法就是简单地从java.util包中扩展ArrayList,然后重写get(int index),这样它就不会为上面的两个索引抛出IndexOutOfBoundsException,而是将它们改为我想要的.它会为任何其他超出范围的索引抛出IndexOutOfBoundsException.

但是,由于elementData(索引)访问a

private transient Object[] elementData;

我无法使它工作,因为我的班级没有看到它,因为它是私人的.

此外,我不想为此使用任何外部库,只是因为我认为没有一个适合我的需求,因为我不想要一个真正的circularArray,但只是它的一部分功能,其余部分是常规的ArrayList.

所以我有两个问题:

我怎样才能做到这一点？有没有办法做到这一点,而无需将整个ArrayList类与AbstractCollection,Collection和Iterable一起复制到我的程序中？这对我来说似乎是糟糕的设计.

如果我能以某种方式使它发挥作用,还有什么我应该注意的吗？如果我进行上述更改,是否会以我希望的方式更改类的行为,还是会有任何其他不需要的行为更改？

编辑: 谢谢你的回答,这就是我所做的:

import java.util.ArrayList;

public class CircularArrayList<E> extends ArrayList<E>
{
    private static final long serialVersionUID …

我注意到Scheme和Lisp(我猜)支持循环列表,我在C/C++中使用循环列表来"简化"元素的插入和删除,但它们有什么用呢？

Scheme确保它们可以构建和处理,但是为了什么？

是否存在需要为圆形或尾部圆形的"杀手级"数据结构？

我需要迭代List但循环方式.我还需要在列表中添加新元素并迭代所有元素(旧元素和新闻元素),我该怎么做？它们有任何数据结构吗？

这是一项任务.我必须创建一个循环链表并删除列表中的每三个数字.当我的程序到达列表的末尾时,它应该返回到头部并继续该过程,直到只剩下一个数字.

我在网上搜索了一些其他参考书,但无法解决我的问题.我发现的大多数参考文献都说如下:

除了循环列表没有结束这一事实外,它们与常规列表完全相同

或者(取自我的教科书):

如果最后一个节点的后继者是第一个,则单个链接列表循环链接

但这些并没有说明如何做到这一点.我也试过使用我在这个网站上找到的一些代码,但这并没有清楚.

我可以创建一个列表(我不知道它是否是循环链表)并显示它,但元素的顺序很奇怪:

• 如果列表有6个数字,则列表为1,6,5,4,3,2.
• 如果列表有8个数字,则列表为1,8,7,6,5,4,3,2.

如果没有正确的列表,我可以正确删除.以下代码有什么问题:

public class LastNumberDemo {
    public static void main(String[] args) {
        LastNumberNode ll=new LastNumberNode();
        System.out.println("how long is the list: ");
        Scanner keyboard = new Scanner(System.in);
        int input = keyboard.nextInt();

        if(input<=0) {
            System.out.println("no number to creat list");
        }
        if(input==1) {
            System.out.println("The Last number is 1.");
        }
        else {
            String[] n=new String[input];
            for(int index=0; index<n.length; index++)
                n[index]=Integer.toString(index+1);
            for(String e:n)
                ll.add(e);
            System.out.print("The list contains: \n");
            ll.print();
            System.out.print("\nThe last number is: ");
            ll.remove();
            ll.print();
        } …

我已经设置了一个表示单词的循环链表数据结构,列表中的每个元素都是单词中的一个字母.在我的问题的底部是列表的类定义和列表的元素.

列表数据结构的目的是能够比较循环词.所以......"picture"和"turepic"是相同的循环词,所以这两个列表是相同的.

所以我equals()在比较两个列表时会覆盖,而且我已经读过,每当你必须覆盖时equals(),你也必须覆盖hashCode().但是,我真的不知道如何做到这一点.

我应该如何为我设置的内容定义一个好的hashCode？我应该考虑什么？在"picture"和"turepic"的例子中,两个列表是相同的,因此它们的hashCode需要相同.有任何想法吗？

谢谢,Hristo

public class Letter {
 char value;
 Letter theNextNode;

 /**
  * Default constructor for an element of the list.
  * 
  * @param theCharacter - the value for this node.
  */
 Letter(char theCharacter) {
  this.value = theCharacter;
 }
}


public class CircularWord {

 /*
  * Class Variables
  */
 Letter head;
 Letter tail;
 Letter theCurrentNode;

 int iNumberOfElements;


 /**
  * Default Constructor. All characters that make up 'theWord' are stored in a 
  * …

场景:

对于包含3个元素[A,B,C]的列表:

您可以根据需要循环访问它.并且还有一个额外的计数功能记录每个元素的访问计数.

例如,如果访问它7次,应返回:

    [A, B, C, A, B, C, A]

并具有以下每个元素的访问计数:

    +–––––––––––+–––––––––––––––+
    |  Element  |  Access count |
    +–––––––––––––––––––––––––––+
    |     A     |       3       |
    +–––––––––––––––––––––––––––+
    |     B     |       2       |
    +–––––––––––––––––––––––––––+
    |     C     |       2       |
    +–––––––––––+–––––––––––––––+

任何回应将不胜感激.

问候.

更新

添加另一个允许调用者指定应该过滤的元素列表的附加函数.仍然使用7次访问作为示例,过滤[C]:

    [A, B, A, B, A, B, A]

    +–––––––––––+–––––––––––––––+
    |  Element  |  Access count |
    +–––––––––––––––––––––––––––+
    |     A     |       4       |
    +–––––––––––––––––––––––––––+
    |     B     |       3       |
    +–––––––––––––––––––––––––––+
    |     C     |       0       |
    +–––––––––––+–––––––––––––––+

并且,随后对getNextOne()的调用应始终获取访问计数低的模拟(模拟负载平衡的访问计数实现).因此,如果第二个调用者尝试访问它10次,则应返回:

    [C, C, C, …

我想创建一个循环/循环链表,其中列表的尾部将指向列表的头部.因此,我可以java.util.LinkedList在创建列表后使用和修改尾节点以使其成为循环/循环吗？如果是这样,你能告诉我一些如何发生的代码吗？

如果我不能使用java.util.LinkedList,我应该如何创建自己的循环/循环链表实现？你能告诉我这个实现的外观吗？

如果您需要更多详细信息,请告诉我,我会清除任何困惑.