线性表的学习

学习目标

  • 线性表的定义
  • 线性表的存储方式和表达方式
  • 基本实现
  • 基本操作实现
  • 双向链表插入和删除实现
  • 循环单链表和循环双向链表的结构特点

1. 线性表：
  • 定义：零个或多个数据元素所构成的有限序列
  • 存储方式：顺序存储结构和链式存储结构
  • 抽象数据类型描述
  1. public interface IList<E>{
  2.     void clear();//线性表清空操作
  3.     boolean isEmpty();// 判空
  4.     int size(); //长度
  5.     E get(int i);//通过下标获取元素
  6.     void insert(int i,E t);// 插入元素到特定位置
  7.     void remove(int i);// 移除元素
  8.     int indexOf(E t);// 查找元素
  9.     void display();//打印元素
  10. }

2. 线性表顺序存储结构：
  • 定义： 用顺序存储方法存储的线性表简称为顺序表（Sequential List）。

  • 节点存储地址的计算：

    • 假设每个节点占用c个存储单元
    • 其中第一个单元的存储地址则是该结点的存储地址; 并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1）
    • 所以结点ai的存储地址LOC（ai）： LOC（ai）= LOC（a1）+（i-1）*c 1≤i≤n

  • 顺序表的特点

    1. 逻辑上相邻的结点其物理位置亦相邻。
    2. 存储密度高； 存储密度= 数据元素所需的存储空间/该数据元素实际所占空间；需要预先分配”足够应用”的空间，可能会造成存储空间浪费
    3. 便于随机存储
    4. 不便于随机插入删除

3. 顺序表基本实现和分析
  1. 删除操作实现及分析
  • 代码实现
  1. public T remove(int i) {
  2.         // 首先，先判度下标 i 是否合法
  3.         if (i < 0 || i > this.lenght)
  4.             throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + this.lenght);
  5.         //获取删除的元素
  6.         T removeObj = (T) objects[i];
  7.         //把下标为i及其后的元素，往前移移一位
  8.         for (int j = i; j < this.lenght - 1; j++) {
  9.             objects[j] = objects[j + 1];
  10.         }
  11.         //把最后一个元素置空，帮助垃圾回收
  12.         objects[lenght - 1] = null;
  13.         //当前线性表长度减一
  14.         --lenght;
  15.         return removeObj;
  16.     }

  • 时间复杂度分析

    • 在n个元素的顺序表中，删除第i各元素，则0<=i<=n-1
    • 假设删除的概率相同，则p = 1/n
    • 删除第i个元素后，需要移动 n-i-1个元素
    • 平均移动的次数为 (1/n) * (n-i-1)求和
    • 所以时间复杂度为：O(n)
  1. 插入操作及分析
  • 代码实现
  1. public void insert(int i, T t) {
  2.         // 首先，先判度下标 i 是否合法
  3.         if (i < 0 || i > this.lenght)
  4.             throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + this.lenght);
  6.         //判断是否超出顺序表的容量
  7.         if (this.lenght >= this.objects.length)
  8.             throw new ArrayIndexOutOfBoundsException("length = " + this.lenght + " Capacity" + this.initCapacity);
  10.         //把下标为i及其后的元素，往后移移一位
  11.         for (int j = this.lenght - 1; j >= i; --j) {
  12.             objects[j + 1] = objects[j];
  13.         }
  14.         //插入元素
  15.         objects[i] = t;
  16.         lenght++;
  17.     }

  • 时间复杂度分析

    • 在长度为 n 的顺序表中，在第i个位置插入一个元素， 0<= i <= n
    • 插入元素前需要将第i个元素开始往后移动，需要移动n-i个元素
    • 假设插入每个位置的概率相同，则p = 1/(n+1)
    • 所以，平均移动次数为 (1/(n+1)) * (n-i) 求和 （0<= i <= n）
    • 则，平均时间复杂度为: O(n)
  1. 查找元素操作及其分析
  • 代码实现
  1. public int indexOf(E e) {
  2.     //先判断 元素是否为空，可防止空指针的出现
  3.     if (t == null) {
  4.         //为空则，返回顺序表中空元素的下标
  5.         for (int i = 0; i < this.lenght; i++)
  6.             if (objects[i] == null)
  7.                 return i;
  8.     } else {
  9.         //不为空，则返回与之匹配的元素下标
  10.         for (int i = 0; i < this.lenght; i++)
  11.             if (t.equals(objects[i]))
  12.                 return i;
  13.     }
  14.     return -1;
  15.     }

  • 时间复复杂度分析

    • 假设在n个元素的顺序表中，第i个元素为查找的元素x
    • 那么，比较的次数为i+1次，如果没有找到，则需要比较n次
    • 假设查找每个元素的概率相同，p= (1/n)
    • 所以，平均比较次数为 (1/n)*(i+1)求和 （0<=i<=n-1）
    • 时间复杂度为：O(n)
  1. SqList 完整源码

