线性表

1.含义

用来存储线性关系一组数据,同时对外部提供相应api算法的数据结构;

2.分类

• 顺序存储
• 链式存储

3.顺序存储

1.含义:线性数据在内存中以连续的地址存储

2.举例

Integer[] arr = {1,2,3,4};
    List<Integer> templist = Arrays.asList(arr);
    //由源码可知, templist 为ArrayList
    /**
     * Arrays.asList(arr) 源码 :
     * public static <T> List<T> asList(T... a) {
     *   return new ArrayList<>(a);
     * }
    */
ArrayList<Integer> arrayList = (ArrayList<Integer>) templist;
//时间复杂度分析 :
    //(1) 查询 get(index i) : O(1)
    arrayList.get(1);
    // arrayList 在内存中是以按照存储的,所以可以通过第一个元素的地址和索引的关系直接计算出给定索引的元素所在位置,故可以实现根据索引随机访问列表数据,不需要遍历整个arrayList;
    //(2) add(index i,element e) : O(n)
    arrayList.add(1,1);
    // arrayList 由于按照顺序存储,在向指定索引 index 处插入数据时候,需要把index后边的元素全部向后移动一个位置,操作次数近似为n;
        

4.链式存储

1.含义:线性数据在内存中以逻辑关系链式存储(通过 前驱(pre) 后继(next) 等);

2.分类

• 单向链表
• 双向链表
• 循环链表
• ......

3.举例

    LinkedList linkedList = new LinkedList();
    时间复杂度分析 :
    //(1) 查询 get(index i) : O(1)
    //(2) add(index i,element e) : O(n)

5.应用

1.一元多项式的求解