链表。头尾参照

Question

我正在尝试为我的链表类创建一个添加和删除方法。我写了两封信，名字是Head和Tail。

头-

当我试图删除特定节点时，我一直遇到问题，因为Java说我越界了。我想是因为我的头没有指向第一个节点？你们觉得怎么样？还是我完全走错路了...

public class LinkedList{

    private Node head;
    private Node tail;
    private int listCount;

    public LinkedList()
    {
        head = new ListNode(null);
        tail = new ListNode(null);
        listCount = 0;
    }

    public void add(Object elem){
        ListNode newNode = new ListNode(elem);
        if (size() == 0){
            newNode = head;
            tail = head;
        }
        newNode.setLink(tail);
        tail = newNode;
        listCount++;
        }

    public Object delete(int index)
    // post: removes the element at the specified position in this list.
    {
        // if the index is out of range, exit
        if(index < 1 || index > size())
            throw new IndexOutOfBoundsException();

        ListNode current = head;
        for(int i = 1; i < index; i++)
        {
            if(current.getLink() == null)
                throw new IndexOutOfBoundsException();

            current = current.getLink();
        }
        current.setLink(current.getLink().getLink());
        listCount--; // decrement the number of elements variable
        return current.getInfo();
    }

    public int size() {
        return listCount;
    }

}

public class Node {

    private Node link;
    private Object info;

    public Node(Object info)
    {
        this.info = info;
        link = null;
    }

    public void setInfo(Object info)
    {
        this.info = info;
    }

    public Object getInfo()
    {
        return info;
    }

    public void setLink(Node link)
    {
        this.link = link;
    }

    public Node getLink()
    {
        return link;
    }
}

Answer 1

我认为这是因为你的头从不链接到任何东西。我要做的是在你的add方法中，检查你列表的size；如果是0，将head设置为新元素，并将尾部等于head。如果是1，将head链接到新节点，并设置end。如果是2，只需设置尾部到新节点的链接，并设置尾部（就像现在一样）。

另外，我不确定您是如何实现它的，但是newNode。setLink（尾部） 似乎错了。。。tail应该链接到newNode。从外观上看，似乎您正在尝试创建newNode-

编辑：好的，这就是我为什么要尝试的原因

public void add(Object elem){
    ListNode newNode = new ListNode(elem);
    if (size() == 0){
        newNode = head;
        tail = head;
    }else if(size() == 1){
        head.setLink(newNode);
        tail = newNode;
    }else{
        tail.setLink(newNode);
        tail = newNode;
    }
    listCount++;
}

Answer 2

看起来您在设置初始（空）链接列表时没有从头到尾初始化链接。

好啊以下是使用单链接列表（仅前向链接）时使用的策略。您需要确定列表上允许哪些操作（例如，仅从头部或尾部添加/删除？；或在链接列表中的任何位置添加和删除节点（删除节点后将列表重新组合在一起）。如果允许从任何位置删除节点，则需要有一种唯一标识每个节点的方法（以便可以明确确定要删除的节点）。您可能还希望能够在其他节点之前或之后添加节点。这可能需要独特性。如果您不在乎在之前/之后删除或添加哪个值，则可以放宽唯一性约束。

现在是战略实施阶段。从一个head开始（最初为null）。

1. 若要添加节点，请沿着链接列表向下走，直到找到空的下一个链接。将其替换为节点，并将节点转发链接设置为null。（提高效率，使尾部始终具有链接列表中的最后一个节点，如果列表中没有任何节点，则为null）

这有用吗？

请查看此链接以获取完整描述！