基本数据结构Java实现(List, Stack and Queue)
– 封面摄于 25th DEC 2017，Edinburgh
假期闲的无聊，于是想把数据结构和基本的算法分析复习和实现一遍，以便于日后工作及学习之需，所以有了这篇博客。之前并没有很深入的研究基本数据结构的实现，Java.util包用了无数次，但是对于其内部实现却一知半解。正好今天翻书柜找到了“Data Structures and Algorithm Analysis In Java”这本书，那么就从这开始吧。
List两种基本实现及特性
List ADT有两种常见的实现方法，即用”Array”或者”Linked method”来实现。 “ArrayList”对于查找操作十分友好，因为其内部实现对于每一个object都有一个index， 所以查找操作在”ArrayList”中的时间复杂度为 O(1), 即”Constant time”. 但是对于增加与删除操作，时间复杂度则高很多。 由于”ArrayList”内部由一个array来存储数据，所以当增加或删除数据时，其他数据的位置也需要被移动，所以最坏情况，当第0位的数据被删除或添加时，其余n个数据都需要被移动，所以时间复杂度为 O(N)。相对的，最好情况， 当最后一位的数据被增加或删除时，剩余的数据都不需要被移动，所以时间复杂度为 O(1). 平均来说，对于增加与删除操作，array中一半的数据会被移动， 所以它们还是会花费linear time即 O(N). 和”ArrayList”相反，当用”Linked method”来实现List ADT时，其增加及删除操作不需要花费太多时间，因为对于LinkedList来说，这两种操作仅仅只是在原本的链式结构中增加或者删除节点而已，所以这两种操作的时间复杂度为 O(1). 但是查找操作对于”LinkedList”来说却相对昂贵，如果需要访问第 i 个数据，那么程序需要从链式结构的第一个节点或最后一个节点开始遍历直到第 i 个，所以查找操作的时间复杂度为O(N).
List的具体实现
ArrayList
“Data Structures and Algorithm Analysis In Java” 书中对于”ArrayList”的实现提出了如下要求：- The ArrayList will maintain the underlying array, the array capacity, and the current number of items stored in the ArrayList.
- The ArrayList will provide a mechanism to change the capacity of the underlying
array. The capacity is changed by obtaining a new array, copying the old array into the
new array, and allowing the Virtual Machine to reclaim the old array. - The ArrayList will provide an implementation of get and set.
- The ArrayList will provide basic routines, such as size, isEmpty, and clear, which are
typically one-liners; a version of remove; and also two versions of add. The add routines
will increase capacity if the size and capacity are the same. The ArrayList will provide a class that implements the Iterator interface. This class
will store the index of the next item in the iteration sequence and provide implementations
of next, hasNext, and remove. The ArrayList’s iterator method simply returns
a newly constructed instance of the class that implements the Iterator interface.根据书中所提要求，代码可以为：
public class MyArrayList<T>{
private int default_capacity = 1;
private int Size;
private Object[] Items;
// initialize arrayList
public MyArrayList() {
Size = 0;
Items = new Object[default_capacity];
}
public void Clear() {
Size = 0;
Items = new Object[default_capacity];
}
public int size() {
return Size;
}
public boolean isEmpty() {
return Size == 0;
}
public T get(int index) {
if (index < 0 || index >= Size) {
throw new ArrayIndexOutOfBoundsException();
}
return (T) Items[index];
}
public void Set(int index, T newVal) {
if (index < 0 || index >= Size) {
throw new ArrayIndexOutOfBoundsException();
}
Items[index] = newVal;
}
public void extandArray(int newCapacity) {
if (newCapacity <= default_capacity) {
return;
} else {
Object[] newItems = new Object[newCapacity];
for (int index = 0; index < Items.length; index++) {
newItems[index] = Items[index];
}
Items = newItems;
}
}
public void add(int index, T val) {
if (Size == Items.length) {
extandArray(Items.length * 2);
}
for (int arrayIndex = index; arrayIndex < Size; arrayIndex++) {
Items[arrayIndex+1] = Items[arrayIndex];
}
Items[index] = val;
Size++;
}
public T remove(int index) {
T removed = (T) Items[index];
for(int arrayIndex = Size-1; arrayIndex>index; arrayIndex--) {
Items[arrayIndex-1] = Items[arrayIndex];
}
Size--;
return removed;
}
public boolean addToTail(T val) {
add(Size, val);
return true;
}
private class ArrayListIterator implements java.util.Iterator<T>{
private int Current = 0;
@Override
public boolean hasNext() {
return Current != Size;
}
@Override
public T next() {
if(!hasNext()) {
throw new java.util.NoSuchElementException();
}
T val = (T) Items[Current+1];
return val;
}
}
}
LinkedList
对于 “LinkedList”，书中给予了以下要求：- The LinkedList class itself, which contains links to both ends, the size of the list, and
a host of methods. - The Node class, which is likely to be a private nested class. A node contains the data
and links to the previous and next nodes, along with appropriate constructors. The LinkedListIterator class, which abstracts the notion of a position and is a private
inner class, implementing the Iterator interface. It provides implementations of next,
hasNext, and remove.根据要求，代码可以是:
- The LinkedList class itself, which contains links to both ends, the size of the list, and
public class MyLinkedList<T> {
private int Size;
Node beginNode;
Node endNode;
private int modCount = 0;
static class Node<T> {
public T data;
public Node<T> prev;
public Node<T> next;
public Node(T d, Node p, Node n) {
data = d;
prev = p;
next = n;
}
public T getData() {
return data;
}
public void setData(T d) {
data = d;
}
}
public MyLinkedList() {
beginNode = new Node<T>(null, null, endNode);
endNode = new Node<T>(null, beginNode, null);
Size = 0;
}
public int size() {
return Size;
}
public boolean isEmpty() {
return Size == 0;
}
public Node getNode(int index) {
Node n;
if (index < 0 || index > Size) {
throw new IndexOutOfBoundsException();
}
if (index < (Size / 2)) {
n = beginNode.next;
for (int Nodeindex = 0; Nodeindex < index; Nodeindex++) {
n = n.next;
}
} else {
n = endNode;
for (int Nodeindex = Size; Nodeindex > index; Nodeindex--) {
n = n.prev;
}
}
return n;
}
public void add(int index, T val) {
Node<T> newNode = new Node<T>(val, getNode(index).prev, getNode(index));
getNode(index).prev.next = newNode;
newNode.next.prev = newNode;
Size++;
modCount++;
}
public void addToTail(T val) {
Node<T> newNode = new Node<T>(val, endNode.prev, endNode);
endNode.prev.next = newNode;
endNode.prev = newNode;
Size++;
modCount++;
}
public void remove(int index) {
Node<T> removed = getNode(index);
// System.out.println(removed.prev.next.getData());
removed.prev.next = removed.next;
removed.next.prev = removed.prev;
Size--;
modCount++;
}
public void set(int index, T val) {
getNode(index).setData(val);
}
private class ArrayListIterator implements java.util.Iterator<T> {
private int acceptModCount = modCount;
private Node currentPos = beginNode;
@Override
public boolean hasNext() {
return currentPos != endNode;
}
@Override
public T next() {
if (acceptModCount != modCount) {
throw new java.util.ConcurrentModificationException();
}
Node next = currentPos.next;
return (T) next;
}
}
}
Stack及Queue的介绍及实现
- Stack适用于FILO原则，即先进后出，越是率先被压入stack中的数据越是后来被push出stack。pop() 和 push() 是Stack 的两个基本操作，push() 的作用是把数据压入Stack中而 pop() 的作用是把数据从Stack中取出。Stack也有两种基本的实现方式，一种是基于 array 的实现，在这篇post中，我们叫它 ArrayStack，另一种是基于 LinkedList的实现，我们叫它 LinkedStack.
LinkedStack的实现可以是：
import java.util.LinkedList;
public class LinkedStack<E> {
LinkedList<E> list = new LinkedList<>();
public E pop() {
return list.removeFirst();
}
public void push(E val) {
list.addFirst(val);
}
public Integer size() {
return list.size();
}
}
而 ArrayStack 的实现则可以为：
public class ArrayStack<E> {
Object[] arr = new Object[10];
int topOfStack = 0;
int size = 0;
public void ensureCapacity(int capacity) {
Object[] newArr = new Object[capacity];
for(int index = 0;index<arr.length;index++) {
newArr[index] = arr[index];
}
arr = newArr;
}
public void push(E val) {
if(size == arr.length ) {
ensureCapacity(arr.length*2);
}
arr[topOfStack] = val;
topOfStack++;
size++;
}
public E pop() {
E val = (E) arr[size-1];
arr[size] = null;
size--;
topOfStack--;
return val;
}
public int size() {
return size;
}
}
再来说说 Queue. Queue遵循FIFO原则，即先进先出，越是先进入Queue的数据越是率先被取出。Queue的两个基本操作为 enqueue() 和 dequeue(). 和 Stack 类似，Queue也有两种实现方式，ArrayQueue 和 LinkedQueue.
LinkedQueue的实现可以是：
import java.util.LinkedList;
public class LinkedQueue<E> {
LinkedList<E> list = new LinkedList<>();
public void enqueue(E val) {
list.add(val);
}
public E dequeue() {
return list.removeLast();
}
public Integer size() {
return list.size();
}
}
而 ArrayQueue 的实现可以是：
public class ArrayQueue<E> {
Object[] arr = new Object[10];
int endOfQueue = 0;
int headOfQueue = 0;
int size = 0;
public void ensureCapacity(int capacity) {
Object[] newArr = new Object[capacity];
for (int index = 0; index < arr.length; index++) {
newArr[index] = arr[index];
}
arr = newArr;
}
public void enqueue(E val) {
if (size == arr.length) {
ensureCapacity(arr.length * 2);
}
arr[endOfQueue] = val;
endOfQueue++;
size++;
}
public E dequeue() {
E val = (E) arr[headOfQueue];
arr[0] = null;
headOfQueue++;
size--;
endOfQueue--;
return val;
}
public int size() {
return size;
}
}
以上是四个简单的数据结构的分析与实现。代码方面可能会有问题，欢迎修正。
Reference:
@book{Weiss:2012:DSA:2331470,
author = {Weiss, Mark Allen},
title = {Data Structures and Algorithm Analysis in Java. Mark Allen Weiss},
year = {2012},
isbn = {0273752111, 9780273752110},
publisher = {Pearson Education},
}