侧边栏壁纸
博主头像
buukle博主等级

布壳儿

  • 累计撰写 106 篇文章
  • 累计创建 15 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

数据结构(2) - 线性表

administrator
2021-03-15 / 0 评论 / 0 点赞 / 275 阅读 / 1448 字

线性表

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.一元多项式的求解

0

评论区