不使用标准库创建链表的子列表

Question

我正在尝试弄清楚如何在不使用标准库的情况下创建链表的子列表进行练习。

我有一个解决方案编码，但我不确定它是否正常工作。我没有出现任何编译错误，但如果有更好的方法或是否应该进行更正，我想征求第二意见。

LinkedListclass基本实例变量

public class LinkedList<E> implements DynamicList<E> {

    LLNode<E> head;
    LLNode<E> tail;
    int llSize;



    LinkedList(){
        this.head = null;
        this.tail = null;
        this.llSize =0;
    }

get 方法寻址 LinkedList 索引

@Override
    public E get(int index) {
        LLNode<E> current = this.head;
        while(current.nextPointer != null){
            if(index == current.getIndex()){
                return current.getObj();
            }else{
                current = current.nextPointer;
            }
        }
        return null;
    }

节点class

public class LLNode<E>{
    E obj;
    LLNode<E> previousPointer;
    LLNode<E> nextPointer;
    int index;

    public LLNode(E obj){
        this.obj = obj;
        this.index=0;
    }

    public E getObj() {
        return obj;
    }

    public LLNode<E> getPreviousPointer() {
        return previousPointer;
    }

    public LLNode<E> getNextPointer() {
        return nextPointer;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }
}

子列表方法

@Override
    public DynamicList<E> subList(int start, int stop) {
        DynamicList<E> newDynamicList = new LinkedList<>();
        for(int i = start; i<stop; i++){
            newDynamicList.add(get(i));
        }


        return newDynamicList;
    }

Answer 1

如我所见，这是一个双向链表。正如评论中所建议的那样，避免将索引用作节点本身的一部分，索引是列表的一部分，因为列表控制遍历每个节点以执行任何操作（添加、删除、查找等）的方式

我的建议（对于子列表）：

检查子列表是否在你的列表大小之内（你可以抛出一些异常或者return一些默认数据，这取决于你的设计）
将索引控件移至列表
为了获取子列表，您可能需要获取子列表的起始节点，然后使用 nextPointer 遍历下一个节点。您可以计算子列表的大小并使用它来控制何时必须停止

public DynamicList<E> subList(int start, int stop) {
        DynamicList<E> newDynamicList = new LinkedList<>();

        //here, you can validate the subList conditions to work (size, boundaries, etc)
        //an exception may be thrown if parameters do not meet some criteria

        int subListSize = stop - start;

        LLNode<E> current = get(start);

        while(newDynamicList.size() < subListSize){
            //Consider cloning the node and add it to the sublist
            newDynamicList.add(current);
            current = current.nextPointer;
        }

        return newDynamicList;
    }

不使用get方法检索每个节点的主要原因是get操作每次调用时都从头开始搜索节点。最好获取起始节点并从那里开始遍历节点。

不要忘记创建的子列表将包含对原始列表节点的引用。我建议克隆元素以避免影响原始节点

不使用标准库创建链表的子列表

Create a sublist of a linked list without using standard library

java

linked-list

sublist