1 线性表简介

1. 线性表是最基本、最简单、也是最常用的一种数据结构，一个线性表是若干个具有相同特性的数据元素的有限序列；
2. 数据元素之间具有一种“一对一”的逻辑关系；
3. 前驱元素：若A元素在B元素的前面，则称A为B的前驱元素；
4. 后继元素：若B元素在A元素的后面，则称B为A的后继元素；
5. 第一个数据元素没有前驱，这个数据元素被称为头结点；
6. 最后一个数据元素没有后继，这个数据元素被称为尾结点；
7. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继；

2 线性表分类

线性表数据存储的方式有两种：顺序存储和链式存储；

1. 顺序存储：指用一组连续的存储单元存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素在物理存储单元中也是相邻的；
2. 链式存储：指用一组任意的存储单元存储线性表的数据元素，线性表中在逻辑结构上相邻的数据元素在物理存储单元中不一定是相邻的；

按照线性表数据存储方式的不同，可以把线性表分为顺序表（顺序存储）和链表（链式存储）。

3 顺序表

顺序表是在计算机内存中以数组的形式顺序存储的线性表。

3.1 API设计

3.1 Java代码

public class SequenceList<T> implements Iterable<T>{
    //定义数组用来存储元素
    private T[] eles;
    //记录顺序表长度
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //数组初始化容量大小为capacity
        this.eles=(T[])new Object[capacity];
        //线性表长度初始化为0
        this.N=0;
    }

    //将线性表置为空
    public void clear(){
        this.N=0;
    }

    //判断线性表是否为空
    public boolean isEmpty(){
       return N==0;
    }

    //获取线性表长度
    public int length(){
        return N;
    }

    //获取索引i处的元素
    public T get(int i){
        if (i<0 || i>=N){
            throw new RuntimeException("当前元素不存在！");
        }
        return eles[i];
    }

    //向线性表中添加元素t
    public void insert(T t){
        //元素已经放满了数组，需要扩容
        if (N==eles.length){
            resize(2*eles.length);
        }

        eles[N++]=t;
    }

    //向i索引处插入元素t
    public void insert(int i,T t){
        if (i<0 || i>N) {
            throw new RuntimeException("插入的位置不合法");
        }
        //元素已经放满了数组，需要扩容
        if (N==eles.length){
            resize(2*eles.length);
        }
        //先把i索引处的元素及其后面的元素依次向后移动一位
        for(int index=N;index>i;index--){
            eles[index]=eles[index-1];
        }
        //再把t元素放到i索引处即可
        eles[i]=t;
        //线性表长度+1
        N++;
    }

    //删除指定索引i处的元素，并返回该元素
    public T remove(int i){
        if (i<0 || i>N-1) {
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //记录索引i处的值
        T current = eles[i];
        //索引i后面元素依次向前移动一位即可
        for(int index = i;index < N-1;index++){
            eles[index] = eles[index+1];
        }
        //元素个数-1
        N--;

        //线性表长度已经不足线性表容量的1/4,减容
        if (N<eles.length/4){
            resize(eles.length/2);
        }

        return current;
    }

    //查找t元素第一次出现的位置
    public int indexOf(T t){
        if(t==null) {
            throw new RuntimeException("查找的元素不合法");
        }
        for(int i=0;i<N;i++){
            if (eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }

    //改变容量
    public void resize(int newSize){
        //记录旧数组
        T[] temp=eles;
        //创建新数组
        eles=(T[])new Object[newSize];
        //把旧数组的数据复制到新数组
        for(int i=0;i<N;i++){
            eles[i]=temp[i];
        }
    }
    //获得线性表的容量
    public int capacity() {
        return eles.length;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator{
        private int cusor;
        @Override
        public boolean hasNext() {
            return cusor<N;
        }
        @Override
        public Object next() {
            return eles[cusor++];
        }
    }
}

public class Test {
    public static void main(String[] args) {
        SequenceList<Integer> list = new SequenceList<>(4);
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        System.out.print(list.length() + "\t");System.out.println(list.capacity());
        list.insert(5);
        System.out.print(list.length() + "\t");System.out.println(list.capacity());
        for(Integer i : list) {
            System.out.print(i + " ");
        }
        list.clear();
        for(Integer i : list) {
            System.out.print(i + " ");
        }
    }
}

4	4
5	8
1 2 3 4 5 

3.3 复杂性分析

1. get(int i)：不论顺序表长度N有多大，只要一次eles[i]即可获取对应元素，所以时间复杂度为O(1)；
2. insert(int i,T t)：每一次插入，都需要把i及i后面的元素后移一次，随着N的增大，移动元素也越多，所以时间复杂度为O(N);
3. remove(int i)：每一次删除，都需要把i后面的元素前移一次，随着N的增大，移动元素也越多，所以时间复杂度为O(N);
4. 由于顺序表的底层由数组实现，数组长度是固定的，因此会涉及容器扩容的操作，这就导致顺序表在使用中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其元素越多，这个问题越明显；

注：

• java中的ArrayList集合的底层就是一种顺序表，底层使用数组实现，也提供了增删改查以及扩容等功能。

4 链表

1. 链表是在计算机内存中以结点的形式链式存储的线性表，在物理存储单元上非连续、非顺序；
2. 链表由一系列结点组成，结点可以在运行时动态生成；

4.1 单向链表

4.1.1 简介

1. 单向链表是链表的一种，由多个结点组成，每个结点由一个数据域和一个指针域构成，数据域用来存储数据，指针域用来指向其后继结点；
2. 头结点不存储数据，指针域指向第一个真正存储数据的结点；

4.1.2 Java代码

public class LinkList<T> implements Iterable<T>{
    //记录头结点
    private Node head;
    //记录链表的长度
    private int N;

    public LinkList() {
        //初始化头结点
        this.head = new Node(null,null);
        //初始化元素个数
        this.N = 0;
    }
    
 	//向链表中添加元素t
    public void insert(T t) {
        //找到当前最后一个结点
        Node pre = head;
        while(pre.next!=null){
            pre=pre.next;
        }
        //让当前最后一个结点指向新结点
        pre.next = new Node(t, null);
        //元素的个数+1
        N++;
    }
    //向指定位置i处，添加元素t
    public void insert(int i, T t) {
    	if (i<0 || i>=N) {
			throw new RuntimeException("位置不合法！");
		}
        //找到i位置前一个结点
        Node pre = head;
        for(int index=0;index<i;index++){
            pre = pre.next;
        }
        //新节点指向i位置节点称为i节点，原来i位置的前一个节点指向新结点
        pre.next=new Node(t, pre.next);
        //元素的个数+1
        N++;
    }
    
	//删除指定位置i处的元素，并返回被删除的元素
    public T remove(int i) {
       	if (i<0 || i>=N) {
			throw new RuntimeException("位置不合法！");
		}
        //找到i位置的前一个节点
        Node pre = head;
        for(int index=0;index<i;index++){
            pre=pre.next;
        }
        //要找到i位置的结点
        Node curr = pre.next;
        //前一个结点指向下一个结点
        pre.next = curr.next;
        //元素个数-1
        N--;
        return curr.item;
    }
    //清空链表
    public void clear() {
        head.next = null;
        N = 0;
    }

	//获取指定位置i处的元素
    public T get(int i) {
        if (i<0 || i>=N) {
			throw new RuntimeException("位置不合法！");
		}
        //通过循环,从头结点开始往后找，依次找i次，就可以找到对应的元素
        Node curr = head;
        for(int index=0;index<=i;index++){
            curr=curr.next;
        }
        return curr.item;
    }
    //查找元素t在链表中第一次出现的位置
    public int indexOf(T t) {
        //从头结点开始，依次找到每一个结点，取出item，和t比较，如果相同，就找到了
        Node pre = head;
        int index = 0;
        while(pre.next!=null) {
            if(pre.next.item.equals(t)) {
                return index;
            }
            pre = pre.next;
            index++;
        }
        return -1;
    }
    //获取链表的长度
    public int length() {
        return N;
    }
    //判断链表是否为空
    public boolean isEmpty() {
        return N == 0;
    }
    
    // 设计迭代器
    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n=head;
        }

        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }

	//结点类
    private class Node {
        //存储数据
        T item;
        //下一个结点
        Node next;
        
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

public class Test {
    public static void main(String[] args) {
        LinkList<Integer> list = new LinkList<>();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);

        for(Integer i : list) {
            System.out.print(i + " ");
        }
    }
}

1 2 3 4 

4.2 双向链表

4.2.1 简介

1. 双向链表是链表的一种，由多个结点组成，每个结点由一个数据域和两个指针域构成；
2. 数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向其前驱结点；
3. 链表头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点；

4.2.2 Java代码

public class TwoWayLinkList<T> implements Iterable<T> {
    //头结点
    private Node head;
    //最后一个结点
    private Node last;
    //链表长度
    private int N;

    //结点类
    private class Node{
        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }

        //存储数据
        public T item;
        //指向上一个结点
        public Node pre;
        //指向下一个结点
        public Node next;
    }

    public TwoWayLinkList() {
        //初始化头结点和尾结点
        head = new Node(null,null,null);
        last=null;
        //初始化元素个数
        N=0;
    }

    //清空链表
    public void clear(){
        head.next=null;
        head.pre=null;
        head.item=null;
        last=null;
        N=0;
    }

    //获取链表长度
    public int length(){
        return N;
    }

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

    //获取第一个元素
    public T getFirst(){
        if (isEmpty()){
            return null;
        }
        return head.next.item;
    }

    //获取最后一个元素
    public T getLast(){
        if (isEmpty()){
            return null;
        }
        return last.item;
    }

    //插入元素t
    public void insert(T t){
        if (isEmpty()){
            //如果链表为空，创建新的结点，并让新结点成为尾结点
            last = new Node(t, head, null);
            //让头结点指向尾结点
            head.next = last;
        }else {//如果链表不为空
            //让尾结点成为旧的尾结点
            Node oldLast = last;
            //创建新的尾结点
            Node newLast = new Node(t, oldLast, null)