單鏈表實現

Question

public class SinglyLinkedList implements Lista { 
private final Element _headAndTail = new Element(null); 
private int _size; 

public SinglyLinkedList() { 
    clear(); 
} 

private static final class Element { 

    private Object _value; 
    private Element _next; 

    public Element(Object value) { 
     setValue(value); 
    } 

    public void setValue(Object value) { 
     _value = value; 
    } 

    public Object getValue() { 
     return _value; 
    } 

    public Element getNext() { 
     return _next; 
    } 

    public void setNext(Element next) { 
     assert next != null : "Wskaźnik na element następny nie może być pusty"; 
     _next = next; 
    } 

    public void attachBefore(Element e) { 
     setNext(e); 
     e.setNext(this); 
    } 
} 

public void insert(int index, Object value) 
     throws IndexOutOfBoundsException { 
    if (index < 0 || index > _size) 
     throw new IndexOutOfBoundsException(); 
    Element element = new Element(value); 
    element.attachBefore(getElement(index)); 
    ++_size; 
} 

private Element getElement(int index) { 
    return getElementForwards(index); 
} 

private Element getElementForwards(int index) { 

    Element element = _headAndTail.getNext(); 
    for (int i = index; i > 0; --i) 
     element = element.getNext(); 
    return element; 
} 

private void checkOutOfBounds(int index) throws IndexOutOfBoundsException { 
    if (index < 0 || index >= size()) 
     throw new IndexOutOfBoundsException(); 
} 

public void add(Object value) { 
    insert(size(), value); 
} 

public int size() { 
    return _size; 
} 

public Object get(int index) throws IndexOutOfBoundsException { 
    checkOutOfBounds(index); 
    return getElement(index).getValue(); 
} 

public Object set(int index, Object value) throws IndexOutOfBoundsException { 
    checkOutOfBounds(index); 
    Element element = getElement(index); 
    Object oldValue = element.getValue(); 
    element.setValue(value); 
    return oldValue; 
} 

public Object delete(int index) throws IndexOutOfBoundsException { 
    checkOutOfBounds(index); 
    Element element = getElement(index); 
    --_size; 
    return element.getValue(); 
} 

public boolean delete(Object value) { 
    Element e = _headAndTail.getNext(); 
    while (e != _headAndTail && !value.equals(e.getValue())) 
     e = e.getNext(); 
    if (e != _headAndTail) { 
     --_size; 
     return true; 
    } 
    else 
     return false; 
} 

public boolean contains(Object value) { 
    return indexOf(value) != -1; 
} 

public void clear() { 
    _headAndTail.setNext(_headAndTail); 
    _size = 0; 
} 

public int indexOf(Object value) { 
    int index = 0; 
    Element e = _headAndTail.getNext(); 
    while (e != _headAndTail && !value.equals(e.getValue())) { 
     e = e.getNext(); 
     ++index; 
    } 
    return e != _headAndTail ? index : -1; 
} 

public boolean isEmpty() { 
    return _size == 0; 
} 

public Iterator iterator() { 
    return new ValueIterator(); 
} 

private final class ValueIterator implements Iterator { 

    private Element _current = _headAndTail; 

    public void first() { 
     _current = _headAndTail.getNext(); 
    } 

    public void last() { 
    } 

    public boolean isDone() { 
     return _current == _headAndTail; 
    } 

    public void next() { 
     _current = _current.getNext(); 
    } 

    public void previous() { 
    } 

    public Object current() throws IndexOutOfBoundsException { 
     if (isDone()) 
      throw new IndexOutOfBoundsException(); 
     return _current.getValue(); 
    } 
} 

}

這是我的代碼，它編譯沒有任何問題，我做了雙向鏈表這樣它的工作沒有任何問題，當我把它改爲單它不會添加對象到列表中會很好，如果有人可以看看 - 我認爲問題是Element類中的方法insert(int index, Object value)和attachBefore(Element e)。

Answer 1

Element.attachBefore(e)有一個概念問題。基本上不可能爲單向鏈表實現該方法。相反，您必須在要插入的位置之前找到Element，並在之後插入新的Element。 （和處理，你在列表的開始插入的特殊情況。）

我會離開你通過細節工作...

但納蘭德的評論是即期。如果您無法弄清楚當前版本的代碼在做什麼，請使用IDE的Java調試器運行它，並通過調用給您的方法來單步調試。