ArrayList
就是数组实现的啦，没什么好说的，如果数组不够了就扩容到原来的1.5倍
实现了迭代器
package com.wenr.collection; import java.io.Serializable;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess; /**
* @author wenr
*
* 实现方法：
* - void add(E e)
* - void add(int index, E e)
* - E get(int index)
* - int indexOf(Object o)
* - boolean contains(Object o)
* - int size()
* - boolean isEmpty()
* - E remove(int index)
* - boolean remove(Object o)
* - Iterator<E> iterator()
*
*/
public class ArrayListDemo<E> implements RandomAccess, Cloneable, Serializable{ private static final int DEFAULT_SIZE = 10; private Object[] elementData;
private int size = 0; ArrayListDemo() {
this(DEFAULT_SIZE);
} ArrayListDemo(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("初始化参数错误：" + initialCapacity);
} else {
elementData = new Object[initialCapacity];
}
} public void add(E e) {
isCapacityEnough(size + 1);
elementData[size++] = e;
} public void add(int index, E e) {
rangeCheckForAdd(index);
isCapacityEnough(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = e;
size++;
} private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("下标越界：" + index);
} private void isCapacityEnough(int capacity) {
// 溢出
if (capacity < 0)
throw new OutOfMemoryError();
// 需要扩容
if (capacity - elementData.length > 0)
grow(capacity);
} private void grow(int capacity) {
int oldCapacity = elementData.length;
// 设置新容量是原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 可能会有一次加入多个数据的情况 那么久直接加到所需容量
if (capacity - newCapacity > 0)
newCapacity = capacity;
elementData = Arrays.copyOf(elementData, newCapacity);
} public E get(int index) {
rangeCheck(index);
return (E)elementData[index];
} private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("下标越界：" + index);
} public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; ++i) {
if (elementData[i] == null)
return i;
}
} else {
for (int i = 0; i < size; ++i) {
if (o.equals(elementData[i]))
return i;
}
}
return -1;
} public boolean contains(Object o) {
return indexOf(o) >= 0;
} public int size() {
return size;
} public boolean isEmpty() {
return size == 0;
} public E remove(int index) {
rangeCheck(index);
E value = (E)elementData[index];
int moveSize = size - index - 1;
if (moveSize > 0)
System.arraycopy(elementData, index + 1, elementData, index, moveSize);
elementData[--size] = null;
return value;
} public boolean remove(Object o) {
int index = indexOf(o);
if (index < 0) {
return false;
} else {
remove(index);
return true;
}
} public Iterator<E> iterator() {
return new Itr();
} private class Itr implements Iterator<E> { int cursor = 0; // 下一个将返回的元素 @Override
public boolean hasNext() {
return cursor != size;
} @Override
public E next() {
if (cursor < 0 || cursor >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayListDemo.this.elementData;
return (E)elementData[cursor++];
} } public static void main(String[] args) {
ArrayListDemo<String> list = new ArrayListDemo<String>();
list.add("1");
list.add("2");
list.add("3");
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.indexOf("3"));
System.out.println(list.remove("3"));
System.out.println(list.contains("3"));
// System.out.println(list.get(3));
Iterator<String> itr = list.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
} }
LinkedList
嗯，就是一个双向链表~
package com.wenr.collection; import java.util.Iterator;
import java.util.NoSuchElementException; /**
* @author wenr
*
* 实现方法:
* - void add(E e)
* - void add(int index, E e)
* - E get(int index)
* - int indexOf(Object o)
* - boolean contains(Object o)
* - E remove(int index)
* - boolean remove(Object o)
* - boolean isEmpty()
* - int size()
* - Iterator<E> iterator()
*
*/
public class LinkedListDemo<E> { private int size;
Node<E> first;
Node<E> last; public LinkedListDemo() {
} // 添加一个节点在结尾处
public void add(E e) {
Node<E> l = last;
Node<E> node = new Node(e, last, null);
last = node;
if (l == null) {
first = node;
} else {
l.next = node;
}
size++;
} public void add(int index, E e) {
rangeCheckForAdd(index);
if (index == size) {
add(e);
} else {
Node<E> x = node(index);
addBeforeNode(e, x);
}
} private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("下标越界：" + index);
} private void addBeforeNode(E e, Node<E> beforeNode) {
Node<E> preNode = beforeNode.prev;
Node<E> newNode = new Node(e, preNode, beforeNode);
if (preNode == null) {
first = newNode;
} else {
preNode.next = newNode;
}
beforeNode.prev = newNode;
size++;
} private Node<E> node(int index) {
// 如果node在前一半就正向查找 否则逆向查找
if (index < (size >> 1)) {
Node<E> cursor = first;
for (int i = 0; i < index; ++i) {
cursor = cursor.next;
}
return cursor;
} else {
Node<E> cursor = last;
for (int i = size-1; i > index; --i) {
cursor = cursor.prev;
}
return cursor;
}
} public E get(int index) {
rangeCheck(index);
Node<E> x = node(index);
return x.item;
} private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界：" + index);
} public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
} public E remove(int index) {
rangeCheck(index); Node<E> x = node(index);
final E element = x.item;
final Node<E> prev = x.prev;
final Node<E> next = x.next; if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
} if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
} x.item = null;
size--;
return element;
} public boolean remove(Object o) {
int index = indexOf(o);
if (index < 0)
return false;
remove(index);
return true;
} public int size() {
return size;
} public boolean isEmpty() {
return size == 0;
} public boolean contains(Object o) {
return indexOf(o) >= 0;
} public Iterator<E> iterator() {
return new Itr();
} private static class Node<E> {
E item;
Node<E> prev;
Node<E> next;
public Node(E item, Node<E> prev, Node<E> next) {
this.item = item;
this.prev = prev;
this.next = next;
}
} private class Itr implements Iterator<E> { private Node<E> cursor;
private int nextIndex; public Itr() {
cursor = first;
nextIndex = 0;
} @Override
public boolean hasNext() {
return nextIndex < size;
} @Override
public E next() {
if (!hasNext())
throw new NoSuchElementException();
E element = cursor.item;
cursor = cursor.next;
nextIndex++;
return element;
} } public static void main(String[] args) {
LinkedListDemo<String> list = new LinkedListDemo<>();
list.add("aaaa");
list.add("bbbb");
list.add("cccc");
list.add("dddd");
System.out.println(list.size());
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(0));
System.out.println(list.remove(2));
list.add(3, "eeee");
System.out.println(list.get(1));
System.out.println(list.get(2));
System.out.println(list.get(3));
System.out.println("_____");
Iterator<String> itr = list.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
} }
Queue
瞎写的啦哈哈哈
队列先进先出 用循环队列实现 节省空间
当front==tail就是队列为空
因为如果队列全部装满的时候front==tail，和空一样，所以循环队列不能全部装满，至少空出一位
当(tail+1)%capacity==front的时候就是队列满（capacity是队列容量大小
package com.wenr.collection; import java.util.Arrays;
import java.util.NoSuchElementException; /**
*
* @author wenr
*
* 通过数组实现的循环队列
*
* 实现方法：
* - boolean offer(E)
* - boolean isEmpty()
* - E peek()
* - E poll()
* - int size()
*
*/ public class QueueDemo<E> { private static final int DEFAULT_SIZE = 0; private Object[] elementData;
private int front;
private int tail; public QueueDemo() {
this(DEFAULT_SIZE);
} public QueueDemo(int capacity) {
elementData = new Object[capacity];
front = tail = 0;
} // 向队列中加入一个元素
public boolean offer(E element) {
int capacity = elementData.length;
// 注意这里是capacity-1哦 因为要区别empty 所以循环队列不能装满的
if (size() == capacity - 1) {
grow(++capacity);
}
elementData[tail] = element;
tail = (tail + 1) % capacity;
return true;
} // 获取并移除此队列的头
public E poll() {
if (isEmpty())
throw new NoSuchElementException();
E element = (E)elementData[front];
front = (front + 1) % elementData.length;
return element;
} private void grow(int capacity) {
if (capacity == -1)
throw new OutOfMemoryError(); int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < capacity)
newCapacity = capacity;
if (front < tail) {
// [front...tail]
elementData = Arrays.copyOf(elementData, newCapacity);
} else {
// [...tail front...]
Object[] tempData = new Object[newCapacity];
int moveSize = oldCapacity - front;
System.arraycopy(elementData, front, tempData, 0, moveSize);
System.arraycopy(elementData, 0, tempData, moveSize, tail);
elementData = tempData;
tempData = null;
front = 0;
tail = oldCapacity - 1;
} } // 获取但不移除此队列的头
public E peek() {
if (isEmpty())
throw new NoSuchElementException();
else
return (E)elementData[front];
} public boolean isEmpty() {
return front == tail;
} public int size() {
int capacity = elementData.length;
return (tail - front + capacity) % capacity;
} public static void main(String[] args) {
QueueDemo<Integer> q = new QueueDemo<>(5);
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
System.out.println(q.poll());
System.out.println(q.poll());
q.offer(5);
q.offer(6);
q.offer(7);
q.offer(8);
while (!q.isEmpty()) {
System.out.print(q.peek() + " ");
q.poll();
}
//q.poll();
}
}
Stack
哦 还是瞎写的
栈 先进后出 没什么好说的 都比较简单
package com.wenr.collection; import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Stack; /**
* @author wenr
*
* 实现函数：
* - E peek()
* - E pop()
* - void push(E)
* - isEmpty()
* - size()
*
*/
public class StackDemo<E> {
private static final int DEFAULT_SIZE = 10;
private int top;
private Object[] data; public StackDemo() {
this(DEFAULT_SIZE);
} public StackDemo(int capacity) {
data = new Object[capacity];
} public E peek() {
if (isEmpty())
throw new NoSuchElementException();
return (E)data[top - 1];
} public E pop() {
if (isEmpty())
throw new NoSuchElementException();
return (E)data[--top];
} public void push(E e) {
int capacity = data.length;
if (top == capacity) {
grow(capacity + 1);
}
data[top++] = e;
} private void grow(int capacity) {
if (capacity <= 0)
throw new OutOfMemoryError();
int oldCapacity = data.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < capacity) {
newCapacity = capacity;
}
data = Arrays.copyOf(data, newCapacity);
} public boolean isEmpty() {
return top == 0;
} public int size() {
return top;
} public static void main(String[] args) {
StackDemo<Integer> stack = new StackDemo<>(3);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.pop();
stack.push(7);
while (!stack.isEmpty()) {
System.out.println(stack.peek());
stack.pop();
}
} }