在不使用标准库的情况下创建链接列表的子列表

Question

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

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

LinkedList类基本实例变量

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

获取寻址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;
}

节点类

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

Sublist方法

@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

正如我所看到的，这是一个双链接列表。正如评论中所建议的，避免使用索引作为节点本身的一部分，索引是列表的一部分。因为列表控制着每个节点执行任何操作(添加、删除、查找等(的方式。

我的建议(分列表(：

• 检查子列表是否在您的列表大小内(您可以抛出一些异常或返回一些默认数据，这取决于您的设计(
• 将索引控件移动到列表
• 为了获取子列表，您可能需要获取子列表的起始节点，然后使用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操作时，它都会从头开始搜索节点。最好获取起始节点，然后从那里开始遍历节点。

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