侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 102 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

数据结构(2) - 线性表

惊羽
2021-03-15 / 0 评论 / 0 点赞 / 253 阅读 / 810 字
温馨提示:
本文为原创作品,感谢您喜欢~

线性表

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
广告 广告

评论区