“线性表（Linear List）”：由同类型数据元素构成的有序序列的线性结构
1.表中元素个数称为线性表的长度
2.线性表没有元素时，称为空表。
3.表起始位置称为表头，表的结束位置称为表尾。
类型名称：线性表(List)
数据对象集：线性表是n(n>=0)个元素构成的有序序列（a1,a2,a3….）
操作集：线性表L∈List，整数i表示位置，元素X∈ElementType.
线性表的基本操作：
1.List MakeEmpty(); 初始化一个空线性表L
2.ElementType FindKth(int k,List l);根据位序K,返回相应的元素
3.int Find(ElementType X,List L);在线性表L中查找X的第一次出现的位置
4.void Insert(ElementType X,int i,List L)；在位序i前插入一个新元素X
5.void Delete(int i,List L); 删除指定次序的元素
6.int Length(List L);返回线性表L的长度n。
基本思想：元素的存储是连续的，在内存中以顺序存储。
如图所示：
顺序表代码实现（利用数组内存顺序存储的特点）
package com.simon.datastructure.javadatastructure;
/**
* auther: Simon zhang
* Emaill:18292967668@163.com
* 线性结构之顺序表的实现
*
*/
public class LinearArrayList<E> {
/**
* 用于存储元素的数组
*/
private Object[] elements;
/**
* 当前数组有多少个元素
*/
private int size;
/**
* 线性表容量
*/
private int capacity;
public LinearArrayList() {
this(10);
}
/**
* 初始化一个空线性表L
* @param capacity
*/
public LinearArrayList(int capacity) {
if(capacity<0){
throw new IllegalArgumentException("initial capacity can't less than zero");
}else{
this.capacity = capacity;
size=0;
elements=new Object[capacity];
}
}
/**
* 根据位序K,返回相应的元素
* @param index
* @return
*/
public E get(int index){
validateIndex(index);
return (E) this.elements[index];
}
/**
* 验证下标是否合法
* @param index
*/
private void validateIndex(int index) {
if(index<0||index>size){
throw new IllegalArgumentException("index out Of Bound Index:"+index+"Size:"+size);
}
}
/**
* 在线性表L中查找X的第一次出现的位置
* @param e
* @return
*/
public int indexOf(E e){
if(e==null){
for (int i = 0; i <size ; i++) {
if(elements[i]==null){
return i;
}
}
}else{
for (int i = 0; i <size ; i++) {
if(e.equals(elements[i])){
return i;
}
}
}
return -1;
}
/**
* 插入一个新元素X
* @param e
* @return
*/
public void add(E e){
ensureCapacity(size+1);
elements[size++]=e;
}
/**
* 数组扩容
* @param size
*/
private void ensureCapacity(int size) {
/* if(size>capacity){
capacity=size;
Object[] temps=new Object[capacity];
for (int i = 0; i <elements.length ; i++) {
temps[i]=elements[i];
}
elements=temps;
}*/
//优化.扩容的时候不是每次都加1,避免频繁扩容
if(size>capacity) {
capacity = capacity+(capacity>>1);
Object[] temps = new Object[capacity];
for (int i = 0; i < elements.length; i++) {
temps[i] = elements[i];
}
elements = temps;
}
}
/**
* 在位序i前插入一个新元素X
* @param e
* @return
*/
public void add(E e,int index){
validateIndex(index);
//问题：数组要不要扩容 答：肯定要扩容。 因为数组是连续存储，不为空.
ensureCapacity(size+1);
size++;
Object[] temps=new Object[capacity];
for (int i = 0; i <size; i++) {
if(i<index){
temps[i]=elements[i];
}else if(i==index){
temps[i]=e;
}else {
temps[i]=elements[i-1];
}
}
this.elements=temps;
}
/**
* 删除指定次序的元素
* @param index
* @return
*/
public E remove(int index){
E oldValue= (E) elements[index];
Object[] temps=new Object[size-1];
for (int i = 0; i <size; i++) {
if(i<index){
temps[i]=elements[i];
}else if(i>=index){
temps[i]=elements[i-1];
}
}
size--;
this.elements=temps;
return oldValue;
}
/**
*
* 返回线性表L的长度n。
* @return
*/
public int size(){
return this.size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i < size; i++) {
sb.append(elements[i].toString());
if(i!=size-1){
sb.append(',');
}
}
sb.append(']').toString();
return sb.toString();
}
}
基本思想：不要求逻辑上相邻的两个元素物理上也相邻。 通过”链”建立起数据元素之间的逻辑关系。插入和删除，不需要移动元素，只需要修改链。
单链表
循环链表
三者的区别和特点：
单向链表代码实现：
package com.simon.datastructure.javadatastructure;
/**
* auther: Simon zhang
* Emaill:18292967668@163.com
*
* 线性表的链表代码实现
*/
public class LinearLinkedList<E>{
/**
* 头节点
*/
private Node<E> header;
/**
* 当前节点数量
*/
private int size;
/**
* 初始化一个空线性表链表L
* @param
*/
public LinearLinkedList() {
}
/**
* 根据位序K,返回相应的元素
* @param index
* @return
*/
public E get(int index){
if(index<0||index>size-1){
throw new IllegalArgumentException("Index out Of Bound Index:"+index+"Size:"+size);
}
Node<E> temp=header;
int count=0;
while (index!=count){
temp=temp.next;
count++;
}
return temp.item;
}
/**
* 根据位序K,返回对应位置的节点
* @param index
* @return
*/
public Node getNode(int index){
if(index<0||index>size-1){
throw new IllegalArgumentException("Index out Of Bound Index:"+index+"Size:"+size);
}
Node<E> temp=header;
int count=0;
while (index!=count){
temp=temp.next;
count++;
}
return temp;
}
/**
* 在线性表链表L中查找X的第一次出现的位置
* @param e
* @return
*/
public int indexOf(E e){
Node<E> temp=header;
int count=0;
if(e==null){
while (count!=size){
if(temp.item==null){
return count;
}
temp=temp.next;
count++;
}
}else{
while (count!=size){
if(temp.item.equals(e)){
return count;
}
temp=temp.next;
count++;
}
}
return -1;
}
/**
* 在插入一个新元素X
* @param e
* @return
*/
public void add(E e){
Node<E> insertNode=new Node<>(e);
if(size==0){
header=insertNode;
}else{
Node lastNode=getNode(size-1);
lastNode.addNextNode(insertNode);
}
size++;
}
/**
* 在位序i前插入一个新元素X
* @param e
* @return
*/
public void add(E e,int index){
if(index<0||index>size){
throw new IllegalArgumentException("Index out Of Bound Index:"+index+"Size:"+size);
}
Node<E> insertNode=new Node<>(e);
if(size==0){
header=insertNode;
}else {
//找到index对应的node, 然后把他的next节点置为e, e的next节点置为index node的next
Node<E> temp = getNode(index-1);
insertNode.addNextNode(temp.next);
temp.addNextNode(insertNode);
}
size++;
}
/**
* 删除指定次序的元素
* @param index
* @return
*/
public E remove(int index){
E oldValue;
if(index<0||index>size-1){
throw new IllegalArgumentException("index out Of Bound Index:"+index+"Size:"+size);
}
//移除头节点
if(index==0){
header=header.next;
oldValue=header.item;
}else{
//找到index对应的node, 然后把他的next节点置为index对应的节点的next。
Node<E> temp=getNode(index-1);
oldValue= temp.next.item;
temp.addNextNode(temp.next.next);
//清空引用
temp.next.next=null;
}
size--;
return oldValue;
}
/**
*
* 返回线性表L的长度n。
* @return
*/
public int size(){
return this.size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
Node<E> temp=header;
while (temp.next!=null){
sb.append(temp.item.toString());
sb.append(',');
temp=temp.next;
}
sb.append(temp.item.toString());
sb.append(']').toString();
return sb.toString();
}
/**
* 链表节点对象
* @param <E>
*/
class Node<E>{
/**
* 当前数据对象
*/
E item;
/**
* 下一个节点
*/
Node<E> next;
public Node() {
}
public Node(E item) {
this.item = item;
}
void addNextNode(Node<E> node){
this.next=node;
}
}
}
目前实现的单链表还有一些两点不足之处：
1.每次添加元素都需要迭代链表。
2.移除元素是，应该清空删除元素的引用。
线性表总结：
1. 顺序表的随机访问速度比链表的要快，因为顺序表的随机访问直接根据索引查找元素，而链表还需要迭代访问元素。
2. 链表的插入和删除速度要快于顺序表。 因为插入的时候顺序表可能进行扩容，删除的时候顺序表要进行移位操作。
疑问？
为什么LinkedList(链表)的迭代速度快于ArrayList呢？
参考：
1.中国大学数据结构课程（浙江大学）
2. http://blog.csdn.net/chenleixing/article/details/42392283