线性表（List）

定义：是零个或者多个数据元素的有限序列。
线性表首先是一个序列，其内部的元素都是有序的，然后是一个有限的序列。例如十二星座，是有序的，有限的，所以它是一个List。
位序：线性表中元素在其中的位置。

• 顺序存储结构

定义：是指用一段地址连续的存储单元依次存储线性表的数据元素。
例如在图书馆替室友占座，一般都是占连续的一排座位，这个就是顺序存储结构。

描述线性表的三个属性

存储空间的起始位置
线性表的最大存储容量
线性表的当前长度

数组长度与线性表长度的区别
数组长度是存放线性表的存储空间的长度，一般来说是不变的。
线性表长度是线性表中数据元素的个数，是可变的。
读取的时间复杂度
只要知道数组中第一个元素的存储位置，后面的元素都可以使用N = A + (n - a) * dx来得到，其中大写字母为元素的物理存储位置，小写字母为 元素在数组中的位置。因此不管n如何变化，只需要一步就能够实现读取的操作，其时间复杂度为O（1）。

• 顺序结构的插入和删除

步骤：

1. 将插入位置以及其后的元素都往后移一位
2. 将要插入的元素放到插入位置上

Java实现

public class insert {

    static int[] test_1; //原始的数组

    /**
     *对原始的数组进行初始化
     */
    private static int[] getTest() {
        test_1 = new int[10];
        for (int i = 0; i < test_1.length; i++) {
            test_1[i] = i;
        }
        return test_1;
    }

    public static int[] insertTest(int s, int[] test, int num) {
        int[] test_2 = new int[test.length + 1];
        for (int i = 0; i < s-1; i++) {
            test_2[i] = test[i];
        }
        for (int i = s-1; i < test.length; i++) {
            test_2[i+1] = test[i];
        }
        test_2[s-1] = num;
        return test_2;
    }

    public static int[] deleteTest(int s, int[] test) {
        int[] test_3 = new int[test.length - 1];
        for (int i = 0; i < s-1; i++) {
            test_3[i] = test[i];
        }
        for (int i = s; i < test.length; i++) {
            test_3[i - 1] = test[i];
        }
        return test_3;
    }

    public static void main(String[] args) {

        int[] test = getTest();
        int[] results = insertTest(3, test, 2);
        for (int i = 0; i < results.length; i++) {
            System.out.println(results[i]);
        }
        int[] results1 = deleteTest(4, test);
        for (int i = 0; i < results1.length; i++) {
            System.out.print(results1[i]);
        }
    }
}

由代码可知，线性表顺序存储的增加与删除的时间复杂度都是O（n）。

顺序存储结构的优点：

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
• 可以快速地存取表中任一位置的元素
  顺序存储结构的缺点
• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量。
• 造成存储空间的碎片。

线性表的链式存储结构

特点：用一组任意的存储单元存储线性表的数据元素，这组数据元素单元可以是连续的，也可以是不连续的，这就意味着在每个元素的存储内容中必须要由下一个元素的位置信息，因为这还是一个线性表，需要有序，有限。这样就能够利用大量碎片空间来存储信息。

在链式储存中，每一个数据元素由两个数据项组成，一个储存数据元素本身的信息，叫做数据域，一个储存着下一个数据元素的位置信息，叫做指针域。指针域中存储的信息叫做指针或者链。这两部分组成数据元素的存储映像，成为结点（Node）。
头指针：链表中第一个结点的存储位置为头指针。
头节点：为了便于操作，在单链表的第一个结点之前附设一个结点，成为头结点。头结点的数据域可以不存储信息，头结点的指针域指向第一个结点的位置。

头指针与头结点的异同

• 头指针
  1. 头指针是指链表指向第一个结点的指针，如果链表有头结点，则是指向头结点的指针。
  2. 头指针具有标志作用，所以常用头指针冠以链表的名字。
  3. 无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
• 头结点
  1. 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般没有意义。
  2. 有了头结点，在对第一个结点进行插入和删除操作就和其他结点的操作一致了。
  3. 头结点不一定是链表的必要组成部分。

单链表的读取

算法思路：

• 声明一个指针P指向链表的第一个结点，初始化j从1开始
• 当j < i的时候，遍历链表，让p的指针向后移动，不断指向下一个结点，j++
• 如果到链表末尾的时候p为空，则说明第i个结点不存在，查找失败
• 否则查找成功，返回结点P的数据

Java实现

public class Model {

    private Object o;
    private Model m;

    Model(Object o, Model m) {
        super();
        this.o = o;
        this.m = m;
    }

