线性表：（List） 是n个具有 相同特性 的数据元素的 有限序列 。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串 线性表在逻辑上是 线性结构 ，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以 数组 和 链式结构 的形式存储
（1）神马是顺序表：(ArrayList) 是用一段 物理地址连续 的存储单元依次存储数据元素的 线性结构（逻辑上也连续） 一般采用 数组 存储，也就是在数组上增删查改
① 从Java语法的角度： List 是接口 ; ArrayList 是类，实现了 List ② 从数据结构的角度： List 表示线性表， ArrayList 表示顺序表 通过 ArrayList 实现 List 。。 表达了顺序表是一种线性表
（2）分类： 静态 顺序表： 使用 定长数组 存储 动态 顺序表： 使用 动态开辟的数组 存储
（3）接口的实现：（下面这个为一个简单的顺序表）
import java.util.Arrays; /** * 顺序表 */ class MyArrayList { public int[] elem; // null public int usedSize; // 0 表示数组中元素的个数 public MyArrayList() { this.elem = new int[5]; this.usedSize = 0; } // 打印顺序表 public void display() { for(int i = 0;i < usedSize;i++) { System.out.print(elem[i]+" "); } System.out.println(); } //在 pos 位置新增元素 public void add(int pos,int data) { if(pos < 0 || pos > this.usedSize) { System.out.println("该位置不合法！"); } //扩容 if(this.usedSize == this.elem.length) { this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } for(int i = this.usedSize;i >= pos;i--) { this.elem[i+1] = this.elem[i]; } this.elem[pos] = data; this.usedSize++; } //判定是否含某个元素 public boolean contains(int toFind) { for(int i = 0;i < this.usedSize;i++) { if(elem[i] == toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int search(int toFind) { for(int i = 0;i < this.usedSize;i++) { if (elem[i] == toFind) { return i+1; } } return -1; } // 获取 pos 位置的元素 public int getPos(int pos) { if(pos < 0 || pos >= this.usedSize) { System.out.println("该位置不合法！"); } return elem[pos-1]; } // 给 pos 位置的元素设为 value public void setPos(int pos,int value) { if(pos < 0 || pos > this.usedSize) { System.out.println("该位置不合法！"); } this.elem[pos] = value; } //删除第一次出现的关键字 key public void remove(int toRemove) { //找到是否有 toRemove int index = search(toRemove); if(index == -1) { System.out.println("么找到该元素！"); return; } for(int i = index;i < this.usedSize-1;i++) { this.elem[i] = this.elem[i+1]; } this.usedSize--; } //获取顺序表长度 public int size() { return this.usedSize; } //清除顺序表 /** * 如果是引用类型： elem[i] = null; */ public void clear() { this.usedSize = 0; // 仅限于简单类型 } } public class table { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(0,1);//往顺序表里添数 myArrayList.add(1,2); myArrayList.add(2,3); myArrayList.add(3,4); myArrayList.display();//打印数组 System.out.println(myArrayList.contains(6));//判断数组中是否有 6 System.out.println("所找的数在第"+myArrayList.search(6)+"个位置"); System.out.println(myArrayList.getPos(2));//获取 2 位置的元素 myArrayList.setPos(2,12);//将 2 位置的数值换为 12 myArrayList.display();//打印数组 myArrayList.remove(6);//删除 6 myArrayList.display(); } } 顺序表中间/头部的插入删除，时间复杂度为O(N)增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。为了解决顺序表的弊端，我们引入了单链表：
（1）神马是单链表 ： 是一种 物理存储结构 上 非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接次序 实现的 。（逻辑连续）
（2）表现形式：（一共是 8 种） 聪明的你尝试自己组合一下。。。 ① 单向 、 双向 ② 带头 、 不带头 ③ 循环 、 非循环
下来我们简单介绍两种形式的：（面试问的最多！） 链表 由一个一个的 节点组成： 你问我节点是干嘛的？ 节点 当然是用来 存储数据 的了。。。
data ：数据，不一定是整型的 next ：下一个节点的引用（地址）
（头节点可能会随时改变） 写一个简单的 单向 不带头 非循环链表
/** * 单链表 */ class Node { public int data; public Node next; // 表示下个节点的引用 public Node(int data) { this.data = data; } } public class SingleLinkedList { public static void main(String[] args) { SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.addFirst(6); singleLinkedList.addLast(1); singleLinkedList.addFirst(4); singleLinkedList.addLast(8); singleLinkedList.addLast(1); singleLinkedList.addLast(6); singleLinkedList.display(); //singleLinkedList.remove(1); //singleLinkedList.display(); System.out.println(singleLinkedList.contains(6)); singleLinkedList.removeAllKey(6); singleLinkedList.display(); } public Node head;// 标识头节点 //头插法 public void addFirst(int data) { Node node = new Node(data); node.next = this.head; this.head = node; } // 打印 public void display() { Node cur = this.head; while(cur != null) { System.out.print(cur.data+" "); cur = cur.next; } System.out.println(); } // 尾插法 public void addLast(int data) { Node node = new Node(data); if(this.head == null) { this.head = node; } else { Node cur = this.head; while(cur.next != null) { cur = cur.next; } cur.next = node; } } // 检查下标是否合法 public boolean checkIndex(int index) { if(index == 0 || index > this.getLength()) { System.out.println("下标不合法！"); return false; } return true; } // 任意位置插入，第一个数据节点为0号下标 public void addIndex(int index,int data) { if(!checkIndex(index)) { return; } if(index == 0) { addFirst(data); return; } if(index == this.getLength()) { addLast(data); return; } Node cur = searchPrev(index);//cur 此时保存的就是 index-1 位置节点的引用 Node node = new Node(data); node.next = cur.next; cur.next = node; } public int getLength() { int count = 0; Node cur = this.head; while(cur != null) { count++; cur = cur.next; } return count; } //查找index的位置，找到并返回引用 public Node searchPrev(int index) { Node cur = this.head; int count = 0; while(count < index-1) { cur = cur.next; count++; } return cur; } // 找前驱 public Node searchPrevNode(int key) { Node cul = this.head; while (cul.next != null) { if(cul.next.data == key) { return cul; } cul = cul.next; } return null; } //删除第一次出现关键字 key 的节点 public void remove(int key) { // 头节点是要删除的节点 if(this.head == null) return; if(this.head.data == key) { this.head = this.head.next; return; } Node cul = searchPrevNode(key); if(cul == null) { System.out.println("没有你要删除的数字！"); return; } Node del = cul.next; // 所要删除的节点 cul.next = del.next; } // 判断是否包含某个元素 public boolean contains(int toFind) { Node cul = this.head; while (cul != null) { if(cul.data == toFind) { return true; } cul = cul.next; } return false; } // 删除所有值为 key 的节点 public void removeAllKey(int key) { if(this.head == null) return; Node prev = this.head; Node cul = this.head.next; while(cul != null) { if (cul.data == key) { prev.next = cul.next; cul = cul.next; } else { prev = cul; cul = cul.next; } } if(this.head.data == key) { this.head = this.head.next; } } }区别：
顺序表：（物理上和逻辑上都是连续的） （1）空间连续、支持随机访问（底层是数组） （2）中间或前面部分的插入删除时间复杂度是O(N) （3）增容代价大 链表： （逻辑上连续，物理上不一定连续） （1）以结点为单位存储， 不支持随机访问 （2）任意位置插入删除时间复杂度为 O(1) （3）没有增容问题，插入一个开辟一个空间
