Linked list and adding elements to the end of the list

Issue

I need to create linked list of rectangles. Im given the class files of rectangleandpointclasses, and need to writeRectNodeandRectList`.

This is 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;
    }   
}

And this is part of RecList which I have a problem with:

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();
    }
}

I want the order to be first-in first-out, but managed only first-in last-out by this:

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

So how I do that the way I need? I tried running trough the list by next.getNext() until the next is null, but can`t figure out by code and implement it.

Solution

These are the issues in addRect:

• There is no assignment of value to anything that relates to the list, so the node is not added.
• There is no provision to update _head when it was null
• If it was intended to create a dummy node that sits in from of _head (which can be a valid approach), then this idea is destroyed by walking away from that node in the loop: you have for ever lost the reference to that dummy node, yet you would need it to update _head (in case it was null)

There are several ways to do this, and I understand from your code that you want to introduce a dummy node, that sits in front of the current _head. But then you would need another reference to stay there, one that is not modified by the loop.

I would also use different variable names. value gives the impression that it is about a node's value, but this is not the case: it is a node -- the one to be added -- so I'd just call it newNode if you really need the variable at all. The name next suggests that it refers to something that precedes it, but that seems irrelevant here. As its purpose is to identify the tail of the list, why not call it tail?

1. Solution using a dummy node

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. Solution without dummy node

Although the solution with the dummy node does not have to distinguish between the case of an empty and non-empty list, you can avoid the use of the dummy node when you do deal separately with these cases:

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));
    }
}

Answered By - trincot