在java中删除位于特定索引的双链表中的节点

我已经创建了一个双链表，它将新节点附加到双链表中。我目前正试图在一个特定的索引删除节点的工作。这是我的节点类，它初始化了三个变量，next和previous，并从我的学生类中导入对象。难道for循环不应该迭代到输入的索引值，然后重定向到下一个值吗?

Node等级:

public class Node {
    Student student;
    Node next;
    Node previous;
    public Node(Student student) {
        this.student = student;
        this.next = null;
        this.previous = null;
    }
    @Override
    public String toString() {
        return student.toString();
    }
}

DoublyLinkedList Class:

public class DoublyLinkedList <T extends Comparable<T>> {
    protected Node head;
    protected Node tail;
    int size=0;
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }
    public Node append(Student student) {
        Node append = new Node(student);
        if (head == null) {
            head = append;
            tail = append;
        }
        else {
            append.previous = tail;
            tail.next = append;
            tail = tail.next;
        }
        size++;
        return append;
    }
    public void delete(int location) throws IllegalArgumentException {
        Node current = head;
        int counter = 1;
        int i;
        // Exception error for cases in which there are no nodes
        if (head == null || location < 0)
            throw new IllegalArgumentException("Sorry but the DLL is NULL, please add nodes");
        // Cases in which the person wants to delete the head at index 0
        if (location == 0) {
            /* If the node that is next is not null we make that the head
             */
            if (head.next != null) {
                head.next.previous = head;
            }
        }
        for (i = 1; head != null && i < location; i++) {
            head = head.next;
        }
        if (head == null)
            head = head.next.previous;
    }
}

我相信我为头为空、输入负值和删除头节点的情况所做的情况是正确的。我认为问题是迭代给定的参数(节点的索引被删除)。我做了一个for循环，迭代到给定的索引。我想做的是，一旦head的值达到输入的参数，它将重定向它迭代到的Node的下一个。这个逻辑是正确的，语法是错误的，还是像这样的情况有另一种逻辑?

您的DoublyLinkedList类是通用的。因此类Node也应该是泛型的。因此，类Student需要实现接口Comparable。

由于您有一个双链表，方法delete也需要更新DoublyLinkedList类中的tail。

由于类DoublyLinkedList有成员size，方法delete也需要更新该成员

因为类DoublyLinkedList有成员size，所以方法delete的参数location在不为负且小于size的情况下有效。

方法delete需要处理三种不同的情况:

删除DoublyLinkedList中的第一个Node。
- 您还需要处理DoublyLinkedList中只有一个Node的情况。
您正在删除DoublyLinkedList中最后一个Node。
您正在删除一个既不是第一个也不是最后一个的Node。
- 您还需要处理删除第二个最后一个Node的情况。

你没有为Student类发布代码，所以我只是编了一个类。

在下面的代码中，我在DoublyLinkedList类中添加了toString方法，只是为了帮助"可视化"。列表。

我还在类DoublyLinkedList中添加了一个main方法来演示delete方法的使用。

public class DoublyLinkedList<T extends Comparable<T>> {
    protected Node<T> head;
    protected Node<T> tail;
    int size = 0;
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }
    public Node<T> append(T student) {
        Node<T> append = new Node<>(student);
        if (head == null) {
            head = append;
            tail = append;
        }
        else {
            append.previous = tail;
            tail.next = append;
            tail = tail.next;
        }
        size++;
        return append;
    }
    public void delete(int location) throws IllegalArgumentException {
        // Exception error for cases in which there are no nodes
        if (head == null || location < 0 || location >= size)
            throw new IllegalArgumentException("Sorry but the DLL is NULL, please add nodes");
        // Cases in which the person wants to delete the head at index 0
        if (location == 0) {
            head = head.next;
            if (head != null) {
                head.previous = null;
            }
            if (size == 2) {
                tail = head;
            }
        }
        else if (location == size - 1) {
            tail = tail.previous;
            tail.next = null;
        }
        else {
            Node<T> current = head;
            for (int i = 1; i < location; i++) {
                current = current.next;
            }
            current.next = current.next.next;
            if (current.next == null) {
                tail = current;
            }
            else {
                current.next.previous = current;
            }
        }
        size--;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("[%d]:", size));
        Node<T> current = head;
        while (current != null) {
            sb.append(current);
            sb.append('u2192');
            current = current.next;
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        DoublyLinkedList<Student> dll = new DoublyLinkedList<>();
        System.out.println(dll);
        dll.append(new Student());
        System.out.println(dll);
        dll.append(new Student());
        System.out.println(dll);
        dll.append(new Student());
        System.out.println(dll);
        dll.append(new Student());
        System.out.println(dll);
        dll.delete(1);
        System.out.println(dll);
    }
}
class Student implements Comparable<Student> {
    private static int counter;
    private int id;
    public Student() {
        id = ++counter;
    }
    @Override
    public int compareTo(Student o) {
        return id - o.id;
    }
    public boolean equals(Object obj) {
        boolean equal = this == obj;
        if (!equal) {
            if (obj instanceof Student) {
                Student other = (Student) obj;
                equal = id == other.id;
            }
        }
        return equal;
    }
    public int hashCode() {
        return id;
    }
    public String toString() {
        return String.format("%d", id);
    }
}
class Node<T> {
    T student;
    Node<T> next;
    Node<T> previous;
    public Node(T student) {
        this.student = student;
        this.next = null;
        this.previous = null;
    }
    @Override
    public String toString() {
        return student.toString();
    }
}

这似乎是作业，所以我不会给出完整的代码，但指出错误所在。如果不是这样，请随意评论，我会删除这个。这应该是一个注释，但这太长了，不适合在注释部分。

在delete方法中有四件事似乎不正常:

当遍历数组以查找要删除的节点时，头部被修改。

for (i = 1; head != null && i < location; i++) {
     head = head.next;
}

这将永久修改双链表的表头，这意味着在新表头之前的节点将丢失。你应该使用一个变量来迭代(我相信current应该是吗?)

删除头部

当要删除的位置是头部时，确实有额外的工作要做，但是head.next.previous = head;什么也不做:head已经是head.next的上一个节点。

删除尾部时

删除头部和尾部都有额外的工作要做。

你从来没有真正删除任何东西

除了迭代时丢失的节点外，永远不会从列表中删除任何节点。

我建议你从简单的案例开始，看看你当前的实现做了什么，然后试着纠正它。你也可以用笔和纸来画双链表，这可以帮助你建立一个应该做什么步骤的直觉。

当遍历数组以查找要删除的节点时，头部被修改。

删除头部

删除尾部时

你从来没有真正删除任何东西

相关内容

最新更新

热门标签：