使用LinkedList实现ArrayList

Question

我需要通过使用内部LinkedList来实现队列和数组列表。我创建了我的DoublyLinkedList类，并能够将其实现到我的队列中，没有任何问题。我遇到的问题是，要向ArrayList添加或删除，添加/删除方法需要一个整数作为索引和一个对象/元素。DoublyLinkedList类中的所有方法都接受元素和/或节点。

我的问题是，当我的DLL类不接受任何int值时，我如何在我的ArrayList中实现我的DoublyLinkedList方法。

我希望能够通过使用索引来添加或删除节点，但是我不能。实际上，我想要类似list.addAfter(I)的东西，而不是I是整数。

注意:这个任务的目标是实现ADT，所以我不能修改ArrayList ADT的方法签名。

DoublyLinedList Class

public class DoublyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public DoublyLinkedList() {
    this.head = new Node<E>(null, null, null);
    this.tail = new Node<E>(null, null, null);
    this.size = 0;
    head.setNext(tail);
    tail.setPrev(head);
}
public int size() {
    return size;
}
public boolean isEmpty() {
    return size == 0;
}
public Node<E> getPrev(Node<E> n) {
    return n.getPrev();
}
public Node<E> getNext(Node<E> n) {
    return n.getNext();
}
public Node<E> getFirst() {
    return head.getNext();
}
public Node<E> getLast() {
    return tail.getPrev();
}
public E remove(Node<E> c) {
    Node<E> a = c.getPrev();
    Node<E> b = c.getNext();
    b.setNext(a);
    a.setPrev(b);
    c.setNext(null);
    c.setPrev(null);
    size--;
    return c.getElement();
}
public E removeFirst() {
    return remove(head.getNext()); // first element is beyond header
}
public E removeLast() {
    return remove(tail.getPrev());
}
public void addBefore(Node<E> node, E e) {
    Node<E> prev = getPrev(node);
    Node<E> n = new Node<E>(e, prev, node);
    node.setPrev(n);
    prev.setNext(n);
    size++;
}
public void addFirst(E e) {
    addAfter(head, e);
}
public void addLast(E e) {
    addBefore(tail, e);
}
public void addAfter(Node<E> node, E e) {
    Node<E> next = getNext(node);
    Node<E> n = new Node<E>(e, node, next);
    node.setNext(n);
    next.setPrev(n);
    size++;
}
}

LArrayList类(我的Arraylist实现)

public class LArrayList implements List {
private DoublyLinkedList list;
private int size;
public LArrayList() {
    this.list = new DoublyLinkedList();
    this.size = 0;
}
public int size() {
    return size;
}
public boolean isEmpty() {
    return size == 0;
}
public void add(int I, Object e) throws IndexOutOfBoundsException {
    if (isEmpty()) {
        list.addFirst(e);
    }
    // HERE IS MY CONCERN. THESE FOUR METHODS ALL TAKE IN INT VALUES WHILE
    // NON OF MY DLL METHODS DO!
}
public Object get(int i) throws IndexOutOfBoundsException {
    return null;
}
public Object remove(int i) throws IndexOutOfBoundsException {
    return null;
}
public Object set(int I, Object e) throws IndexOutOfBoundsException {
    return null;
}
}

Answer 1

public Object get(int i) throws IndexOutOfBoundsException {
    if(list.size()<=i) throw new IndexOutOfBoundsException();
    Node current = list.getFirst();
    for(int x = 0; x<=i; x++){
       if(x == i) return current.getElement();//Change this behaviour for remove and set
       current = current.getNext();
    }
}

Answer 2

这似乎是一件相当容易的事情-只需使用您的LinkedList公开的API并向其添加一些逻辑。这是您缺少的部分

if (list.size() < I) {
    throw new IndexOutOfBoundsException()
}
//get a starting point
Node node = list.getFirst();
//loop until you get to the specified position
while(I-- > 0) {
    node = list.getNext(node);
} 
//now node points at the node in position I - insert the new
//node before it to comply with the List interface
list.addBefore(node, e);
this.size++;

我必须注意到你的LinkedList实现可以改进——首先，getPrev() getNext() addBefore()和addAfter()应该是静态的，因为你不应该使用LinkedList实例来调用它们。然而，如果这些方法实际上是Node中的方法，那就更好了，因为那样的话，LinkedList的遍历和使用就会容易得多。如果方法在Node:

中，上面的代码看起来是这样的:

if (list.size() < I) {
    throw new IndexOutOfBoundsException()
}
//get a starting point
Node node = list.getFirst();
//loop until you get to the specified position
while(I-- > 0) {
    node = node.getNext();
} 
//now node points at the node in position I - insert the new
//node before it to comply with the List interface
node.addBefore(e);
this.size++;

你几乎根本不需要列表——当然你不需要只是向一些函数传递额外的参数。你仍然可以在链表中保留做同样事情的方法(希望是静态的)，但它们只是方法的Node实现的代理，例如:

public static void addAfter(Node<E> node, E e) {
    node.addAfter(e);
}

我不确定你是否需要在LinkedList中使用这些方法，但如果你愿意的话，它们肯定可以用于"向后遵从"。

第一个代码位是add()的实现，我相信你可以解决剩下的，因为他们会做同样的事情。