线性表 - 数组和矩阵

数组是一种连续存储线性结构，元素类型相同，大小相等，数组是多维的，通过使用整型索引值来访问他们的元素，数组尺寸不能改变

数组的优点:

  • 存取速度快

    数组的缺点:

  • 事先必须知道数组的长度

  • 插入删除元素很慢
  • 空间通常是有限制的
  • 需要大块连续的内存块
  • 插入删除元素的效率很低

    线性表 - 链表

    n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来
    [

](https://www.pdai.tech/md/algorithm/alg-basic-linklist.html)

优缺点

链表优点

  • 空间没有限制
  • 插入删除元素很快

链表缺点 存取速度很慢

分类

  • 单向链表 一个节点指向下一个节点。
  • 双向链表 一个节点有两个指针域。

  • 循环链表 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环

    实现

    数据结构基础 - 图1

    节点

    1. public class Node {
    2.   //数据域
    3.   public int data;
    4.   //指针域，指向下一个节点
    5.   public Node next;
    7.   public Node() {
    8.   }
    9.   public Node(int data) {
    10.       this.data = data;
    11.   }
    12.   public Node(int data, Node next) {
    13.       this.data = data;
    14.       this.next = next;
    15.   }
    16. }

    如上，一个链表节点对象就创建完成了，但理解链表本身并不难，但做相关的操作却并非易事，其算法包括且不限于:

  • 插入节点

  • 遍历
  • 查找
  • 清空
  • 销毁
  • 求长度
  • 排序
  • 删除节点
  • 去重

    线性表(散列) - 哈希表

    散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表