1.1.线性表
线性表是指由同种元素构成的有序且线性的一种数据结构，由于其有序且线性的特点，可以抽象出对其的一个操作集：
ElementType findKth(int k)//查找位序为K的元素 int find(ElementType e)//查找元素e出现的第一次位置 void insert(ElementType e,int i)//在位序i前面插入一个元素 void delete(int i)//删除位序i的元素 int length()//返回线性表的长度
线性表的实现有两种：
- 数组
- 队列
1.1.1.数组
1.逻辑简介
数组操作中要注意的操作是在中间插入或者删除，要涉及元素的位移。
在数组中间删除：
删除数组中间某个位置的元素，为了保持连续，后面的元素要挨个前移。
在数组中间插入：
在数组中间某个位置插入元素，首先要腾出位置，也就是说，该位置后面的元素要挨个后移
2.代码实现
使用代码实现顺序表：
public class Array{ //数组 private Object[] array; private int maxSize; //初始化一个空数组 public void initArray(int maxSize){ this.maxSize=maxSize; array=new Object[maxSize]; } //查找位序为K的元素 public Object findKth(int K){ return array[K]; } //查找元素X第一次出现的位置 public int find(Object X){ int i=0; while(!X.equals(array[i])){ i++; } return i; } //查找最后一个非空元素位置的位序 public int findLastTh(Object[] targetArray){ int i=0; for (int j=0;j<targetArray.length;j++){ if(array[j]!=null){ i=j; } } return i; } //在i位序插入一个元素 public void insert(Object X,int i){ System.out.println("当前数组的容量:"+array.length); //判断是否存满，是否需要追加空间。 if(isFull()){ newSpace(); } //若插入位置上没有元素则直接插入 if(array[i]==null){ array[i]=X; } else //若插入位置上有元素则当前位置开始顺序后移一位 { for (int j = findLastTh(array); j >= i; j--) { array[j + 1] = array[j]; } array[i] = X; } } //判断数组是否已经存满 public boolean isFull(){ return array[array.length-1]!=null ? true:false; } //为数组开辟新空间 public void newSpace(){ //copy原数组 Object[] tempArry=this.array; //记录原数组 //追加新空间,追加容量为初始化容量的一倍 array=new Object[maxSize+maxSize]; //将原数组元素，copy到新数组 for (int i=0;i<=findLastTh(tempArry);i++){ array[i]=tempArry[i]; } System.out.println("扩容后数组容量:"+array.length); } //打印表中所有元素 public void print() { int i=0; String s=""; while (i<=findLastTh(array)) { s=s+i+":"+array[i]+"\t"; i++; } System.out.println(s); } }
1.1.2.链表
1.逻辑简介
链表操作中要注意的操作是在中间插入或者删除，要涉及指针的操作。
在链表中间删除：
在链表中间删除一个元素，即将该元素前一个节点的指针指向要删除节点的下一个节点，即要删除节点的指针所指向的位置，然后将要删除的节点的指针指向空。
2.代码实现
链表中的每个节点：
public class Node{ //数据域 Object data; //指针域 Node next; 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; } }
使用链表实现顺序表：
public class List { //节点 public class Node{ //数据域 Object data; //指针域 Node next; 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; } } //尾指针 Node last; //遍历指针 Node flag; //头节点 Node header; //初始化头节点 //初始化末尾指针 public List(){ this.header=new Node(); this.header.setData("header"); this.last=header; } //插入 public void insert(Object data){ Node newNode=new Node(); newNode.setData(data); last.setNext(newNode); //指针后移 last=newNode; } //指定位置插入 //插入在指定节点的后面 //header位序为0，依次类推 //此方法无法实现直接挂在末尾，挂在末尾请用上面的无参insert() public void insert(int X,Object data){ //遍历指针指向头节点 this.flag=header; //计数器 int i=0; Node newNode=new Node(); newNode.setData(data); //查找动作 while(i<X){ flag=flag.getNext(); i++; } //删除动作 //后面节点挂在当前节点后 newNode.setNext(flag.getNext()); //当前节点挂在目标节点后 flag.setNext(newNode); } //遍历打印链表 public void printf(){ //遍历指针指向头节点 this.flag=header; //消息 String message=""; while (flag.getNext()!=null){ message=message+flag.getData()+"—>"; flag=flag.getNext(); } //拼接最后一个节点 message=message+flag.getData()+"—>"; System.out.println(message); } //删除指定位序节点 public void delete(int X){ //遍历指针指向头节点 this.flag=header; //计数器 int i=0; //查找动作 while(i<X-1){ flag=flag.getNext(); i++; } //删除动作 flag.setNext(flag.getNext().getNext()); } }
1.2.堆栈
1.2.1.逻辑简介
堆栈，一种后入先出（LIFO，last in frist out）或者叫先入后出（FILO，first in last out）的线性且有序的数据结构。
堆栈的操作集可抽象为：
Boolean isFull();//判断堆栈是否已满 Boolean isEmpty();//判断堆栈是否为空 void push();//入栈 void pop();//出栈
1.2.2.代码实现
此处的代码实现以数组来存储数据，数组进行出入堆栈的时候会涉及位移操作，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。
public class Stack { //数据域 Object[] stack; //头指针 int first=0; //尾指针 int last=-1; public Stack(int size){ stack=new Object[size]; } //判断堆栈是否已满 public Boolean isFull(){ return (stack.length-1)==last; } //判断堆栈是否为空 public Boolean isEmpty(){ return last==-1; } //入栈 public void push(Object o){ if(!isFull()) { stack[++last] = o; } } //出栈 public Object pop(){ Object data=null; if(!isEmpty()) { data=stack[last]; stack[last] = null; last--; } return data; }
1.3.队列
1.3.1.逻辑简介
队列，一种先进先出（FIFO，first in first out）或者叫后进后出（LILO，last in last out）的线性且有序的数据结构。
队列的理解不难，就像我们生活中排队时的各种队列一样，就是先进先出，后进后出。
队列的操作集可抽象为：
Boolean isFull();//判断队列是否已满 Boolean isEmpty();//判断队列是否为空 void push();//入队 void pop();//出队
1.3.2.代码实现
此处的代码实现以数组来存储数据，比起链表来说还更复杂一点，链表的话直接操作指针的指向即可更加方便。
public class Queue { //数据域 Object[] stack; //头指针 int first=0; //尾指针 int last=-1; public Queue(int size){ stack=new Object[size]; } public Boolean isFull(){ return (stack.length-1)==last; } public Boolean isEmpty(){ return last==-1; } public void push(Object o){ if(!isFull()) { stack[++last] = o; } } public Object pop(){ Object o=stack[first]; //删除头元素，后续元素顺序前移 stack[first]=null; if(!isEmpty()) { for (int i = 1; i <=last; i++) { Object temp=stack[i]; stack[i-1]=temp; } stack[last--]=null; } return o; } }
1.4.性能对比
从链表和数组的结构特点和使用过程中可以看到，数组和链表在增删改查各个场景中性能各有优劣：
- 查找和遍历时是数组性能更好，因为存储是挨在一起的。链表的话则需要通过指针来寻址。
- 增加和删除时链表性能更好，因为数组中间元素的增加删除涉及后面元素的位移，明显不如链表只动一个元素的性能。
