创建一个链表的子列表,不使用标准库。

huangapple go评论72阅读模式
英文:

Create a sublist of a linked list without using standard library

问题

我正在尝试弄清楚如何在练习中创建一个链表的子列表,而不使用标准库。

我已经编写了一个解决方案,但我不确定这是否正常工作。我没有遇到任何编译错误,但希望得到第二意见,看是否有更好的方法来做这个,或者是否应该进行更正。

链表类基本实例变量

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

获取方法处理链表索引

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

子列表方法

@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;
}
英文:

I'm trying to figure out how to create a sublist of a linked list without using the standard library for a practice exercise.

I have a solution coded but I'm not sure if this is working properly. I don't have any compile errors that are coming up but wanted a second opinion if there is a better way to do this or if corrections should be made.

LinkedList class basic instance variables

public class LinkedList&lt;E&gt; implements DynamicList&lt;E&gt; {

    LLNode&lt;E&gt; head;
    LLNode&lt;E&gt; tail;
    int llSize;



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

get method addressing LinkedList index

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

Node class

public class LLNode&lt;E&gt;{
    E obj;
    LLNode&lt;E&gt; previousPointer;
    LLNode&lt;E&gt; nextPointer;
    int index;

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

    public E getObj() {
        return obj;
    }

    public LLNode&lt;E&gt; getPreviousPointer() {
        return previousPointer;
    }

    public LLNode&lt;E&gt; getNextPointer() {
        return nextPointer;
    }

    public int getIndex() {
        return index;
    }

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

Sublist method

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


        return newDynamicList;
    }

答案1

得分: 1

根据我所看到的情况,这是一个双向链表。正如评论中所建议的,避免将索引作为节点本身的一部分,索引是列表的一部分,因为列表控制着对每个节点进行遍历以执行任何操作(添加、删除、查找等)。

我的建议(针对子列表):

  • 检查子列表是否在您的列表大小范围内(您可以抛出异常或返回一些默认数据,这取决于您的设计)。
  • 将索引控制移到列表中。
  • 对于获取子列表,您可以像获取子列表的起始节点一样,然后使用“nextPointer”遍历下一个节点。您可以计算子列表的大小,并使用它来控制何时停止。
public DynamicList<E> subList(int start, int stop) {
    DynamicList<E> newDynamicList = new LinkedList<>();

    // 在这里,您可以验证子列表条件是否能够工作(大小、边界等)
    // 如果参数不满足某些条件,可能会抛出异常

    int subListSize = stop - start;

    LLNode<E> current = get(start);

    while(newDynamicList.size() < subListSize){
        // 考虑克隆节点并将其添加到子列表
        newDynamicList.add(current);
        current = current.nextPointer;
    }

    return newDynamicList;
}

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

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

英文:

As I'm seeing, that is a double linked list. As is suggested in comments, avoid using an index as part of the node itself, the index is part of the List, because the list controls the way each node is traversed to perform any operation (add, remove, find, etc)

My suggestion (for sublist):

  • Check if the sublist is within the size of your list (you can throw some exception or return some default data, it depends on your design)
  • Move the index control to the list
  • For getting the sublist, you might have something like get the start node of the sublist, and then, use the nextPointer to traverse through the next nodes. You can calculate the size of the sublist and use that to control when you have to stop
public DynamicList&lt;E&gt; subList(int start, int stop) {
        DynamicList&lt;E&gt; newDynamicList = new LinkedList&lt;&gt;();

        //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&lt;E&gt; current = get(start);

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

        return newDynamicList;
    }

The main reason for not using the get method for retrieve each node is that get operation search for the node from the beginning each time you call it. It is better to get the start node and start traversing the nodes from there.

Don't forget that created Sublist will contain a reference to the original list nodes. I suggest to clone the elements for avoiding affect the original node

huangapple
  • 本文由 发表于 2020年10月21日 03:31:15
  • 转载请务必保留本文链接:https://go.coder-hub.com/64452114.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定