一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
采用顺序表的形式，可以写到类里面，将来就可以面向对象了。

顺序表一般可以分为:

静态顺序表:使用定长数组存储。
动态顺序表:使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，相比之下动态顺序表更灵活, 根据需要动态的分配空间大小。

应用示例：实现一个动态顺序表
定义一个MyArrayList类，里面的成员变量有两个：elem、usedSize，还有一个构造方法，并在构造方法里面定义一个长度为10的数组。并在测试类中new一个MyArrayList对象。此时其底层结构如下图所示：

栈里面存放的MyArrayList引用指向堆里面的对象elem、usedSize，elem又在堆上new了一个长度为10的数组。

代码示例：

public class MyArrayList{
    public int[] elem;
    public int usedSize;//表示当前有效数据个数

    public MyArrayList(){
        this.elem = new int[10];
    }

2.1打印顺序表

代码示例：

 // 打印顺序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] +" ");
        }
        System.out.println();
    }

2.2获取顺序表长度

代码示例：

// 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

2.3在 pos 位置新增元素

具体思想如下：

首先判断pos位置是否合法，如果pos小于0或者pos大于数组有效元素的个数，则认为该位置不合法，直接结束该语句。
然后，再判断该数组是否已经满了，如果现存有效元素个数与数组长度相等，就表明该数组已经满了，则这时就需要用到 Arrays.copyOf()函数来进行扩容，将数组长度扩大为原来的两倍。
最后，通过for循环来进行数组元素的移动，从有效元素位置开始，到要添加元素的pos位置，挨将前一个元素移动到后一个元素位置，直到移动到pos位置，然后将此位置赋值为要新增的data元素，最后再将有效元素的个数加1。

具体代码实现如下：

 public void add(int pos, int data){
 	if(pos < 0 || pos > usedSize){
 		System.out.println("pos位置不合法");
		return;
	}
	if(isFull()){
		this.elem = Arrays.copyOf(this.elem,this.elem.length * 2);
	}
	for(int i = this.usedSize - 1;i >= pos;i--){
		this.elem[i+1] = this.elem[i];
	}
	this.elem[pos] = data;
	this.usedSize++;
 }
 public boolean isFull(){
	return this.usedSize == this.elem.length;
}

public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }


 public int search(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

 public int getPos(int pos) {
    if (pos < 0 || pos >= this.usedSize){
        System.out.println("pos位置不合法");
        return -1;
    }
        if (isEmpty()){
            System.out.println("顺序表为空");
            return -1;
        }
        return this.elem[pos];
    }
    public boolean isEmpty(){
        return this.usedSize == 0;
    }

三、链表

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表的结构非常多样，以下情况组合起来就有8种链表结构：

• 单向、双向
• 带头、不带头
• 循环、非循环

这里主要讲解单向、不带头、非循环及双向、不带头、非循环。

链表是由一个一个的节点组成，节点中包括：val数据域及next域存放下一个节点的地址。每一个节点都有一个地址。每个节点中的next域就存放着下一个节点的地址。

head里面存放的就是第一个节点（头节点）的地址，head.next存储的就是下一个节点的地址。

head叫做头节点，最后一个节点叫做尾节点。尾节点的的next域为null。