4. 链表的概念
  1. 定义：
  • 链接方式存储的线性表简称为链表（Linked List）。
  1. 存储结构定义：
  • 用一组任意的存储单元来存放线性表的结点
  • 链表中结点的逻辑次序和物理次序不一定相同
  • 每个结点由：数据域（存放数据信息）和指针域（存放直接后继节点地址）两部分组成

  • 注意：

    • 链式存储是最常用的存储方式之一
    • 它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构
  1. 链表的结点结构

数据结构基础学习之线性表 - 图1

  • data域—存放结点值的数据域
  • next域—存放结点的直接后继的地址（位置）的指针域（链域）

  • 注意：

    • 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
    • 每个结点只有一个链域的链表称为单链表（Single Linked List）。
  1. 单链表的表示

数据结构基础学习之线性表 - 图2

  • 头节点和头指针的区别
  1. 链表中的第一个节点的储存位置叫做头指针
  2. 链表中的第一个节点前预设的一个节点叫做头节点
  3. 头指针是链表必要元素
  4. 头节点不一定是链表的必要元素

数据结构基础学习之线性表 - 图3

5. 链表的实现及分析
  1. 结点类
  1. public class LNode<T> {
  2.     //数据域
  3.     public T data;
  4.     //指针域
  5.     public LNode<T> next;
  6.     //...略
  7. }
  1. 查找操作
  • 代码实现
  1. //按序号查找
  2.  public T get(int i) {
  3.         //获取第一个节点元素
  4.         LNode node = head.next;
  5.         //计数器
  6.         int pos = 0;
  7.         //遍历节点，直到节点为空 或者 指向第 i 个节点退出循环
  8.         while (node != null && pos < i) {
  9.             node = node.next; //指向后继节点
  10.             ++pos;//计数器加一
  11.         }
  12.         //判断是否找到节点
  13.         if (node == null || pos > i)
  14.             throw new RuntimeException("第 " + i + " 个元素不存在！");
  16.         return (T) node.data;
  17.     }
  20.   //按元素值查找
  21.    public int indexOf(T t) {
  22.           //获取第一个节点元素
  23.           LNode node = head.next;
  24.           //计数器
  25.           int pos = 0;
  27.           //判断查询的值是否为空
  28.           if (t == null) {
  29.               //遍历节点，直到节点为空 或者 节点的数据域为空，退出循环
  30.               while (node != null) {
  31.                   if (node.data == null) {
  32.                       return pos;
  33.                   }
  34.                   node = node.next; //指向后继节点
  35.                   ++pos;//计数器加一
  36.               }
  37.           } else {
  38.               //遍历节点，直到节点为空 或者 指向值为 t的 节点退出循环
  39.               while (node != null) {
  40.                   if (t.equals(node.data)) {
  41.                       return pos;
  42.                   }
  43.                   node = node.next; //指向后继节点
  44.                   ++pos;//计数器加一
  45.               }
  46.           }
  47.           return -1;
  48.       }
  • 时间复杂度：每次查找都是表头开始遍历查找，所以时间复杂度为：O(n)
  1. 插入操作

数据结构基础学习之线性表 - 图4

  • 代码实现
  1. //带头结点链表插入操作
  2.     public void insert(int i, T t) {
  3.             LNode p = head;
  4.             int pos = -1;
  5.             //1. 找到第 (i-1)个节点(位置 i 的前驱节点)
  6.             while (p.next != null && pos < i - 1) {
  7.                 p = p.next;
  8.                 pos++;
  9.             }
  10.             //判断插入位置的合法性
  11.             if (p == null || pos > i - 1)
  12.                 throw new RuntimeException("插入节点的位置不合法！");
  14.             //2. 创建一个新的节点
  15.             LNode newNode = new LNode(t);
  16.             //3.1 新节点的后继指针指向 原先第 i个节点
  17.             newNode.next = p.next;
  18.             //3.2  第（i-1）节点 p 的后继指针指向新节点
  19.             p.next = newNode;
  20.         }
  23.     //不带头结点
  24.     public void insert(int i, T t) {
  25.         LNode p = head;
  26.         int pos = 0;
  28.         while (p.next != null && pos < i - 1) {
  29.             p = p.next;
  30.             pos++;
  31.         }
  32.         //判断插入位置的合法性
  33.         if (p == null || pos > i)
  34.             throw new RuntimeException("插入节点的位置不合法！");
  36.         //2. 创建一个新的节点
  37.         LNode newNode = new LNode(t);
  38.         if(i==0){
  39.         //插入表头时
  40.             newNode.next = head;
  41.             head = newNode;
  42.         }else{
  43.              newNode.next = p.next;
  44.               p.next = newNode;
  45.         }
  46.     }
  • 时间复杂度：在第i个元素插入结点，需要找到第(i-1)个结点，时间复杂度：O(n)
  1. 删除操作

