0

我需要编写自己的 Deque 类,并且必须使用双向链表实现来存储数据。问题是编写方法 pushfromLeft(Thing thing) 将插入双端队列的左侧。以下是我迄今为止所拥有的,但似乎不起作用。

 public void pushLeft(Thing thing) {
         Node beg = new Node();  
         Node end = new Node();
         Node T = new Node();  

       if(isEmpty())
       { 
             beg = first;
             end = last;
             beg = end;
             T = beg.thing;
             N++;
       }
       else
       {
             beg = beg.next;
             end = end.next;
             T = beg.previous;
             N++;


       }
4

4 回答 4

4

您在该方法中所做的很少有任何外部影响,除了更改Nand item。大概你应该修改first. 如果您提供类的字段以及它们的含义,这将有所帮助。例如,不清楚是什么item

您还应该提出不同的命名成员和局部变量的约定,或者始终使用this.,或两者兼而有之。

于 2012-04-17T18:34:53.117 回答
1

我是否可以提出一个建议,可以为您解决很多问题。这不是你要求的,但它可能是你需要的。

使用OO设计,这意味着不是对某事进行操作,而是要求某事对自己进行操作。这意味着 Node 应该更智能——目前你正在对 node 进行操作。

由于 Node 是双重链接的,它可以非常聪明!它可以有如下方法:

newNode.insertBefore(currentNode)
newNode.insertAfter(currentNode) 
currentNode.remove() 

一旦你有了这些,你的其余代码应该清理一下。给定一个双向链表,它们应该很容易实现。

void insertBefore(node existing) {
    // first set my stuff up
    previous = existing.previous;
    next = existing;
    // then point other stuff at me
    previous.next = this; 
    existing.previous = this;
}

我想——这只是我的想法。

另一个问题是你如何处理你的“端点”。您的第一个和最后一个指针必须是 Node 的实例才能工作,但如果他们注意到整个“If”因素超出了您的原始代码!甜的!

只是总是有一个第一个和最后一个对象开始指向彼此(并且从不接受值)。当您进行第一次添加时,执行 first.insertAfter() 或 last.insertBefore() 即可完成。

顺便说一句,另一种可能性是使列表循环 - 没有理由 First 和 Last 不能是同一个“特殊”未分配节点,您仍然可以遍历它的 Next (这将为您提供第一个真正的项目在列表中)和上一个(为您提供列表中的最后一项)。

当迭代整个列表时,如果 .value == null,你知道你已经到达了另一端,这使得 node.next() 和 previous() 非常容易实现(你甚至不需要实现 .接下来,但见下文。

/** returns null if there are no more items in the list */
Node next() {
    return next;
}

试试看,它会大大简化你的代码。大多数人真的不明白实际的 OO 代码有多么有用。

此外,将所有变量设为私有,这是一个好习惯。在这种情况下,当您让节点相互操作时,它们仍然可以访问彼此的私有成员(不像听起来那么脏),因此您仍然可以像我写的那样拥有 insertBefore 并且您不必拥有 getter 和设置器或公共变量。两全其美。

还要注意在节点上“操作”的原始类几乎消失了——事实上,它可以完全消失。如果您需要一些特定的方法,例如 find(item) 或 insertSorted(item) ,则没有理由不能将它们添加到节点本身。不过,在您实施它之前,这可能很难看到。

有趣的是,如果您实际上编码得很好,那么人们对 Java 的大多数抱怨都不会出现。

于 2012-04-17T18:53:01.297 回答
0

您绝对不需要创建多个Node内部添加方法。如果您想稍后从左侧和右侧读取,则每个都Node必须记住上一个和下一个元素。然后在添加的时候,只需要重新定位这些链接,像这样:

public void pushLeft(Thing thing) {
   Node newNode = new Node();  
   newNode.setValue(thing); //or just   newNode.value = thing;

   if(this.isEmpty())
   { 
         this.first = this.last = newNode;
         this.n=1;
   }
   else
   {
         this.first.previous = newNode;
         newNode.next = this.first;
         this.first = newNode;
         this.n++;
   }
}

为 Node 类创建一个应该自动设置值的构造函数是明智的,然后你可以写:

Node newNode = new Node(thing);
于 2012-04-17T19:01:29.227 回答
0

您是否查看过LinkedList源代码作为参考?

于 2012-04-17T18:39:26.320 回答