java语言实现简单的ArrayList，LinkedList，Heap，Stack，没有考虑线程安全
List接口
package com.coding.basic; public interface List { public void add(Object o); public void add(int index, Object o); public Object get(int index); public Object remove(int index); public int size(); }ArrayList.java
package com.coding.basic; import java.util.Arrays; /** * @autor zhougd 20170306 * 数组实现ArrayList */ public class ArrayList implements List { private int size = 0; private Object[] elementData; //扩容默认值 private static final int INCREAMENT_CAP = 10; //含参数的构造函数 public ArrayList(int size, Object[] elementData) { this.size = size; this.elementData = elementData; } //默认100容量的构造函数 public ArrayList() { this.size = 0; this.elementData = new Object[100]; } @Override public void add(Object o) { //判断超过容量自动扩容 if (this.size + 1 > this.elementData.length) { increase(); } this.elementData[size++] = o; } @Override public void add(int index, Object o) { if (index < 0 || index > this.size) { throw new IndexOutOfBoundsException("Index out of bound!"); } //判断超过容量自动扩容 if (this.size + 1 > this.elementData.length) { increase(); } this.size++; //index后面数组后移一位 for (int cur = this.size; cur > index; cur--) { this.elementData[cur] = this.elementData[cur - 1]; } this.elementData[index] = o; } public Object get(int index) { if (index < 0 || index > this.size) { throw new IndexOutOfBoundsException("Index out of bound!"); } return this.elementData[index]; } public Object remove(int index) { Object o = this.get(index); this.size--; //index后面的数向前移动一位 for (int cur = index + 1; cur < this.size; cur++) { this.elementData[cur] = this.elementData[cur + 1]; } return o; } public int size() { return this.size; } public Iterator iterator() { return new ArrayListIterator(); } @Override public String toString() { String arrayStr = "ArrayList{ size = " + this.size() + " , "; arrayStr += "elementData=["; for(int i = 0 ;i<this.size();i++){ arrayStr += i == this.size()-1 ? elementData[i]+"]":elementData[i]+"," ; } arrayStr+= " }"; return arrayStr; } private void increase() { this.elementData = Arrays.copyOf(this.elementData, this.elementData.length + INCREAMENT_CAP); } private class ArrayListIterator implements Iterator { private int currentIndex = 0; private int count = size(); @Override public boolean hasNext() { return currentIndex < count-1; } @Override public Object next() { currentIndex++; return get(currentIndex); } } } LinkedList.java
package com.coding.basic; import java.util.NoSuchElementException; /** * @author zhougd 20170306 * 单向链表实现LinkedList */ public class LinkedList implements List { java.util.LinkedList a; /** * 第一个元素 */ private Node head; /** * 最后一个元素 */ private Node tail; /** * 元素容量 */ private int size = 0; public void add(Object o){ Node node = new Node(o); //判断是否链表为空 if(this.size() == 0){ this.addFirst(node); }else{ this.addLast(node); } } public void add(int index , Object o){ checkIndex(index); Node oldNode= this.getNode(index); Object oldObject = oldNode.getData(); Node next = oldNode.getNext(); //将原位置修改为新元素 oldNode.setData(o); //设置下一个元素 oldNode.setNext(new Node(oldObject)); //设置下一个元素的下一个元素 oldNode.getNext().setNext(next); size ++; } public Object get(int index){ checkIndex(index); return this.getNode(index).getData(); } public Object remove(int index){ checkIndex(index); //获取到当前元素和下一个元素 //把当前元素的值设置成下一个元素的值，删除掉下一个元素，这样的话，不必管上一个元素是什么，是不是第一个元素 Node node = this.getNode(index); Object data = node.getData(); Node nextNode = this.getNode(index + 1); node.setData(nextNode.getData()); node.setNext(nextNode.getNext()); return data; } public int size(){ return this.size(); } public void addFirst(Object o){ Node node = new Node(o); //原头变为第二 Node temp = this.head; this.head = node; node.next = temp; size++; } public void addLast(Object o){ Node node = new Node(o); Node t = this.tail; if(t == null){ this.head = node; }else{ this.tail.next = node; this.tail = node; } size++; } public Object removeFirst(){ Node head = this.head; if(head == null){ throw new NoSuchElementException("No such element !"); } this.head = this.head.getNext(); size--; return head ; } public Object removeLast(){ Node node ; if(this.tail == null){ throw new NoSuchElementException("No such element !"); } node = this.tail; if(this.head ==this.tail){ node = this.head; this.head = null; this.size = 0; }else{ //获取尾元素的上一个元素 this.tail = this.getNode(this.size-2); this.tail.setNext(null); this.size--; } return node; } public Iterator iterator(){ return new LinkedListIterator(); } private void checkIndex(int index){ if(index < 0 || index >size()){ throw new IndexOutOfBoundsException("Index out of bound !"); } } private Node getNode(int index ){ Node node = this.head; for(int i = 0 ;i<size();i++){ node = node.next; } return node; } private class LinkedListIterator implements Iterator{ private int currentIndex = 0; private int count = size(); @Override public boolean hasNext() { return currentIndex < count-1; } @Override public Object next() { currentIndex++; return get(currentIndex); } } private static class Node{ Object data; Node next; public Node(Object data) { this.data = data; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } }
Queue.java
package com.coding.basic; /** * author by zhougd 20170306 * 链表实现队列 */ public class Queue { private java.util.Queue a;; /** * 队列体，初始100个元素 */ private List queue = new LinkedList(); public Queue(){} /** * 入队 * @param o */ public void enQueue(Object o){ queue.add(o); } /** * 出队 * @return */ public Object deQueue(){ return queue.remove(0); } /** * 队列是否为空 * @return */ public boolean isEmpty(){ return queue == null || queue.size() <= 0; } /** * 获取队列大小 * @return */ public int size(){ return queue.size(); } }
Stack.java
package com.coding.basic; /** * author zhougd 20170306 * */ public class Stack { private List elementData = new ArrayList(); public Stack() { } /** * 入栈 * @param o */ public void push(Object o){ elementData.add(o); } /** * 出栈 * @return */ public Object pop(){ if(this.isEmpty()){ throw new IndexOutOfBoundsException("stack is empty!"); } Object element = elementData.get(size()-1); elementData.remove(size()-1); return element; } /** * 查看栈顶元素 * @return Object */ public Object peek(){ if(this.isEmpty()){ throw new IndexOutOfBoundsException("stack is empty!"); } Object element = elementData.get(size()-1); return element; } /** * 查看栈是否为空 * @return boolean */ public boolean isEmpty(){ return elementData == null || elementData.size()<=0; } /** * 获取栈大小 * @return */ public int size(){ return elementData.size(); } }