数据结构基础学习之线性表 - 图5

  • 代码实现
  1. public T remove(int i) {
  2.         LNode p = head;
  3.         int pos = -1;
  4.         //找到待删除节点的前驱节点
  5.         while (p.next != null && pos < i - 1) {
  6.             p = p.next;
  7.             ++pos;
  8.         }
  9.         if (pos > i - 1 || p == null)
  10.             throw new RuntimeException("删除节点的位置不合法！");
  11.         //待删除节点
  12.         LNode remove = p.next;
  13.         //3. 第 （i-1) 节点的指针指向 (i+1)节点
  14.         p.next = remove.next;
  15.         return (T) remove.data;
  16.     }
  • 时间复杂度：O(n)
  1. 单链表的创建
  • 示意图

数据结构基础学习之线性表 - 图6

  • 头插入法
  1. public void insertAtHead(T t) {
  2.         //构建新插入的节点
  3.         LNode newNode = new LNode(t);
  4.         //新节点的后继指针指向头结点的头指针
  5.         newNode.next = head.next;
  6.         //头指针指向新节点
  7.         head.next = newNode;
  8.     }

数据结构基础学习之线性表 - 图7

  • 尾插法
  1. public void insertTail(T t) {
  2.     //获取到最后的节点
  3.     LNode tail = this.head;
  4.     while (tail.next != null) {
  5.         tail = tail.next;
  6.     }
  7.     //构造新的节点
  8.     LNode newNode = new LNode(t);
  9.     //新节点指针指向 尾节点指针
  10.     newNode.next = tail.next;
  11.     //尾节点指针指向新节点
  12.     tail.next = newNode;
  13. }
  1. 单链表实现源码

6. 循环链表

数据结构基础学习之线性表 - 图8

  1. 实现循环链表的方式
  • 使用头指针的方式
  • 使用尾指针的方式
  • 使用头尾指针的方法
  1. 循环链表尾指针方式实现源码

7. 双向链表

数据结构基础学习之线性表 - 图9

  1. 结点类
  1. public class DuLNode<E> {
  2.     public E data;//数据域
  3.     public DuLNode<E> prior;//前驱指针
  4.     public DuLNode<E> next;//后驱指针
  5.     public DuLNode() {
  6.         this(null);
  7.     }
  8.     public DuLNode(E data) {
  9.         this.data = data;
  10.         this.prior = null;
  11.         this.next = null;
  12.     }
  13. }
  1. 插入操作
    数据结构基础学习之线性表 - 图10
  1. public void insert(int i, E t) {
  2.         //先判断索引是否合法
  3.         if (i < 0 || i > length)
  4.             throw new RuntimeException("插入元素的位置不合法！ i=" + i);
  5.         DuLNode<E> p = head;
  6.         //下标
  7.         int index = -1;
  8.         //找到第i个元素
  9.         while (p.next != null && index < i) {
  10.             index++;
  11.             p = p.next;
  12.         }
  13.         //创建一个新的结点
  14.         DuLNode<E> newNode = new DuLNode<>(t);
  15.         if (i == 0 || i == length) {
  16.             newNode.prior = p;
  17.             p.next = newNode;
  18.         } else {
  19.             //1. 第i个结点p的前驱结点的后继指向新结点
  20.             p.prior.next = newNode;
  21.             //2. 新结点的前驱指向第(i-1)个结点
  22.             newNode.prior = p.prior;
  23.             //3. 新结点的后驱指向第i个结点p
  24.             newNode.next = p;
  25.             //4. 第i个结点p的前驱指向新结点
  26.             p.prior = newNode;
  27.         }
  28.         //长度加一
  29.         length++;
  30.     }
  1. 删除操作
    数据结构基础学习之线性表 - 图11
  1. public E remove(int i) {
  3.         //先判断索引是否合法
  4.         if (i < 0 || i > length - 1)
  5.             throw new RuntimeException("删除元素不存在！ i=" + i);
  7.         DuLNode<E> p = head;
  8.         //下标
  9.         int index = -1;
  10.         //找到第i个元素
  11.         while (p.next != null && index < i) {
  12.             index++;
  13.             p = p.next;
  14.         }
  16.         DuLNode<E> remove = p;
  18.         //1. 第（i-1）个结点的后驱指向 第 （i+1）个结点
  19.         p.prior.next = p.next;
  20.         //2. 第 （i+1）个结点的前驱指向 第（i-1）个结点
  21.         p.next.prior = p.prior;
  23.         //长度减一
  24.         length--;
  25.         return remove.data;
  26.     }
  1. 双向链表完整源码

8. 链表与顺序表的比较

  • 基于空间考虑

    • 分配方式

      • 顺序表：静态分配。
      • 链表：动态分配。
      • 难以估计其存储规模时，以采用动态链表作为存储结构为好。

    • 存储密度

      • 顺序表：=1
      • 链表：<1
      • 为了节约存储空间，宜采用顺序表作为存储结构。
      • 存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）

  • 基于时间考虑

    • 存取方法

      • 顺序表： 随机存储结构，时间复杂度O(1);
      • 链表：顺序存取结构，时间复杂度O(n)
      • 操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜

    • 插入删除操作

      • 在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。
      • 在链表中的任何位置上进行插入和删除，都只需要修改指针。