数据结构与算法（Java 语言描述）【三】

常用数据结构

数组

• 特点：

  • 一般具有固定长度，下标从0开始，具体如下图

  

• 逻辑结构：逻辑上连续的多个关联数据，能通过下标或遍历快速访问

• 物理结构：存储在连续的内存中

• 优点：

  • 按照下标查找速度快

  • 遍历方便

• 缺点：

  • 无法扩容

  • 只能存储一种类型的数据

  • 插入、删除效率低

• Java语言中一般数组的定义方法如下：

  int[] data = new int[10];

• 详细示例见附件中的ArrayDemo.java

链表

• 特点：

  • 没有限定的数据长度，查找数据需要通过整个链表遍历的方式实现

  • 常见的有单向链表、双向链表、循环链表等，具体如下图：

• 逻辑结构：逻辑上连续的多个关联数据，能通过遍历的访问实现顺序访问

• 物理结构：存储在非连续的内存空间中，包含数据域和指针域，指针域的指针指向其相邻数据的内存地址

• 优点：

  • 无需像数组一下初始化容量，可任意插入或删除数据

  • 插入、删除数据效率高

• 缺点：

  • 要多一个指针域，相对会占用更多存储空间

  • 查找数据需要遍历整个链表，效率低

• Java语言中单向链表的定义方法如下

  LinkedList<String> data = new LinkedList<>();

• 详细示例见附件中的LinkedListDemo.java

【备注：部分图片来自网络】