第一节 线性表的定义

1 逻辑结构

线性表是具有n(n≥0)个相同数据类型的元素的有限序列。其中n为表长，当n=0时，该线性表是一个空表。

若用L命名线性表，则其一般表示为：

L = (a1, a2, ……, ai, ai+1, ……, an)

其中，a1是表头元素，an是表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

2 存储结构

线性表的存储结构主要可以分为顺序存储和链式存储。

顺序存储的线性表又称为顺序表，它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

链式存储的线性表又称为链表，它不需要使用地址连续的存储单元，不要求逻辑上相邻的两个元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系。

3 基本操作

对线性表的基本操作如下：

1、初始化表：构造一个空的线性表。

2、求表长：返回线性表的长度，即线性表中数据元素的个数。

3、按位查找：获取线性表中第i个位置的元素的值。

4、按值查找：获取线性表中某个值的元素的位置。

5、插入操作：在线性表的第i个位置插入指定元素。

6、删除操作：删除线性表中第i个位置的元素。

7、更新操作：修改线性表中第i个位置的元素的值。

8、判空操作：判断线性表是否为空。

9、输出操作：按照前后顺序输出线性表中所有元素的值。

10、销毁操作：销毁线性表，释放线性表所占的内存空间。

第二节 顺序表

1 定义

存储结构为顺序存储的线性表称为顺序表。

它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

顺序表的特点如下：

1、随机访问，通过首地址和元素序号可在时间O(1)内找到指定的元素；

2、存储密度高，每个节点只存储数据元素；

3、逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素，开销大。

2 实现

顺序表使用数组实现。

我们定义一个MyArrayList类，用来表示顺序表。

定义属性：data[]，maxSize，length。其中data[]用于存放元素；maxSize用于记录当前使用的数组的长度，便于对数组进行动态分配；length用于记录当前顺序表中的元素的个数。

定义方法：初始化、插入、删除等操作。

public class MyArrayList<T> {
    private T[] data;   // data数组用于存放数据元素
    private int maxSize;   // maxSize用于表示数组的大小
    private int length; // length用于表示数据元素的个数

    /**
     * 初始化顺序表
     */
    public MyArrayList() {
        this.maxSize = 10;   // 默认maxSize为10
        this.data = (T[]) new Object[this.maxSize];
    }

    /**
     * 顺序表中数据元素是否为空
     * @return
     */
    public boolean isEmpty() {
        return length == 0;
    }

    /**
     * 在顺序表的第index个位置插入新元素data。
     * @param data
     * @param index
     * @return
     */
    public boolean insert(T data, int index) {
        this.resize();
        if (index < 0 || index > this.length) {
            return false;
        } else {
            if (this.length == 0) {
                this.data[0] = data;
            } else {
                for (int i = this.length - 1; i >= index; i--) {
                    this.data[i + 1] = this.data[i];
                }
                this.data[index] = data;
            }
            this.length++;
            return true;
        }
    }

    /**
     * 删除顺序表中第index个位置的元素。
     * @param index
     * @return
     */
    public boolean delete(int index) {
        this.resize();
        if (isEmpty()) {
            return false;
        }
        if (index < 0 || index >= this.length) {
            return false;
        } else {
            for (int i = index; i < this.length; i++) {
                this.data[i] = this.data[i + 1];
            }
            this.data[this.length - 1] = null;
            this.length--;
            return true;
        }
    }

    /**
     * 动态改变数组大小
     */
    private void resize() {
        T[] temp = null;
        if (this.length >= this.maxSize) {
            this.maxSize = this.length + 10;
            temp = (T[]) new Object[this.maxSize];
            for (int i = 0; i < this.length; i++) {
                temp[i] = this.data[i];
            }
            this.data = temp;
        } else if (this.length < this.maxSize - 10) {
            this.maxSize = this.length - 10;
            temp = (T[]) new Object[this.maxSize];
            for (int i = 0; i < this.length; i++) {
                temp[i] = this.data[i];
            }
            this.data = temp;
            temp = null;
        }
    }
}

