如何在Java中使用DoublyLinkedList编写添加/插入方法

本文介绍了如何在Java中使用DoublyLinkedList编写添加/插入方法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要有关Java中add方法的帮助。它与DoublyLinked List一起使用。

I need help with my add method in java. It works with DoublyLinked List.

我正在实现一个循环的DoublyLinkedList数据结构。像单链链表一样，双链表中的节点也具有对下一个节点的引用，但与单链链表不同，双链表中的节点也具有对前一个节点的引用。此外，由于列表是循环的，因此列表中最后一个节点中的下一个引用指向列表中的第一个节点，列表中第一个节点中的上一个引用指向列表中的最后一个节点

I am implementing a cyclic DoublyLinkedList data structure. Like a singly linked list, nodes in a doubly linked list have a reference to the next node, but unlike a singly linked list, nodes in a doubly linked list also have a reference to the previous node. Additionally, because the list is "cyclic", the "next" reference in the last node in the list points to the first node in the list, and the "prev" reference in the first node in the list points to the last node in the list.

该方法应该做的是将value参数插入列表中的指定索引。确保解决列表为空和/或添加的元素为列表中第一个元素的情况。如果index参数无效，则应该抛出IndexOutOfBoundsException。

What the method is suppose to do is insert the value parameter at the specified index in the list. Be sure to address the case in which the list is empty and/or the added element is the first in the list. If the index parameter is invalid, an IndexOutOfBoundsException should be thrown.

这是我的以下代码：

public class DoublyLinkedList<E> { private Node first; private int size; @SuppressWarnings("unchecked") public void add(E value) { if (first == null) { first = new Node(value, null, null); first.next = first; first.prev = first; } else { first.prev.next = new Node(value, first, first.prev); first.prev = first.prev.next; } size++; } private class Node<E> { private E data; private Node next; private Node prev; public Node(E data, Node next, Node prev) { this.data = data; this.next = next; this.prev = prev; } }

这是失败的方法。我将对我坚持的那一行进行评论，但除此之外，从我听到的内容来看，前几行所做的都是正确的。

Here is the method where it fails. I will comment the line where I'm stuck on, but other than that, what is done in the previous lines is correct from what I heard.

@SuppressWarnings("unchecked") public void add(int index, E value) { if(index < 0) { throw new IndexOutOfBoundsException(); } if(index > size) { throw new IndexOutOfBoundsException(); } if (first.data == null) { throw new NullPointerException(); } if (index == 0) { first = new Node(value, null, null); first.next = first; first.prev = first; } else { Node current = first; for (int i = 0; i < index; i++) { current = current.next; } current.prev.next = new Node(value, current, current.prev); // This is the line where I get lost on. current.prev = current.prev.next; } size++; }

其余的代码在这里。请专注于我正在研究的方法。谢谢！

The rest of my code is here. Please focus on the method I'm working on. thank you!

@SuppressWarnings("unchecked") public void remove(int index) { if(index < 0) { throw new IndexOutOfBoundsException(); } if(index > size) { throw new IndexOutOfBoundsException(); } if (first.data == null) { throw new IndexOutOfBoundsException(); } else if (index == 0) { first = first.next; } else { Node current = first.next; for (int i = 0; i < index; i++) { current = current.next; } // current.prev = current.next; current.next = current.next.next; } size--; } @SuppressWarnings("unchecked") public E get(int index) { if(index < 0) { throw new IndexOutOfBoundsException(); } if(index > size) { throw new IndexOutOfBoundsException(); } Node current = first; for (int i = 0; i < index; i++) { current = current.next; } return (E) current.data; } @SuppressWarnings("unchecked") public int indexOf(E value) { int index = 0; Node current = first; while (current != current.next) { if (current.data.equals(value)) { return index; } index++; current = current.next; } return index; } public boolean isEmpty() { if (size == 0) { return true; } else { return false; } } public int size() { return size; } @SuppressWarnings("unchecked") public String toString() { if (isEmpty()) { return "[]"; } else { String result = "[" + first.data; Node current = first.next; for(int i = 0; i < size-1; i++) { result += ", " + current.data; current = current.next; } result += "]"; return result; } } }

推荐答案

这一点都不容易，但是我找到了问题的答案。

This was not easy at all, however I figured out the answer to my question.

@SuppressWarnings("unchecked") public void add(int index, E value) { if(index > size || index < 0) { throw new IndexOutOfBoundsException(); } if (first == null) { Node n = new Node(value, null, null); n.next = n; n.prev = n; first = n; } else { Node current = first; for (int i = 0; i < index; i++) { current = current.next; } //current points to node that will follow new node. Node n2 = new Node(value, current, current.prev); current.prev.next = n2; current.prev = n2; //update first if necessary. if(index == 0) { first = n2; } } size++; }