我在双向链表的 Java 实现中做错了什么？

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

Answer 1

事实上你的双向链表应该有以下变量：

1. int 大小 - 它是列表的大小，它允许您以 O(1) 复杂度返回大小
2. 节点头 - 它链接到列表的头（第一个节点）
3. 节点尾 - 它链接到列表的尾部（最后一个节点）

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

Answer 2

班级名单{

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

}

}

除了“额外”的方法，insert 和 extract 方法可能对你有帮助。我使用一种方法在项目之间移动。我认为使用“first”和“currentPosition”属性可以更轻松地构建方法。在包括节点引用或蜜蜂引用在内的每种方法中，您都需要检查是否有空引用其他内容的可能性（它会“破坏”您的程序）；但如果一个节点引用一个空值，就没有问题。