一、线性表
线性表是最基本、最简单、也是最常用的一种数据机构，一个线性表是n个具有相同特性的数据元素的有限序列

前驱元素：

若A元素再B元素的前面，则称A为B的前驱元素。

后继元素：

若B元素再A元素的前面，则称B为A的前驱元素。

线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。

1、第一个数据元素没有前驱，这个数据元素被称为头结点。

2、最后一个数据元素没有后继，这个数据元素被称为尾结点。

3、除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱元素和后继元素。

线性表的分类：

线性表中数据存储的方式可以是顺序存储，也可以是链式存储。按照数据的存储方式的不同，可以把线性表分为顺序表和链表。

1、1 顺序表

1.1.1、顺序表的实现

package test.linear;

import org.apache.poi.ss.formula.functions.T;

public class SequenceList {
    //储存元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //初始化数组
       this.eles = (T[]) new Object[capacity];
       //初始化长度
        this.N=0;
     }
    //建一个线性表置为空表
     public void clear(){
        this.N=0;
     }
     //判断该表是不是空表
     private boolean isEmpty(){
        return N==0;
     }

     public int length(){
        return N;
     }

     public T get(int i){
        return eles[i];
     }
     //向线性表插入元素
     public  void insert(T t){
        eles[N++]=t;
     }
    //向线性表位置I出的元素插入元素t
    public  void insert(int i,T t){
        N++;
        for (int index = N-1; index >i ; index--) {
                eles[index]=eles[index-1];
        }
        eles[i]=t;

    }

    //删除指定位置的元素，并返回该元素
    public  T remove(int i){
        T t = eles[i];
        for (int index = i; index  
 
 
1.1.2 顺序表的遍历 
一般作为容器存储数据，都需要像外部提高遍历的方法，因此我们需要给顺序表提供遍历方式。 
再java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则需要做如下操作： 
1、让SequenceList实现iterable接口，重写iterator接口； 
2、在SequenceList内部提供一个内部类Siterator,实现iterator接口，重写hasNext()方法和next()方法； 
代码： 
package test.linear;

import org.apache.poi.ss.formula.functions.T;
import java.util.Iterator;


public class SequenceList implements Iterable {
    //储存元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //初始化数组
       this.eles = (T[]) new Object[capacity];
       //初始化长度
        this.N=0;
     }
    //建一个线性表置为空表
     public void clear(){
        this.N=0;
     }
     //判断该表是不是空表
     private boolean isEmpty(){
        return N==0;
     }

     public int length(){
        return N;
     }

     public T get(int i){
        return eles[i];
     }
     //向线性表插入元素
     public  void insert(T t){
        eles[N++]=t;
     }
    //向线性表位置I出的元素插入元素t
    public  void insert(int i,T t){
        N++;
        for (int index = N-1; index >i ; index--) {
                eles[index]=eles[index-1];
        }
        eles[i]=t;

    }

    //删除指定位置的元素，并返回该元素
    public  T remove(int i){
        T t = eles[i];
        for (int index = i; index  iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator {

        private int cusor;

        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext(){
           return cusor 
 
1.1.3 顺序表的容量可变 
1、添加元素时： 
应当检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组俩倍容量的新数组存储元素 
 
 
 
2、移除数组时： 
移除数组时，应当检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样会造成空间的浪费，应当创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个原数组容量的1/2的新数组存储元素。 
 
 
package test.linear;

import org.apache.poi.ss.formula.functions.T;
import java.util.Iterator;


public class SequenceList implements Iterable {
    //储存元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //初始化数组
       this.eles = (T[]) new Object[capacity];
       //初始化长度
        this.N=0;
     }
    //建一个线性表置为空表
     public void clear(){
        this.N=0;
     }
     //判断该表是不是空表
     private boolean isEmpty(){
        return N==0;
     }

     public int length(){
        return N;
     }

     public T get(int i){
        return eles[i];
     }
     //向线性表插入元素
     public  void insert(T t){
        if(N>=eles.length){
            resize(2*eles.length);
        }
        eles[N++]=t;
     }
    //向线性表位置I出的元素插入元素t
    public  void insert(int i,T t){
        if(N>=eles.length){
            resize(2*eles.length);
        }
        N++;
        for (int index = N-1; index >i ; index--) {
                eles[index]=eles[index-1];
        }
        eles[i]=t;

    }

    //删除指定位置的元素，并返回该元素
    public  T remove(int i){

        T t = eles[i];
        for (int index = i; index  iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator {

        private int cusor;

        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext(){
           return cusor 
 
1.1.4时间复杂度 
 
1.1.5 java中ArrayList实现 
ArrayList底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。 
1、是否用数组实现 
2、有没有扩容操作 
3、有没有提供遍历方式

算法-线性表-顺序表

1、1 顺序表

1.1.4时间复杂度

1.1.5 java中ArrayList实现 ArrayList底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。 1、是否用数组实现 2、有没有扩容操作 3、有没有提供遍历方式

Java相关栏目本月热门文章

1.1.5 java中ArrayList实现
ArrayList底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。

1、是否用数组实现

2、有没有扩容操作

3、有没有提供遍历方式