    public Object getO() {
        return o;
    }

    public void setO(Object o) {
        this.o = o;
    }

    public Model getM() {
        return m;
    }

    public void setM(Model m) {
        this.m = m;
    }
}

package com.company;

public class SingleLinkedList {

    private Model start;
    private Model current;
    private int size;

    //获取一个空的单链表
    private SingleLinkedList() {
        start = current = new Model(null, null);
        size = 0;
    }

    //判断该单链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //获取该单链表的大小
    public int getSize() {
        return size;
    }

    //读取单链表
    public Model getModel(int i) {
        current = start.getM();
        int j = 1;
        while (!this.isEmpty() && j<i) {
            current = current.getM();
            j++;
        }
        return current;
    }

    //在单链表的最后添加
    public void addToLast(Object o) {
        //因为是在单链表的最后添加的，所以其指针域为null
        Model newModel = new Model(o, null);
        //到达单链表的最后
        while (current.getM() != null) {
            current = current.getM();
        }
        current.setM(newModel);
        size++;
    }

    //在单链表的开始添加
    public void addToStart(Object o) {
        Model startModel = start.getM();
        Model newModel = new Model(o, startModel);
        start.setM(newModel);
        size++;
    }

    //在单链表的中间某处添加
    public void add(int i, Object o) {
        if (i == 1) {
            addToStart(o);
        }
        //获取要被往后推的model
        Model after = getModel(i);
        //获取要被添加处之前的model
        Model before = getModel(i-1);
        //创建新的model，并与后面的model连接起来
        Model newModel = new Model(o, after);
        //与之前的model连接起来
        before.setM(newModel);
        size++;
    }

    public void deleteFirst() {
        Model first = start.getM();
        Model next = first.getM();
        start.setM(next);
    }

    //在链表中某处删除
    public void delete(int i) {
        if (getSize() == 0) {
            System.out.println("链表为空不能删除");
            return;
        }
        if (i == 1) {
            deleteFirst();
        } else {
            //获取要被删除的model
            Model deletedModel = getModel(i);
            //获取被删除model前一位置的model
            Model before = getModel(i - 1);
            //获取被删除model之后的model
            Model after = deletedModel.getM();
            before.setM(after);
        }
    }

    public void printAll() {
        if (isEmpty()) {
            System.out.println("链表为空");
        } else {
            for (current = start.getM(); current != null; current = current.getM()) {
                System.out.print("[" + current.getO().toString() + "]" + " ");
            }
        }
    }

    public static void main(java.lang.String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        for (int i = 1; i < 8; i++) {
            linkedList.addToLast(i);
        }
        linkedList.printAll();
        System.out.println("初始化完成");
        java.lang.String result = linkedList.getModel(1).getO().toString();
        System.out.println(result);
        linkedList.add(3, 12);
        linkedList.printAll();
        linkedList.delete(4);
        System.out.println("删除线性表中第四位");
        linkedList.printAll();
    }
}

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

• 存储分配方式
  1. 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  2. 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
• 时间性能
  1. 查找：顺序存储结构为O(1)，单链表为O(n)
  2. 插入与删除：顺序存储结构需要平均移动表长一半的元素，时间为O(n)，单链表只是在查找第一个位置的指针是时间为O(n)，后面进行的增加删除都为O(1)
• 空间性能
  1. 顺序存储结构需要时间进行空间分配，分大了的话就会浪费空间，分小了的话就会出现上溢现象
  2. 单链表不需要是预先进行空间分配，只要有剩余空间就可以使用，元素个数也不受限制

结论

• 如果线性表需要经常进行插入删除等操作，例如游戏中买卖商品导致数据的变化，单链表存储结构就更适合。如果是涉及到大量的读取操作，例如用户在登陆游戏时，服务器进行的信息验证，顺序存储结构就更适合一点。
• 如果线性表中的元素数量过大，或者不知道元素数量，单链表结构较为适合。因为这样可以有效利用存储空间，而且可以改变元素的数量。如果元素数量较小，或者知道元素数量，顺序存储结构更好。

循环链表

定义：将单链表中终端终点的指针端由空指针改为指向头结点，单链表就会变成一个头尾相接的循环链表（circular linked list）
头结点不是循环链表的必须组成成分，如果没有头结点，那链表中终端终点的指针变成头指针就行了。

循环链表与单链表的主要区别在于循环的判断条件上，原来是判断结点的指针域是否为null，现在是结点的指针域是否指向头结点或者第一个结点。

双向链表

定义：在单链表的每一个结点中，都保存着指向上一个结点的指针域。