数据结构-线性表

如有错误，望不吝斧正！

文章目录

• 线性表
• • 抽象数据类型
  • 顺序存储结构
  • • 查询
    • 增加
    • 插入和删除
    • 优缺点
  • 链式存储结构
  • • 单链表
    • • 读取
      • 插入与删除
      • 单链表结构与顺序存储结构优缺点
      • • 存储分配方式
        • 时间性能
        • 空间性能
    • 循环链表
    • 双向链表

线性表

线性表是零个或多个具有相同类型的数据元素的有限序列。

抽象数据类型

• ADT 线性表
• Data 线性表的数据对象集合为{a₁ ,a₂,.……,aₙ），每个元素的类型均为DataType。其中，除第一个元素a₁外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
• Operation

  //参考java的list
  public construct();	//初始化操作，建立一个线性表
  boolean isEmpty();	//判断线性表是否为空
  void clear();	//清空线性表
  E get(int index);	//获取下标为index的元素
  boolean contains(Object o); //如果线性表包含指定的元素，返回true
  void add(int index, E element); //在指定位置插入指定元素
  E remove(int index); //移除指定位置的元素并返回
  int size();	//返回这个线性表中元素的个数
             

endADT

顺序存储结构

使用一段地址连续的存储单元依次存储线性表的数据元素，通常使用数组来实现。

具体实现可参考ArrayList！

实现顺序存储结构：

• 存储空间的起始位置：数组elementData，它的存储位置就是存储空间的起始位置
• 线性表的最大存储容量：数组长度DEFAULT_CAPACITY
• 线性表的当前长度：size

伪代码如下：

public class ArrayList{
	//线性表默认容量大小
	private static final int DEFAULT_CAPACITY = 10;
	//线性表的当前长度
	private int size;
	//存储数据元素的数组
	Object[] elementData=new Object[DEFAULT_CAPACITY];
}
           

查询

//java中ArrayList中查询元素的主要方法，可知时间复杂度是O(1)
E elementData(int index) {
    return (E) elementData[index];
}
           

增加

附加指定元素到线性表的后面

//时间复杂度为O(1)
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
           

插入和删除

在这个线性表中在指定的位置插入指定的元素

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
           

删除方法与插入方法类似，都是通过System.arraycopy方法来实现。本人对System.arraycopy方法不是很了解，看了一些资料和源码，也没看出个所以然来。但看到有文章分析时间复杂度是O(n)。

总结：读取和增加的时间复杂度是O(1)，插入和删除的时间复杂度是O(n)。说明，它比较适合元素个数不太变化，而更多是存取数据的应用。

优缺点

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

链式存储结构

Java虽然没有指针，但是启用了对象引用机制，与指针的作用类似。

链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

为了表示每个数据元素aᵢ与其直接后继数据元素aᵢ-₁之间的逻辑关系，对数据元素aᵢ来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素aᵢ的存储映像，称为结点（Node)。

单链表

每个结点中只包含一个指针域，所以叫做单链表。

单链表的数据结构：

private static class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}
           

链表中第一个结点的存储位置叫做头指针，最后一个节点的指针为空，通常用“null”或“^”表示。

有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

若线性表为空表，则头节点的指针域为空。

头结点与头指针的区别：

头指针：

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
• 头结点不一定是链表必须要素

读取

单链表的读取，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需遍历，第一个就取出数据了，而当i=n 时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。

可以参考Java的LinkedList的get方法，虽然它的实现是双向链表，但是类似。

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
           

插入与删除

如果一个队列是：A->B->C->D ，需要在B和C之间插入E，1.循环遍历线性表先找到元素B，2.将B的后继指针赋值给E的后继指针，3.将B的后继指针指向E。

删除与之类似，也是循环找到要删除的元素，然后将它的后继指针赋值给它前一个元素的后继指针，最后释放它。

从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

单链表结构与顺序存储结构优缺点

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

• 查找
  • 顺序存储结构O(1)
  • 单链表O(n)
• 插入和删除
  • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
  • 单链表在线出某位置的指针后，插入和删除时间仅为O(1)

空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

增加和读取多，插入和删除少，推荐使用顺序存储结构

插入和删除少，推荐使用链表结构

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linkedlist)。

从当中一个结点出发，可以访问到链表的全部结点。

可以用于模拟类似约瑟夫环的问题。

双向链表

双向链表（double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

Java的LinkedList就是使用的双向链表结构。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
           

本文参考《大话数据结构》

https://zhuanlan.zhihu.com/p/28016098