需要帮助开始实现链表而不是DoubleArraySeq的数组。
认为某些方法(例如确保容量(会过时，所以我将其排除在外。
任何帮助将不胜感激。谢谢。
public class DoubleArraySeq implements Cloneable {
private double[] data;
private int manyItems;
private int currentIndex;
public DoubleArraySeq() {
this(10);
}
public DoubleArraySeq(int initialCapacity) {
if(initialCapacity <= 0) {
throw new IllegalArgumentException("Negative initialCapacity: " + initialCapacity);
}
data = new double[initialCapacity];
manyItems = 0;
currentIndex = -1;
}
public void addAfter(double element) {
if(manyItems == data.length) {
ensureCapacity(manyItems * 2 + 1);
}
if(!isCurrent()) {
currentIndex = 0;
} else {
currentIndex++;
}
for(int i = currentIndex; i < manyItems; i++) {
data[i + 1] = data[i];
}
data[currentIndex] = element;
manyItems++;
}
public void addAll(DoubleArraySeq addend) {
if(addend == null) {
throw new NullPointerException("addend Array is Null Point.");
}
this.ensureCapacity(manyItems + addend.manyItems);
System.arraycopy(addend.data, 0, this.data, this.manyItems, addend.manyItems);
manyItems += addend.manyItems;
}
public void addBefore(double element) {
if(manyItems == data.length) {
ensureCapacity(manyItems * 2 + 1);
}
if(!isCurrent()) {
currentIndex = 0;
}
for(int i = manyItems; i > currentIndex; i--) {
data[i] = data[i - 1];
}
data[currentIndex] = element;
manyItems++;
}
public void addEnd(double element) {
if(manyItems == data.length) {
ensureCapacity(manyItems * 2 + 1);
}
currentIndex = manyItems;
data[currentIndex] = element;
manyItems++;
}
public void addFront(double element) {
if(manyItems == data.length) {
ensureCapacity(manyItems * 2 + 1);
}
currentIndex = 0;
for(int i = manyItems; i > currentIndex; i--) {
data[i] = data[i - 1];
}
data[currentIndex] = element;
manyItems++;
}
public void advance() {
if(!isCurrent()) {
throw new IllegalStateException("There is not current element, so it can't advance");
}
currentIndex++;
}
@Override
public DoubleArraySeq clone() {
// Clone a DoubleArraySeq object.
DoubleArraySeq answer;
try {
answer = (DoubleArraySeq) super.clone();
} catch(CloneNotSupportedException e) {
throw new RuntimeException("This class does not implement Cloneable");
}
answer.data = data.clone();
return answer;
}
public void ensureCapacity(int minimumCapacity) {
int ensuredCapacity;
if(data.length < minimumCapacity) {
ensuredCapacity = minimumCapacity;
} else {
ensuredCapacity = data.length;
}
double[] biggerArray = new double[ensuredCapacity];
System.arraycopy(data, 0, biggerArray, 0, manyItems);
data = biggerArray;
}
public int find(double element) {
for(int i = 0; i < manyItems; i++) {
if(element == data[i]) {
this.currentIndex = i;
return i;
}
}
return -1;
}
public int getCapacity() {
return data.length;
}
public double getCurrent() {
if(this.isCurrent()) {
return data[currentIndex];
} else {
throw new IllegalStateException("there is no current element");
}
}
public int getSize() {
return this.manyItems;
}
public void gotoEnd() {
if(manyItems <= 0) {
throw new IllegalStateException("The sequence is empty");
}
currentIndex = manyItems - 1;
}
public void gotoStart() {
if(data.length > 0) {
currentIndex = 0;
}
}
public boolean isCurrent() {
return currentIndex >= 0;
}
public void removeCurrent() {
if(manyItems - 1 < currentIndex) {
throw new IllegalStateException("There is no current element.");
}
for(int i = currentIndex; i < manyItems; i++) {
try {
data[i] = data[i + 1];
} catch(ArrayIndexOutOfBoundsException e) {
}
}
data[manyItems-- - 1] = 0;
}
public void removeEnd() {
this.gotoEnd();
this.removeCurrent();
}
public void removeFront() {
this.gotoStart();
this.removeCurrent();
}
public double retrieveElement(int i) {
if(i < 0 || i >= manyItems) {
throw new IllegalArgumentException("Given index of " + i + " is outside the bounds of the sequence");
}
return data[i];
}
public void setCurrent(int i) {
if(i < 0 || i >= manyItems) {
throw new IllegalArgumentException("Given index of " + i + " is outside the bounds of the sequence");
}
this.currentIndex = i;
}
@Override
public String toString() {
String ret = "";
ret += "The sequence: ";
for(int i = 0; i < manyItems; i++) {
ret += data[i] + " ";
}
ret += "nNumber of elements: " + manyItems + "n";
try {
ret += "Current element: " + getCurrent();
} catch(IllegalStateException e) {
ret += "Current element: N/A";
}
return ret;
}
public void trimToSize() {
double[] trimmedArray;
if(data.length != manyItems) {
trimmedArray = new double[manyItems];
System.arraycopy(data, 0, trimmedArray, 0, manyItems);
data = trimmedArray;
}
}
}
对于依赖于单链表或双链表的链表 首先你必须创建节点
Node<E> {
E data;
Node<E> next;
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
完整代码示例的单向链表的一些代码参考我的 github
public class SinglyLinkedList<E> {
private Node<E> head;
private int size = 0;
public int getSize() {
return size;
}
/**
* Inserts the specified element at the beginning of this list.
*
* @param e
* the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* @param e
* element to be appended to this list
* @return {@code true}
*/
public boolean add(E e) {
linkLast(e);
return true;
}
private void linkFirst(E e) {
final Node<E> f = head;
Node<E> newNode = new Node<E>(e, null);
head = newNode;
if (f != null) {
newNode.next = f;
}
size++;
}
private void linkLast(E e) {
Node<E> newNode = new Node<E>(e, null);
if (head == null) {
head = newNode;
} else {
Node<E> head = this.head;
while (head.next != null) {
head = head.next;
}
head.next = newNode;
}
size++;
}