链表并将元素添加到列表的末尾

Question

我需要创建矩形链表。 Im given the class files of 矩形and点classes, and need to writeRectNodeandRectList`.

这是RectNode:

public class RectNode
{     
    private RectangleA _rect;
    private RectNode _next;
    
    public RectNode(RectangleA r)
    {
         _rect = r;   
         _next = null;
    }
        
    public RectNode(RectangleA r,RectNode n)    
    {    
        _rect = r;        
        _next = n;  
    }
    
    public RectNode(RectNode other) 
    {
        _rect = other._rect;
        _next =other._next;
    }
    
    public RectangleA getRect()
    {
        return _rect;
    }
        
    public RectNode getNext() 
    {
        return _next;
    }

    public void setRect(RectangleA r) 
    {
        _rect = r;
    }

    public void setNext (RectNode next) 
    {
        _next = next;
    }   
}

这是 RecList 的一部分，我有一个问题：

public class RectList
{
    private RectNode _head;
    public RectList()
    {
        _head = null;
    }
   
public void addRect(RectangleA t)
{
    RectNode value = new RectNode(t,null);
    RectNode next = new RectNode(t,_head);
    while(next.getNext() != null) 
    {
        next = next.getNext();
    }
}

我想要顺序是先进先出，但是通过这个只管理先进后出：

public void addRect(RectangleA t)
{
     RectNode next = new RectNode(t,_head);
     _head = next;
}

那么我如何按照我需要的方式来做呢？我尝试运行通过 next.getNext() 遍历列表，直到 next是null，但是无法通过代码找出并实现它。

Answer 1

这些是 addRect 中的问题：

value 没有分配给与列表相关的任何内容，因此未添加节点。
当 null

_head

如果打算创建一个位于 _head 中的虚拟节点（这可能是一种有效的方法），那么在循环中离开该节点会破坏这个想法：你有for ever 丢失了对该虚拟节点的引用，但您需要它来更新 _head（如果它是 null）

有几种方法可以做到这一点，我从你的代码中了解到你想要引入一个虚拟节点，它位于当前 _head 的前面。但是然后你需要对 stay 的另一个引用，一个没有被循环修改的引用。

我也会使用不同的变量名。 value 给人的印象是它是关于一个节点的值，但事实并非如此：它是一个节点——要添加的节点——所以我只称它为 newNode 如果你真的需要变量。 next 这个名字暗示它指的是它之前的东西，但这在这里似乎无关紧要。因为它的目的是识别列表的尾部，为什么不叫它tail？

1。使用虚拟节点的解决方案

public void addRect(RectangleA t)
{
    final RectNode preHead = new RectNode(t, _head); // This reference will stay here
    RectNode tail = preHead; // This reference will traverse the list
    while (tail.getNext() != null) 
    {
        tail = tail.getNext();
    }
    // Now create and append the new node immediately after the tail node:
    tail.setNext(new RectNode(t, null));
    // Set the new head (in case it was null, this is relevant)
    _head = preHead.getNext();
}

2。没有虚拟节点的解决方案

虽然withdummy node的解决方案不用区分空列表和非空列表的情况，但是可以避免使用dummy node的时候做分别处理这些情况：

public void addRect(RectangleA t)
{
    if (_head == null) { // Special case, the only one where _head must change
        _head = new RectNode(t, null);
    } else { // The list is not empty, and _head will not change
        RectNode tail = _head;
        while (tail.getNext() != null) 
        {
            tail = tail.getNext();
        }
        // Now create and append the new node immediately after the tail node:
        tail.setNext(new RectNode(t, null));
    }
}

链表并将元素添加到列表的末尾

Linked list and adding elements to the end of the list

java

linked-list

1。使用虚拟节点的解决方案

2。没有虚拟节点的解决方案