implementation of basic data structures

fei9009 · fei9009 · commit c27c036fe16b · 2017-02-24T22:48:11.000-06:00
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/ArrayList.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/ArrayList.java
@@ -0,0 +1,71 @@
+package com.github.fei9009.coding2017.basic;
+
+public class ArrayList implements List {
+	
+	private int size = 0;
+	private int capacity;
+	
+	private Object[] elementData = new Object[100];
+	
+	public ArrayList() {
+		this.capacity = 20;
+	}
+	
+	private void extend() {
+		Object[] updatedElementData = new Object[this.elementData.length + this.capacity];
+		System.arraycopy(this.elementData, 0, updatedElementData, 0, this.elementData.length);
+		this.elementData = updatedElementData;
+	}
+	
+	public void add(Object o){
+		if (this.size == elementData.length) {
+			extend();
+		}
+		elementData[size] = o;
+		this.size++;
+	}
+	
+	public void add(int index, Object o){
+		if (this.size == elementData.length) {
+			extend();
+		}
+		int i;
+		for (i = this.size - 1; i >= index; i--) {
+			this.elementData[i + 1] = this.elementData[i];
+		}
+		this.elementData[i + 1] = o;
+		this.size++;
+	}
+	
+	public Object get(int index){
+		if (index >= 0 && index < this.size) {
+			return this.elementData[index];
+		}else {
+			return null;
+		}
+	}
+	
+	public Object remove(int index){
+		if (index >= 0 && index < this.size) {
+			int i = 0;
+			Object deletedElement = this.elementData[index];
+			for (i = index + 1; i < this.size; i++) {
+				this.elementData[i - 1] = this.elementData[i]; 
+			}
+			this.elementData[i] = null;
+			this.size--;
+			return deletedElement;
+		}else {
+			return null;
+		}
+	}
+	
+	public int size(){
+		return this.size;
+	}
+	
+	public Iterator iterator(){
+		return null;
+	}
+	
+}
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/BinaryTreeNode.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/BinaryTreeNode.java
@@ -0,0 +1,57 @@
+package com.github.fei9009.coding2017.basic;
+
+public class BinaryTreeNode <Object extends Comparable<Object>> {
+	
+	private Object data;
+	private BinaryTreeNode left;
+	private BinaryTreeNode right;
+	
+	public BinaryTreeNode(Object o) {
+		data = o;
+		left = null;
+		right = null;
+	}
+	
+	public Object getData() {
+		return data;
+	}
+	public void setData(Object data) {
+		this.data = data;
+	}
+	public BinaryTreeNode getLeft() {
+		return left;
+	}
+	public void setLeft(BinaryTreeNode left) {
+		this.left = left;
+	}
+	public BinaryTreeNode getRight() {
+		return right;
+	}
+	public void setRight(BinaryTreeNode right) {
+		this.right = right;
+	}
+	
+	public BinaryTreeNode insert(Object o){
+		BinaryTreeNode node = new BinaryTreeNode(o);
+		boolean left = true;
+		BinaryTreeNode cur = this;
+		BinaryTreeNode pre = null;
+		while (cur != null) {
+			pre = cur;
+			if (node.getData().compareTo(cur.getData()) <= 0) {
+				cur = cur.left;
+				left = true;
+			} else {
+				cur = cur.right;
+				left = false;
+			}
+		}
+		if(left) {
+			pre.left = node;
+		} else {
+			pre.right = node;
+		}
+		return node;
+	}
+	
+}
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/Iterator.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/Iterator.java
@@ -0,0 +1,7 @@
+package com.github.fei9009.coding2017.basic;
+
+public interface Iterator {
+	public boolean hasNext();
+	public Object next();
+
+}
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/LinkedList.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/LinkedList.java
@@ -0,0 +1,91 @@
+package com.github.fei9009.coding2017.basic;
+
+public class LinkedList implements List {
+	
+	private Node head;
+	private int size;
+	
+	public void add(Object o){
+		add(size, o);
+	}
+	
+	public void add(int index , Object o){
+		if (index > this.size || index < 0) {
+			throw new IndexOutOfBoundsException("index " + index + "beyond the size " + size );
+		}
+		Node dummy = node(index);
+		Node newNode = new Node(o);
+		newNode.next = dummy;
+		if (index == 0) {
+			head = newNode;
+		}
+		else {
+			Node before = node(index-1);
+			before.next = newNode;
+		}
+		this.size++;
+		
+	}
+	
+	public Object get(int index){
+		if (index >= this.size || index < 0) {
+			throw new IndexOutOfBoundsException("index " + index + "beyond the size " + size );
+		}
+		Node node = node(index);
+		return node.data;
+		
+	}
+	public Object remove(int index){
+		if (index >= this.size || index < 0) {
+			throw new IndexOutOfBoundsException("index " + index + "beyond the size " + size );
+		}
+		Node delNode = node(index);
+		if (index == 0)
+			head = delNode.next;
+		else {
+			Node before = node(index-1);
+			before.next = delNode.next;
+		}
+		size--;
+		return delNode.data;
+	}
+	
+	public int size(){
+		return this.size;
+	}
+	
+	public void addFirst(Object o){
+		add(0, o);
+	}
+	public void addLast(Object o){
+		add(o);
+	}
+	public Object removeFirst(){
+		return remove(0);
+	}
+	
+	public Object removeLast(){
+		return remove(this.size -1);
+	}
+	public Iterator iterator(){
+		return null;
+	}
+	
+	Node node(int index) {
+		Node x = head;
+		for (int i=0; i<index; i++) {
+			x = x.next;
+		}
+		return x;
+	}
+	
+	private static  class Node{
+		Object data;
+		Node next;
+		Node(Object o) {
+			this.data = o;
+			this.next = null;
+		}
+		
+	}
+}
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/List.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/List.java
@@ -0,0 +1,9 @@
+package com.github.fei9009.coding2017.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();
+}
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/Queue.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/Queue.java
@@ -0,0 +1,21 @@
+package com.github.fei9009.coding2017.basic;
+
+public class Queue {
+	private ArrayList elementData = new ArrayList();
+	
+	public void enQueue(Object o){		
+		elementData.add(o);
+	}
+	
+	public Object deQueue(){
+		return elementData.remove(0);
+	}
+	
+	public boolean isEmpty(){
+		return elementData.size() == 0 ? true : false;
+	}
+	
+	public int size(){
+		return elementData.size();
+	}
+}
diff --git a/group02/527705641/src/com/github/fei9009/coding2017/basic/Stack.java b/group02/527705641/src/com/github/fei9009/coding2017/basic/Stack.java
@@ -0,0 +1,26 @@
+package com.github.fei9009.coding2017.basic;
+
+
+public class Stack {
+	private ArrayList elementData = new ArrayList();
+	
+	public void push(Object o){		
+		elementData.add(o);
+	}
+	
+	public Object pop(){
+		Object o = elementData.remove(elementData.size() - 1);
+		return o;
+	}
+	
+	public Object peek(){
+		Object o = elementData.get(elementData.size() - 1);
+		return o;
+	}
+	public boolean isEmpty(){
+		return elementData.size() == 0 ? true : false;
+	}
+	public int size(){
+		return elementData.size();
+	}
+}