第三节 链表

1 定义

存储结构为链式存储的线性表又称为链表。

链表不要求逻辑上相邻的两个元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此对线性表的插入、删除不需要移动元素，而只需要修改指针。

按照实现方式及功能的不同，链表可分为：单链表、双链表、循环链表和静态链表等。

2 单链表

单链表结点中只有一个指向其后继结点的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

public class MyLinkedList<T> {
    private Node<T> first; // 头节点
    private int length; // 链表长度

    /**
     * 初始化链表
     */
    public MyLinkedList() {
        this.first = new Node<>();
        this.length = 0;
    }

    /**
     * 将node插入到第index位置上
     * @param data
     * @param index
     * @return
     */
    public boolean insert(T data, int index) {
        if (index < 0 || index > length) {  // 判断index是否合法
            return false;
        } else {
            Node<T> node = new Node<>(data);
            Node<T> cur = this.first;
            int count = 0;
            while (count < index) {
                cur = cur.next;
                count++;
            }
            node.next = cur.next;
            cur.next = node;
            length++;
            return true;
        }
    }

    /**
     * 删除第i个节点
     * @param index
     * @return
     */
    public boolean delete(int index) {
        if (index < 0 || index > length) {  // 判断index是否合法
            return false;
        } else {
            Node<T> cur = this.first;
            int count = 0;
            while (count < index) {
                cur = cur.next;
                count++;
            }
            cur.next = cur.next.next;
            length--;
            return true;
        }
    }

    /**
     * 求表长
     * @return
     */
    public int getLength() {
        return this.length;
    }

    /**
     * 获取第index个节点的值
     * @param index
     * @return
     */
    public T getNode(int index) {
        if (this.length == 0) {
            System.out.println("链表为空。");
        }
        if (index < 0 || index > length) {  // 判断index是否合法
            return null;
        } else {
            Node<T> cur = this.first;
            int count = 0;
            while (count <= index) {
                cur = cur.next;
                count++;
            }
            return cur.data;
        }
    }


    /**
     * 遍历链表
     */
    public void print() {
        Node<T> cur = this.first.next;
        if (this.length == 0) {
            System.out.println("链表为空。");
        }
        while (cur != null) {
            System.out.println(cur.data);
            cur = cur.next;
        }
    }

    /**
     * 定义链表的元素节点
     */
    private class Node<T> {
        private T data;         // 数据
        private Node next;      // 指针
        public Node() {}
        public Node(T data) {
            this.data = data;
        }
    }
}

3 双链表

双链表仅在单链表的结点中增加了一个指向其前驱的prior指针，因此在双链表中执行按值查找和按位查找的操作与在单链表中的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对prior指针作出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为O(1)。

public class MyDLinkedList<T> {
    private DNode<T> head; // 头节点
    private int length; // 双链表长度

    /**
     * 初始化双链表：
     *      this.head.data = null
     *      this.head.prior = null
     *      this.head.next = null
     *      this.length = 0
     */
    public MyDLinkedList() {
        this.head = new DNode<T>();
    }

    /**
     * 双链表是否为空：若为空，返回true；否则返回false。
     * @return
     */
    public boolean isEmpty() {
        return this.length == 0;
    }

