java - Java中的链表代码

Question

我正在观看提供的有关数据结构和算法的视频 here

首先链表的代码是这样写的

public class SListNode{
    public Object item;
    public SListNode next;
    public SListNode(Object item,SListNode next){
        this.item=item;
        this.next=next; 
    }
    public SListNode(Object item){
        this(item,null);
    }
    public void insertAfter(Object item){
        next=new SListNode(item,next);  
    }
    public SListNode nth(int position){
        if (position==1){
            return this;
        }
        else if ((position<1)|| next==null){
            return null;
        }
        else{
            return next.nth(position-1);
        }

    }

然后讲师说这个实现有两个问题。

1) 如果 X 和 Y 引用同一个列表，并且如果向 x 插入了一个新项目，则 y 不会更新。我认为这可以通过

检查

public static void main (String args[]){
        SListNode l1=new SListNode("milk",new SListNode(0,new SListNode(1)));
        SListNode l2=l1;
        l2=new SListNode("soap",l2);
        System.out.println(l1.item+ " "+l1.next.item+ " " +l1.next.next.item);
        System.out.println(l2.item+ " "+l2.next.item+ " " +l2.next.next.item);  

2) 创建空列表时。

因此，作为一种解决方案，创建了维护列表头部的单独 SListClass。

public class SList{
    privte SListNode head;
    private int size;
    public SList(){
        head=null;
        size=0;
    }
    public void insertFront(Object item){
    head=new SListNode(item,head);
    }
}

我不明白如何使用 SList 类。
如何用这个类创建链表？

SListNode和Slist类是如何连接的，SList中如何调用SlistNode的方法？
此外，如果 X 和 Y 引用同一个列表，并且如果向 x 插入新项目，y 不会更新，那么这个新实现如何为早期问题提供解决方案。

我是编程和 Java 的新手，因此最好有一个清晰的解释

Answer 1

你这里有一个经典的 LinkedList 实现。 SListNode 表示列表的单个节点，而SList 基本上表示整个列表。它管理列表的头部(通常还有一些其他属性，例如列表的大小，可能是对列表尾部的引用等)。

您通常会在代码中仅使用SList，它封装和管理您的单个SListNode。为此，SList 需要“字典方法”来插入、删除、查找列表中的对象等(这些对象封装在由 SList 管理的 SListNode 元素中)。这就是为什么我认为您上面的 SList 类尚未完成。

您的代码示例

SListNode l1=new SListNode("milk",new SListNode(0,new SListNode(1)));
SListNode l2=l1;
l2=new SListNode("soap",l2);

不显示讲师所说的内容。您在这里所做的是创建一个引用 l1 的 SListNode。然后创建一个新的 SListNode-Object 并将 l2 指向它(然后创建一个对其自身的“循环引用”)。当然 l1 和 l2 不再引用同一个对象!