一 前言
由于做的是应用层开发，因此对数据结构理解不够透彻，有时候优化代码，或者定位问题时，往往陷入挣扎。最近在看数据结构方面的内容。现在重新过一下常用的数据结构和算法。Java集合类基本实现了所有的数据结构和算法，我这边会简单实现一些数据结构。
二 算法
2.1 算法的特性
算法和数据结构是互为一体的，互利共生的。一个算法要具备以下特性：
- 输入，输出；
- 有穷性（如果一个算法陷入死循环，或者要计算几年时间，那就没什么意义了）；
- 确定性（在计算机世界，是要解决确定问题，不能出现人类社会模棱两可的情况）；
- 可行性（执行有限的次数后，要有结果）。
2.2 衡量算法效率的两个标准
一个算法要考虑时间成本（时间复杂度）和空间存储成本（空间复杂度）。这两个概念我相信很多软件行业的从业者不是很清楚。
2.2.1 时间复杂度
先看这个时间成本如何估算，用一个时间复杂度的概念计算,数学上记为T(n)。
举个例子1-100之间求和，来理解一下事件复杂度这个概念。
- 实现一（一般大家都是这样实现的）
public int sumTotal1(int total){
int sum=0; //执行1次
int n=total; //执行1次
for (int i=1;i<=n;i++){ //执行n+1次
sum=sum+i; //执行n次
}
return sum; //执行1次
}
- 实现二（二百年前的高斯小朋友实现方法，不愧是神童）
public int sumTotal2(int total){
int sum=0; //执行1次
int n=total; //执行1次
sum=(1+n)*n/2; //执行1次
return sum; //执行1次
}
实现一的算法执行次数是2n+4次，实现二的算法执行次数是4次。
前面提到的算法时间复杂度与两个因素有关，一是问题输入规模（也就是n），二是执行次数。
这里可以看出实现一的是随着n的变化，线性增加的。
实现二，n无论如何变化，都是常数。
现在简化一下实现一的表达式，去掉常数项，只保留最高阶，并去掉最高阶的系数。
实现一的算法时间复杂度可记为O(n);
实现二的算法时间复杂度可记为O(1);
常用时间复杂度耗费时间从小到大排序依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n的二次幂)<O(2的n次幂)<O(n!)<O(n的n次幂)
想想如果n取比较小的值20，0(n的n次幂)是20的20次幂，这个执行次数需要耗费多长时间，想想都是噩梦。
2.2.2 空间复杂度
如果一个算法执行所需的空间不算输入数据规模的变化而变化，就记为O(1)。
2.2.3 小结
一个算法效率取决于时间复杂度和空间复杂度，我们要根据实际情况抉择，平衡两者之间的度。
三 数据结构
常见的数据结构有线性顺序表、链表、栈（注意和内存中的栈不是一个意思）、队列、树、图。
下面会简单讲解常用数据结构的实现，以及四中基本操作算法的时间复杂度。
3.1 线性顺序表（类似于Java集合中的ArrayList）
3.1.1 用数组自定义实现线性顺序表
/**
* 用数组自定义实现线性顺序表
* Java的ArrayList默认就是用动态数据实现的
*/
public class MyArrayList{
private int maxLength=10; //数组默认大小；
private int size; //数组当前下标；
private Object[] elementDatas;
public MyArrayList(int length){
this.maxLength=length;
this.elementDatas=new Object[length];
}
public MyArrayList(){
this(10);
}
public boolean addItem(Object e){
if(size==maxLength){
//超出设定的长度，返回false
return false;
}
elementDatas[size++]=e;
return true;
}
public Object getItem(int index){
if(index<0||index>size) return null
return elementDatas[index];
}
void ensureCap(int cap){
Object[] T=elementDatas;
elementDatas=T;
for(int i=0;i<size;i++){
elementDatas[i]=T[i];
}
}
//添加指定位置的元素
public boolean addItem(int index ,Object e){
if(size==maxLength) ensureCap(size*2);
if(index<0&&index>size){
//index不在数组范围内
return false;
}
if(index<=size){
for(int k=size;k>=index;k--){
//将下标index到size的元素向后移动一位
elementDatas[k+1]=elementDatas[k];
}
}
}
elementDatas[index]=e;
index++;
return true;
}
//移除指定位置元素
public boolean remove(int index){
if(index==0) return false;
if(index<0||index>size)return false;
if(index<=size){
for(int k=index;k<size;k++){
//将下标index到size的元素
elementDatas[k]=elementDatas[k+1];
}
}
//尾元素置空
elementDatas[size]=null;
size--;
}
}
}
3.1.2 增删改查的算法时间复杂度
| get | set | add | remove |
|---|---|---|---|
| O(1) | O(1) | O(n) | O(n) |
3.1.3 小结
上面的时间复杂度表明，线性顺序表随机读写元素的效率高，插入和删除元素的效率低。
3.2 线性单链表
链表实现原理图，可参考文章2，画的原理图很形象。
3.2.1 自定义实现单链表
public class MySingleLinkList{
//定义结点结构
class Node{
//结点数据
private Object data;
//结点指针
private Node next;
Node(Object e){
this.data=e;
}
}
public MySingleLinkList(){
}
public MySingleLinkList(Object o){
this.data=o;
}
public Node head;//头指针
public Object data;
public boolean isEmpty(){
return this.head==null;
}
//获取链表长度
public int length(){
Node p=head; //定义移动指针
int i=0;
//节点循环
while(p!=null){
i++;
p=p.next;
}
return i;
}
//添加元素
public boolean add(int index,Object o){
if(o!=null&&index>=0){
Node q=new Node(o); //构造新结点
if(head==null||index==0){
//空链表或者表头添加元素
q.next=head;
head=q;
}else{
//表中间或者结尾插入元素
//定义移动指针
Node p=head;
int i=0;
//循环找到插入节点前一个节点
while(p.next!=null&&i<index-1){
i++;
p=p.next;
}
q.next=p.next; //先赋值插入节点的指针；
p.next=q; //在赋值前一个节点的指针指向插入节点；
}
return ture;
}
return false;
}
//获取指定位置的元素
public Object get(int index){
if(head!=null&&index>=0){
Node p=head;//定义移动指针
int i=0;
while(p.next!=null&&i<index){
i++;
p=p.next;
}
if(p!=null) return p.data;
}
return null;
}
//设置某个位置元素
public boolean set(int index,Object o){
if(head!=null&&index>=0&&o!=null){
Node p=head; //定义移动指针；
int i=0；
while(p.next!=null&&i<index){
i++;
p=p.next;
}
if(p!=null)p.data=o;
return true;
}
return false;
}
public boolean remove(int index){
if(head!=null&&index>=0){
if(index==0){
//删除头节点
head=head.next;
}else{
Node p=head;
int i=0;
while(p.next!=null&&i<index-1){
//定位到删除节点的前一个节点
i++;
p=p.next;
}
p.next=p.next.next;
}
return true;
}
return false;
}
}
3.2.2 增删改查算法时间复杂度
| get | set | add | remove |
|---|---|---|---|
| O(n) | O(n) | O(n) | O(n) |
链表的添加和删除时间复杂度是O(n)，因为需要循环查找位置，找到位置以后，赋值操作是O(1),所以添加删除元素的效率要比线性顺序列表高。
3.2.3 小结
单链表添加删除元素效率较高，随机查询元素效率较低。
3.3 双链表（类似于JAVA集合中的LinkedList）
/**
* 双链表实现
*/
public class MyDoubleLinkedList {
class Node{
private Object data;
private Node prev; //前指针
private Node next; //后指针
Node(){
}
//构造节点
Node(Object data){
this.data=data;
}
}
private Node head; //头指针
private int size;// 链表索引长度
public MyDoubleLinkedList(){
//初始化头指针
this.head=new Node();
}
//尾部添加元素
public boolean add(Object object){
if (object!=null){
Node p= head;
while (p!=null){
p=p.next;
}
Node q=new Node(object);
p.next=q;
q.prev=p;
size++;
return true;
}
return false;
}
//添加指定索引位置的数据
public boolean add(int index,Object object){
if(object!=null&&index>=0){
if (index>size){
add(object);
}else {
Node p=head;//定义移动指针
int i=0;
while (p!=null&&i<index){
//查找到index的位置
i++;
p=p.next;
}
if (p!=null){
Node q=new Node(object); //定义要插入的元素
q.prev=p.prev;
q.next=p;
if (p.prev!=null) p.prev.next=q;
p.prev=q;
size++;
}
}
return true;
}
return false;
}
public boolean remove(int index){
if (index>=0){
if (index==0) index=1;
Node p=head;
int i=0;
while (p!=null&&i<index){
i++;
p=p.next;
}
if (p!=null){
p.prev.next=p.next;
p.next.prev=p.prev;
}
size--;
return true;
}
return false;
}
//设置元素
public boolean set(int index,Object o){
if (index>=0&&o!=null){
Node p=head; //定义移动指针；
int i=0;
while (p!=null&&i<index){
i++;
p=p.next;
}
if (p!=null){
p.data=o;
}
}
return false;
}
//获取指定元素
public Object get(int index){
if (index>=0){
Node p=head;
int i=0;
while (p!=null&&i<index){
i++;
p=p.next;
}
if (p.next!=null) return p.data;
}
return null;
}
}
3.4 循环链表
3.5 栈
概念已经被大家说烂了（后进先出或者先进后出的线性表结构）。
3.5.1 数组实现栈（类似与Java中的ArrayDueue）
public class MyArrayStack{
private int size; //内部数组当前下标
private int maxLength=10; //内部数组默认长度;
private int top=-1;//栈顶指针;
private Object[] elementDatas;
MyArrayStack(int length){
this.maxLength=length;
this.elementDatas=new Object[length];
}
MyArrayStack(){
this(10);
}
//压栈
public void push(Object e){
if(elementDatas.length==size){
//动态扩容
ensureCap(size*2);
}
size++;
elementDatas[++top]=e;
}
//出栈-从栈顶移除元素
public Object pop(){
if(top==-1) new StackExceptio();
size--;
renturn element[top--];
}
//查询栈顶元素
public Object peek(){
if(top==-1) new StackException();
return element[top];
}
//内部数组扩容
void ensureCap(int cap){
if(cap<size) return;
Object[] T=elementDatas;
elementDatas=new Object[cap];
for(int i=0;i<size;i++){
elemetnDatas[i]=T[i];
}
}
}
3.5.2 顺序表(ArrayList)实现栈
public class MyColStack{
private ArrayList arrayList;
MyColStack(){
arrayList=new ArrayList();
}
public void push(Object e){
arrayList.add(e);
}
public Object pop(){
if(arraylist.size==0) new EmptyStackExceptio();
return arrayList.remove(arrayList.size()-1);
}
public Object peek(){
if(arrayList.size==0) new EmptyStackException();
return arrayList.get(arrayList.size()-1);
}
}
3.5.3 链表栈
public class MyLinkedStack {
//节点
class Node{
Node next;
Object object;
Node(Object o){
this.object=o;
}
Node(){
}
}
//头节点
private Node head;
private int size;
public MyLinkedStack() {
this.head = null;
size = 0;
}
public boolean isEmpty(){
return this.head==null;
}
public int length(){
return size;
}
/**
* 入栈-在表头插入数据
* @param o
*/
public void push(Object o){
if (o==null) return ;
Node old=head;
head=new Node();
head.object=o;
head.next=old;
size++;
}
/**
* 出栈
* @return
*/
public Object pop(){
if (isEmpty()) return new NoSuchElementException("stack ");
Object item=head.object;
head=head.next;
size--;
return item;
}
/**
* 查看栈顶元素
* @return
*/
public Object peek(){
if (isEmpty()) return new NoSuchElementException("stack ");
Object item=head.object;
return item;
}
}
3.5.4 栈算法时间复杂度
| push | pop | peek |
|---|---|---|
| O(1) | O(1) | O(1) |
3.6 队列
队列实现原理图，可参考文章2，画的原理图很形象。
3.6.1 利用数组实现顺序队列
public class MySeqQueue {
private Object[] value; //存储元素；
private int front;
private int rear;
MySeqQueue(int length){
value=new Object[Math.abs(length)];
front=-1;
rear=-1;
}
MySeqQueue(){
this(16);
}
public boolean isEmpty(){
return front==-1&&rear==-1;
}
//扩展容量
void ensureCap(int size){
Object[] T=value;
value=new Object[size];
for (int i=0;i<size;i++){
value[i]=T[i];
}
}
//入队
public boolean enqueue(Object o){
if (o!=null) return false;
if (isEmpty()) {
value[0]=o;
front++;
rear++;
}else {
if (rear==value.length-1){
ensureCap(value.length*2);
}
value[++rear]=o;
}
return true;
}
//出队
public Object dequeue(){
if (isEmpty())return null;
Object temp=value[front];
front++;
return temp;
}
}
3.6.2 循环队列
/**
* 数组实现循环队列
*/
class MySeqCycleQueue {
private Object[] objects; //存储队列的数组元素
private int front; //队头下标
private int rear; //队尾下标
public MySeqCycleQueue(int size){
objects=new Object[size];
front=0;
rear=0;
}
public MySeqCycleQueue(){
this(16);
}
public boolean isEmpty(){
//循环队列在中间也有可能front和rear相同，所以不能用front==rear==0.来判断
return front==rear;
}
public boolean enqueue(Object o){
if (o!=null) return false;
if (front==(rear+1)%objects.length){
//队满——注意队满的情况会预留一个空位，防止front==rear，这里采用了取模运算
ensureCap(objects.length*2);
}
objects[rear]=o;
rear=(rear+1)%objects.length; //rear下标变化规律，入队移动rear下标
return true;
}
void ensureCap(int size){
Object[] old=objects;
objects=new Object[size];
for(int i=0;i<size;i++){
objects[i]=old[i];
}
}
boolean dequeue(){
if (!isEmpty()){
front=(front+1)%objects.length;//出队移动front下标
return true;
}
return false;
}
}
3.6.3 链式循环队列
/**
* 链表实现循环队列
*/
public class MyLinkedQueue {
public MyLinkedQueue() {
head=null;
tail=null;
n=0;
}
class Node{
Node next;
Object object;
Node(Object o){
this.object=o;
}
Node(){
}
}
//头节点
Node head;
//尾节点
Node tail;
int n;
public boolean isEmpty(){
return head==null;
}
public int length(){
return n;
}
/**
* 入队
*/
public void enqueue(Object o){
if (o==null) return;
Node old=tail;
tail=new Node();
tail.object=o;
tail.next=null;
if (isEmpty()) head=tail;
else old.next=tail;
n++;
}
/**
* 出队
*/
public Object dequeue(){
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Object o=head.object;
head=head.next;
n--;
if (isEmpty())tail=null;
return o;
}
public Object peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return head.object;
}
}
3.6.4 循环队列时间复杂度
| enqueue | dequeue |
|---|---|
| O(1) | O(1) |
代码地址：https://github.com/ywqyunshan/LearnCode/tree/master/src/com/iigeo/datastrut
参考文章
1.数据结构与算法——常用数据结构及其Java实现.MageekChiu
2.Java数据结构与算法.zejian的博客
3.数据结构.人生设计师的博客
