在我的双链表的Java实现中,我做错了什么?[关闭]

trnvg8h3  于 2023-05-21  发布在  Java
关注(0)|答案(2)|浏览(103)

已关闭,此问题需要更focused。目前不接受答复。
**想改善这个问题吗?**更新问题,使其仅通过editing this post关注一个问题。

昨天关门了。
Improve this question
我试图创建一个双重链接的列表在java和只是需要一点指导,因为我也去错了。我还希望能够设置一个列表的容量以及。
这是我目前掌握的情况:

public class LRU(int capacity){
    int data;
    Node previous;
    Node next;

    public void Node(int data){
        this.data = data;

     }
    Node head,tail = null;

    public void addNode(int data){
        Node newNode;
        newNode = new Node(data);

    if(head == null){
        head = tail = newNode;

        head.previous = null;

        tail.next = null;
    }else{
        tail.next = newNode;
        newNode.previous = tail;
        tail = newNode;
        tail.next= null;
    }
}
z18hc3ub

z18hc3ub1#

实际上,你的双向链表应该有以下变量:

  1. int size -它是你的列表的大小,它允许你以O(1)的复杂度返回大小
    1.节点头-它是指向列表头的链接(第一个节点)
  2. Node tail -它链接到列表的尾部(最后一个Node)
    Previous和Next Nodes应该在类'Node'中声明。这意味着每个节点都将链接到上一个和下一个节点。
    这里是一个小例子,但最好使用泛型来使列表更灵活(这样它就可以支持不同的类型,而不仅仅是int):
public class DoublyLinkedList {
    private int size;
    private Node head;
    private Node tail;

    public void addFirst(int value) {
        size++;

        // already have head (list not empty)
        if (head != null) {
            // creating new "head" element, old "head" now has previous value
            head.previous = new Node(null, value, head);
            head = head.previous; // update head
            return;
        }

        // empty list, so create first node
        head = new Node(null, value, null);
        tail = head; // because we have only one element, and it also becomes tail
    }

    public void add(int value) {
        size++;

        // already have tail (list not empty)
        if (tail != null) {
            tail.next = new Node(tail, value, null); // creating new "tail" node with given value, old "tail" now has next value
            tail = tail.next; // update tail
            return;
        }

        // empty list, so create first node
        if (head == null) {
            head = new Node(null, value, null);
            tail = head; // because we have only one element, and it also becomes tail
        }
    }

    public int getSize() {
        return size;
    }

    private static class Node {
        private Node previous;
        private Node next;
        private int data;

        public Node(Node previous, int data, Node next) {
            this.previous = previous;
            this.data = data;
            this.next = next;
        }
    }
}
rdlzhqv9

rdlzhqv92#

class List {

// nested class
public class Node {
    Node next;
    Node previous;
    float data;

    public Node(Node next, float data) {
        this.next = next;
        this.data = data;
    }

    public Node(float elem) {
        this(null, elem);
    }
}

private Node first;
private Node currentPosition;

int size;

public void forward(int numPositions) {
    if (numPositions > 0 && first != null) {
        int positionsForward = numPositions;
        if (currentPosition == null) {
            currentPosition = first;
            positionsForward--;
        }
        while (currentPosition.next != null && positionsForward > 0) {
            currentPosition = currentPosition.next;
            positionsForward--;
        }
    }
}

public void insert(float data) {
    Node node = new Node(data);

    if (currentPosition == null) {
        // inserts in first node
        node.next = first;
        if (first != null) {
            first.previous = node;
        }
        first = node;
    } else {
        // the node isn't the first.
        node.next = currentPosition.next;
        node.previous = currentPosition;
        if (currentPosition.next != null) {
            currentPosition.next.previous = node;
        }
        currentPosition.next = node;
    }

    // updates current position
    currentPosition = first;
    size++;
}

public Object extract() {
    Object data = null;

    if (currentPosition != null) {
        data = currentPosition.data;

        // 'delete' the node
        if (first == currentPosition) {
            first = currentPosition.next;
        } else {
            currentPosition.previous.next = currentPosition.next;
        }

        if (currentPosition.next != null) {
            currentPosition.next.previous = currentPosition.previous;
        }

        // next position
        currentPosition = currentPosition.next;
    }

    size--;
    return data;
}

public Object pop(){

    return currentPosition.data;

}

public void divide(){ //questao 1

    List half2 = new List();

    for(int i = 0; i < Math.floorDiv(size, 2); i++){

        half2.insert((Float) this.extract());

    }

    //debugar

    for(int i = 0; i < half2.size; i++){

        System.out.println(half2.extract());

    }

}

public float soma(){ //questao 2

    float sum = 0f;

    currentPosition = first;

    for (int i = 0; i < size; i++){

        sum += (Float) this.pop();

        this.forward(1);

    }

    currentPosition = first;

    return sum;

}

public void extrairMenores(float check){ //questao 3

    currentPosition = first;

    for(int i = 0; i < size; i++){

        if(currentPosition.data < check){

            System.out.println("if aq");

            this.extract();

        } else{

            System.out.println("else aq");

            this.forward(1);

        }

    }

    currentPosition = first;

}

public boolean igualdadeCheck(List outra_lista){ //questao 4

    currentPosition = first;

    outra_lista.currentPosition = first;

    for(int i = 0; i < size; i++){

        if(currentPosition.data - outra_lista.currentPosition.data != 0){

            return false;

        }

        forward(1);

        outra_lista.forward(1);

    }

    currentPosition = first;

    return true;

}

}
除了“额外”方法外,插入和提取方法可能会对您有所帮助。我使用一种方法在项目之间移动。我认为使用“first”和“currentPosition”属性使方法的结构化更容易。在每个方法(包括节点引用或被引用)上,您需要检查是否有null引用其他内容的可能性(这将“破坏”您的程序);但是如果节点引用空,则没有问题。

相关问题