接口定义
public interface MyList<T> extends Iterable<T>{
void add(T element);
void add(int index, T element);
void remove(Object element);
T remove(int index);
T get(int index);
int indexOf(T element);
int size();
}
基于数组实现ArrayList
public class MyArrayList<T> implements MyList<T> {
private static final int DEFAULT_SIZE = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private transient Object[] elementData;
private int size;
public MyArrayList() {
elementData = new Object[DEFAULT_SIZE];
}
public MyArrayList(int capacity) {
if (capacity > 0) {
elementData = new Object[capacity];
} else if (capacity == 0) {
elementData = new Object[0];
} else {
throw new IllegalArgumentException("illegal capacity " + capacity);
}
elementData = new Object[capacity];
}
@Override
public void add(T element) {
ensureCapacity(size + 1);
elementData[size++] = element;
}
private void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length) {
if (minCapacity < DEFAULT_SIZE) {
minCapacity = DEFAULT_SIZE;
}
grow(minCapacity);
}
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < 0) {
throw new OutOfMemoryError();
}
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
@Override
public void add(int index, T element) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
ensureCapacity(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
@Override
public void remove(Object element) {
for (int i = 0; i < size; i++) {
if (Objects.equals(element, elementData[i])) {
remove(i);
return;
}
}
}
@Override
public T remove(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException();
}
T oldElement = (T) elementData[index];
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
elementData[--size] = null; //for gc
return oldElement;
}
@Override
public T get(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException();
}
return (T) elementData[index];
}
@Override
public int indexOf(T element) {
for (int i = 0; i < size; i++) {
if (Objects.equals(element, elementData[i])) {
return i;
}
}
return 0;
}
@Override
public int size() {
return size;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private int cursor;
@Override
public boolean hasNext() {
return cursor != size;
}
@Override
public T next() {
return (T) elementData[cursor++];
}
};
}
}
基于链表实现LinkedList
public class MyLinkedList<T> implements MyList<T> {
private int size;
private Node<T> first;
private Node<T> last;
@Override
public void add(T element) {
Node<T> l = last;
Node<T> newNode = new Node<>(l, element, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
@Override
public void add(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(String.valueOf(index));
}
if (index == size) {
add(element);
} else {
Node<T> node = getNode(index);
Node<T> prev = node.prev;
Node<T> newNode = new Node<>(prev, element, node);
prev.next = newNode;
node.prev = newNode;
size++;
}
}
@Override
public void remove(Object element) {
int nodeIndex = findNodeIndex(element);
if (nodeIndex > 0) {
remove(nodeIndex);
}
}
private int findNodeIndex(Object element) {
Node node = first;
int index = 0;
while (node != null) {
Node next = node.next;
if (Objects.equals(element, node.item)) {
return index;
}
node = next;
index++;
}
return -1;
}
private void removeNode(Node node) {
Node prev = node.prev;
Node next = node.next;
if (prev != null) {
prev.next = next;
}
if (next != null) {
next.prev = prev;
}
node = null;//For gc
size--;
}
@Override
public T remove(int index) {
Node<T> node = getNode(index);
removeNode(node);
return node.item;
}
@Override
public T get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(String.valueOf(index));
}
return getNode(index).item;
}
private Node<T> getNode(int index) {
if (index < (size >> 1)) {
Node<T> node = first;
for (int i = 1; i <= index; i++) {
node = node.next;
}
return node;
} else {
Node<T> node = last;
for (int i = 1; i <= size - index - 1; i++) {
node = node.prev;
}
return node;
}
}
@Override
public int indexOf(T element) {
int nodeIndex = findNodeIndex(element);
return nodeIndex;
}
@Override
public int size() {
return size;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private Node cur = first;
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public T next() {
Object item = cur.item;
cur = cur.next;
return (T) item;
}
};
}
private static class Node<T> {
private T item;
private Node<T> next;
private Node<T> prev;
public Node(Node<T> prev, T item, Node<T> next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
}
网友评论