基于 Java 8 实现的代码片段集合,可以在较短的时间内理解这些数据结构代码片段。提供了各种数据结构的实现方法,并对实现进行分析说明。该项目的 Github 地址:暂无。

列表 - List

基于数组实现的列表

public class ArrayList<T> implements IList<T>, Iterable<T> {
private static final int DEFAULT_CAPACITY = 10;
private int size;
private T[] items;

public ArrayList(){
this(DEFAULT_CAPACITY);
}

public ArrayList(int capacity){
this.items = (T[]) new Object[capacity];
this.size = 0;
}

public void clear(){ this.size = 0; }

public int size(){ return this.size; }

public boolean isEmpty(){ return this.size == 0; }

public boolean contains(T item){
for (int i = 0; i < this.size; i++){
if (this.items[i] == item) return true;
}
return false;
}

public T get(int index) {
if (index >= this.size || index < 0) throw new IndexOutOfBoundsException();
return this.items[index];
}

public void set(int index, T item) {
if (index >= this.size || index < 0) throw new IndexOutOfBoundsException();
this.items[index] = item;
}

public boolean add(T item){
add(this.size, item);
return true;
}

public void add(int index, T item) {
if (index > this.size || index < 0) throw new IndexOutOfBoundsException();
if (this.size == this.items.length) ensureCapacity(this.size * 2);
System.arraycopy(this.items, index, this.items, index + 1, this.size - index);
this.items[index] = item;
}

public boolean remove(T item){
int index = -1;
for (int i = 0; i < this.size; i++)
if (item.equals(this.items[i])) index = i;

if (index != -1){
remove(index);
return true;
}
return false;
}

public void remove(int index) {
if (index >= size() || index < 0) throw new IndexOutOfBoundsException();
System.arraycopy(this.items, index + 1, this.items, index, this.size - index);
--this.size;
}

private void ensureCapacity(int capacity){
if (capacity < this.size) return;
T[] old = this.items;
this.items = (T[]) new Object[capacity];
System.arraycopy(old, 0, this.items, 0, old.length);
}

public Iterator<T> iterator() {
return new ArrayListIterator();
}

private class ArrayListIterator implements Iterator<T>{
private int current = 0;

public boolean hasNext() { return this.current < size(); }

public T next() {
if (! hasNext()) throw new NoSuchElementException();
return items[current++];
}

public void remove() {
ArrayList.this.remove(--current);
}
}
}

基于单链表实现的列表

public class LinkedList<T> implements Iterable<T> {
private int size;
private int modCount;
private final Node<T> startNode;
private final Node<T> endNode;

public MyLinkedList(){
this.startNode = new Node<T>(null, null, null);
this.endNode = new Node<T>(null, this.startNode, null);
this.startNode.next = this.endNode;

this.size = 0;
modCount++;
}

public int size(){ return size; }

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

public boolean contains(T item){
Node<T> curr = startNode;
while (curr.next != null) {
curr = curr.next;
if (curr.data == item) return true;
}
return false;
}

public boolean add(T item) {
add(size(), item);
return true;
}

public void add(int index, T item){
addBefore(getNode(index, 0, size()), item);
}

private void addBefore(Node<T> node, T item){
Node<T> newNode = new Node<T>(item, node.prev, node);
newNode.prev.next = newNode;
node.prev = newNode;
size++;
modCount++;
}

public boolean remove(T item){
Node<T> curr = startNode;
while (curr.next != endNode){
curr = curr.next;
if (curr.data == item){
remove(curr);
return true;
}
}
return false;
}

public void remove(int index){
remove(getNode(index));
}

private void remove(Node<T> node){
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
modCount++;
}

public Node<T> getNode(int index){
return getNode(index, 0, size() - 1);
}

public Node<T> getNode(int index, int lower, int upper){
Node<T> node;
if (index < lower || index > upper)
throw new IndexOutOfBoundsException();
if (index < size() / 2){
node = startNode.next;
for (int i = 0; i < index; i++)
node = node.next;
}else {
node = endNode;
for (int i = size(); i > index; i--)
node = node.prev;
}
return node;
}

public T get(int index){
return getNode(index).data;
}

public T set(int index, T item){
Node<T> node = getNode(index);
T oldValue = node.data;
node.data = item;
return oldValue;
}

public Iterator<T> iterator() {
return new LinkedListIterator();
}

public static class Node<T>{
public T data;
public Node<T> prev;
public Node<T> next;

public Node(T data, Node<T> prev, Node<T> next){
this.data = data;
this.prev = prev;
this.next = next;
}
}

public class LinkedListIterator implements Iterator<T>{
private Node<T> curr = startNode.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;

public boolean hasNext() {
return curr != endNode;
}

public T next() {
if (modCount != expectedModCount) throw new ConcurrentModificationException();
if (!hasNext()) throw new NoSuchElementException();

T nextItem = curr.data;;
curr = curr.next;
okToRemove = true;
return nextItem;
}

public void remove() {
if (modCount != expectedModCount) throw new ConcurrentModificationException();
if (!okToRemove) throw new IllegalStateException();

MyLinkedList.this.remove(curr.prev);
expectedModCount++;
okToRemove = false;
}
}
}

评论