简介
线性结构是一个有序元素集合
常用的线性结构有:线性表,栈,队列,双队列,数组,串
关于广义表,是一种非线性数据结构
常见的非线性结构有:二维数组,多维数组,树(二叉树等),广义表,图。
线性表
- 顺序表
顺序表将元素存储在一组连续的单元中,在物理内存上是连续的,就是说内存地址是连续的。
顺序的密度比较大,节省空间。读取的时间复杂度为:O(1),查询的时间复杂度为 O((n-0)/2),插入或者删除的时间复杂度为 O((n-0)/2),删除的时间复杂度为 O((n-1)/2)
- 链表
链表拥有很多结点,每个结点前半部分是数据域,后半部分是指针域,指针域指针指向下一个结点;链表可分为单链表、循环链表和双链表。
单链表
从结构可以看出,单链表有一个头部节点,没有 data 域,直接指向第一个节点 p1,第一个节点分为两个部分,一个是 data 域,一个是指针域,指针域指向下一个节点 p2,最后一个节点的指针域为 NULL.
链表的密度比较散列。读取的时间复杂度为 O((n+1)/2),查询的时间复杂度为 O(n/2),插入的时间复杂度为 O(1),删除的时间复杂为 O(1)