    /**
     * 将数据包装成节点，并插入到双链表的第index位置。
     * 若插入成功，返回true；否则返回false。
     * @param data
     * @param index
     * @return
     */
    public boolean insert(T data, int index) {
        // 第一种情况：index不合法
        if (index < 0 || index > this.length) {
            throw new RuntimeException("index不合法");
        }

        DNode<T> insNode = new DNode<>(data);    // 声明并初始化待插入节点
        int count = 0;  // 计数器
        DNode<T> cur = this.head;   // 遍历器
        boolean flag = false;

        // 第二种情况：在末尾添加数据
        if (index == this.length) {
            while (cur.next != null) {   // 将cur移动到双链表末尾
                cur = cur.next;
            }
            insNode.prior = cur;    // 将insNode的prior指向cur
            cur.next = insNode;     // 将cur的next指向insNode
            this.length++;  // length+1
            flag = true;
        } else {  // 第三种情况：如果插入位置不是最后一个位置
            while (count < index) { // 将cur移动到待插入位置的前一个位置
                cur = cur.next;
                count++;
            }
            insNode.next = cur.next;    // 将insNode的next指向cur的下一个节点
            cur.next.prior = insNode;   // 将下一个节点的prior指向insNode
            insNode.prior = cur;        // 将insNode的prior指向cur
            cur.next = insNode;         // 将cur的next指向insNode
            // length+1
            this.length++;
            flag = true;
        }
        return flag;
    }

    /**
     * 删除第index个节点。
     * 若删除成功，返回true；否则返回false。
     * @param index
     * @return
     */
    public boolean del(int index) {
        if (this.isEmpty()) {   // 第一种情况：如果双链表为空，不能进行删除操作
            throw new RuntimeException("双链表为空");
        } else {
            int count = 0;  // 计数器
            DNode<T> cur = this.head;   // 遍历器
            DNode<T> next = this.head.next;   // 遍历器
            boolean flag = false;
            if (index < 0 || index >= this.length) { // 第二种情况：index不合法
                throw new RuntimeException("index不合法");
            } else if (index == this.length - 1) {  // 第三种情况：删除最后一个节点
                while (cur.next != null) {   // 将cur移动到最后一个位置
                    cur = cur.next;
                }
                // 删除
                cur.prior.next = null;
                cur = null;
                // length-1
                this.length--;
                flag = true;
            } else {    // 第四种情况：删除的不是最后一个节点
                while (count < index) { // 将cur移动到待插入位置的前一个位置
                    cur = next;
                    next = next.next;
                    count++;
                }
                // 删除
                next.next.prior = cur;
                cur.next = next.next;
                next = null;
                // length-1
                this.length--;
                flag = true;
            }
            return flag;
        }
    }

    /**
     * 打印双链表数据
     */
    public void print() {
        DNode<T> cur = this.head;   // 遍历器
        while (cur.next != null) {
            cur = cur.next;
            System.out.println(cur.data);
        }
    }

    /**
     * 双链表节点
     * @param <T>
     */
    private class DNode<T> {
        private T data;
        private DNode prior;
        private DNode next;

        public DNode() {
        }

        public DNode(T data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        MyDLinkedList<String> list = new MyDLinkedList<>();
        list.insert("a", 0);
        list.insert("b", 0);
        list.insert("c", 0);
        list.insert("d", 3);
        list.print();
        System.out.println("==========");
        list.del(0);
        list.del(2);
        list.print();
    }
}

第四节 顺序表与链表的比较

1 存取方式

顺序表：可以顺序存取，也可以随机存取。

链表：只能从表头顺序存取。

2 逻辑结构与物理结构

顺序表：逻辑上相邻的元素，其对应的物理存储位置也相邻。

链表：逻辑上相邻的元素，其物理存储位置不一定相邻，其对应的逻辑关系是通过指针链接来表示的。

3 查找、插入和删除操作

按值查找：顺序表无序时，两者的时间复杂度均为O(n)；顺序表有序时，可采用二分查找，此时的时间复杂度为O(log2n)。

按序号查找：顺序表支持随机访问，时间复杂度仅为O(1)；链表的平均时间复杂度为O(n)。

插入和删除操作：顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需修改相关节点的指针域即可。

4 空间分配

顺序表

在静态存储分配的情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。

链表

链式存储的节点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。但由于链表的每个节点都带有指针域，因而在存储空间上要比顺序存储付出的代价大，而存储密度不够大。