定义：
线性表全名线性存储构造是最根本、最简略、也是最罕用的一种数据结构，专门用于存储逻辑关系为"一对一"的数据。个性：
- 数据类型统一
- 数据的逻辑关系都具备一对一关系
- 数据元素无限(专业术语为：存在惟一一个被称为“第一个”的数据元素，存在惟一一个被称为“最初一个”的数据元素)
- 是有序序列（专业术语为：除第一个元素外，每个元素都有惟一的一个”间接前驱“。除最初一个元素外，每一个元素都有惟一的”间接后继“）
存储形式：
线性表，基于数据在理论物理空间中的存储状态，又可细分为**程序表（顺序存储构造）**和**链表（链式存储构造）**。程序表（顺序存储构造）：
定义：
程序表，个别应用数组实现。也就是在内存中找个初始地址，而后数据元素顺次排队，数组大小有两种形式指定——动态调配和是动静扩大。特点：
- 随机拜访：可通过首地址和元素序号在单位工夫O(1)内找到指定的元素。
- 存储密度高：存储密度高是因为每个结点存储空间指用来存储数据元素，没有别的额定开销。
物理地位相邻：物理地位和逻辑地位一样，放弃相邻，因而插入和删除元素须要挪动大量元素，比拟耗时。这是物理构造相邻的所有数据结构的通病，尽管拜访快，然而如果有频繁的增删挪动操作，就会效率很低。
长处：
- 空间利用率高（理由：间断寄存）
- 存取速度高效，通过下标间接进行存储和读取。（想想排队哈）
- 顺序存储，随机读取（不算是长处，算是特点）
毛病：
- 插入和删除比较慢。（想想插队，前面的全副须要往后移一个位）
- 程序表开始时就要定义一个长度，因而是存在空间限度的。当须要存储的元素个数可能多于程序表元素时，可能呈现“溢出”问题。
链式存储构造：
定义：
用一组任意的存储单元存储线性表的数据元素（这组存储单元能够是间断的，也能够是不间断的），包含数据域和指针域，数据域存数据，指针域批示其后继的信息。特点：
随机存储、程序读取：物理地位和逻辑地位不同，物理地位随机存储，但都通过指针域连成线，能够按逻辑程序读取长处：
- 插入和删除的速度快，保留原有的物理程序（只扭转下指针。想想上述的插队问题就明确了）。
- 没有空间限度，根本只与内存空间大小无关。（满天飞）
- 随机存储，程序读取（算是特点）
毛病：
- 查找元素比较慢（不能进行索引拜访，只能从头结点开始程序查找）
- 占用额定的空间用来存储指针（不是间断寄存的（满天飞理解下），空间碎片多）
造成空间节约。
实操：
创立线性表接口类
/** * 线性表接口 * @author gxw * @date 2021/11/1 早晨21:50 */public interface LinearList { /** * 查找办法 */ //查找，是否蕴含g元素 boolean contains(Object g); //查找，返回 g 元素所在位置 int indexOf(Object g); //查找，返回第i地位的元素 Object getByIndex(int i); /** * 增加办法 */ //将元素插入到第i个地位 void add(int i, Object g) throws Exception ; //将元素插入到最初 void add(Object g) throws Exception ; //将g元素插入到x元素之前 boolean addBefore(Object x, Object g) throws Exception; //将g元素插入到x元素之后 boolean addAfter(Object x, Object g) throws Exception; /** * 删除办法 */ //删除第i个元素 void remove(int i) throws Exception ; //删除第一个为g的元素 void remove(Object g) throws Exception ; /** * 批改办法 */ //将第i个元素替换为g boolean replace(int i, Object g); //将x元素全副替换为g boolean replaceAll(Object x, Object g); /** * 返回线性表大小 */ int getSize(); /** * 判断线性表是否为空 */ boolean isEmpty(); /** * 输入线性表 */ void display();}程序表：
第一步：创立程序表实现类
/** * 线性表之程序表（顺序存储构造） * @author gxw * @date 2021/11/1 早晨21:51 */public class SequenceList implements LinearList { //申明大小为maxSize的程序表 private Object[] myList;//程序表的存储空间 private int size;//程序表以后的长度 private int maxSize;//程序表最大的长度 //构造方法来初始化程序表 public SequenceList(int maxSizeParam){ //设置程序表的初始长度为0 size = 0; //设置程序表的最大长度 maxSize = maxSizeParam; //实例化程序表 myList = new Object[maxSize]; } //是否蕴含g元素 @Override public boolean contains(Object g) {//工夫复杂度O(n) for (Object x : myList) { if(x.equals(g)) return true; } return false; } //获取g元素在第几个地位 @Override public int indexOf(Object g) {//工夫复杂度O(n) for(int i = 0;i < size;i++){ if(myList[i].equals(g)) return i; } return -1; } //获取第i地位的元素 @Override public Object getByIndex(int i) {//工夫复杂度O(1) //判断是否合乎现有长度 if(i < 0 || i > size) return null; return myList[i]; } @Override public void add(int i, Object g) throws Exception {//工夫复杂度O(n) //判断程序表是否曾经满员 if(size == maxSize) throw new Exception("程序表已满员，不可插入！");//手动抛出异样 //判断i是否在正确范畴内 if(i < 0 || i > size) throw new Exception("插入地位不合理，不可插入！");//手动抛出异样 //筹备执行插入，在插入之前，将要插入地位的元素往后移 for(int j = size;j > i;j--){ myList[j] = myList[j - 1]; } //执行插入 myList[i] = g; //现有程序表长度减少1 size++; } @Override public void add(Object g) throws Exception {//工夫复杂度O(1) //判断程序表是否曾经满员 if(size == maxSize) throw new Exception("程序表已满员，不可插入！");//手动抛出异样 //执行插入，插入到最初 myList[size] = g; //现有长度加一 size++; } @Override public boolean addBefore(Object x, Object g) throws Exception {//工夫复杂度O(n) //判断程序表是否曾经满员 if(size == maxSize) return false; //先获取x元素所在位置 int index = indexOf(x); if(index < 0) return false; //将x元素以及后继元素往后移 add(index, g); return true; } @Override public boolean addAfter(Object x, Object g) throws Exception {//工夫复杂度O(n) //判断程序表是否曾经满员 if(size == maxSize) return false; //先获取x元素所在位置 int index = indexOf(x); if (index < 0) return false; //将x元素的后继元素往后移 add(index + 1, g); return true; } @Override public void remove(int i) throws Exception {//工夫复杂度O(n) //判断程序表是否曾经为空 if(size == 0) throw new Exception("程序表已空，无奈删除！");//手动抛出异样 //判断i元素是否在0-size范畴内 if(i < 0 || i > size) throw new Exception("角标超出范围，无奈删除！");//手动抛出异样 //将i元素之后后继元素往前移 for(int j = i;j < size;j++){ myList[j] = myList[j + 1]; } //程序表长度减一 size--; } @Override public void remove(Object g) throws Exception {//工夫复杂度O(n) //判断程序表是否曾经为空 if(size == 0) throw new Exception("程序表已空，无奈删除！");//手动抛出异样 //查找元素的地位 int index = indexOf(g); if(index >= 0){ //删除元素，并将后继元素往前移 remove(index); }else{ throw new Exception("程序表无此元素，无奈删除！");//手动抛出异样 } } @Override public boolean replace(int i, Object g) {//工夫复杂度O(1) //判断程序表是否曾经为空 if(size == 0) return false; //判断i是否在0-size范畴内 if(i < 0 || i > size) return false; //执行替换，将i元素的值替换为g myList[i] = g; return true; } @Override public boolean replaceAll(Object x, Object g) {//工夫复杂度O(n) //判断程序表是否曾经为空 if(size == 0) return false; //暂存角标字符串 String indexStr = ""; //取出元素为x的所有角标 for (int i = 0;i < size;i++){ if(myList[i].equals(x)){ indexStr += i + ","; } } indexStr = indexStr.substring(0, indexStr.length() - 1); String[] indexArr = indexStr.split(","); //将取出的所有角标全替换为g元素 for (int i = 0;i < indexStr.split(",").length;i++){ int index = Integer.parseInt(indexArr[i]); //设置值 myList[index] = g; } return true; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void display() { for (int i = 0;i < size;i++){ System.out.print(myList[i] + " "); } System.out.println("展现程序表完结：一共长度为：" + size); }}第二步：测试
public static void main(String[] args) throws Exception { /** * 程序表 */ SequenceList sequenceList = new SequenceList(10); //增加 sequenceList.add("sequence "); sequenceList.add("hello "); sequenceList.add("world!"); sequenceList.add("hello "); sequenceList.display(); //指定角标增加 sequenceList.add(1, "哈哈 "); sequenceList.display(); //在指定元素之前增加 sequenceList.addBefore("哈哈 ", "呼呼 "); sequenceList.display(); //在指定元素之后增加 sequenceList.addAfter("哈哈 ", "嘿嘿 "); sequenceList.display(); //替换 sequenceList.replace(1, "略略 "); sequenceList.display(); //将指定元素值全都替换成设置元素值 sequenceList.replaceAll("hello ", "HELLO "); sequenceList.display(); //删除 sequenceList.remove(1); sequenceList.display(); //指定元素删除 sequenceList.remove("HELLO "); sequenceList.display(); }后果：
链表：
第一步：因为单链表依赖于Node，所以创立Node类
/** * 单链表采纳了结点，所以须要以下定义 * 次要两个属性，一个是数据域(存放数据内容)，一个是指针域(寄存下一个的结点的地址) */public class Node { //数据域 private Object data; //指针域 private Node next; public Node(){ this.data = new Object(); this.next = null; } public Node(Object data, Node next){ this.data = data; this.next = next; } public Node(Object data){ this.data = data; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; }}第二步：创立单链表实现类
/** * 线性表之链表（链式存储构造） * @author gxw * @date 2021/11/1 早晨21:53 */public class LinkedList implements LinearList { private Node headNode = new Node();//定义一个头空结点 private int size;//定义一共有几个结点 @Override public boolean contains(Object g) { Node node = headNode;//从头结点开始 for(int i = 0;i < size;i++){ if(node.getData().equals(g)){ return true; } //拜访下一个结点 node = node.getNext(); } return false; } @Override public int indexOf(Object g) { Node node = headNode;//从头结点开始 //因为头结点不存数据，所以间接获取子结点数据 node = node.getNext(); for(int i = 0;i < size;i++){ if(node.getData().equals(g)){ return i; } //拜访下一个结点 node = node.getNext(); } return -1; } @Override public Object getByIndex(int i) { Node node = headNode;//从头结点开始 for(int j = 0;j < i;j++){ //拜访下一个结点,直到拜访的第i个地位 node = node.getNext(); } return node.getData(); } @Override public void add(int i, Object g) throws Exception { //如果i不在0-size范畴 if(i < 0 || i > size) throw new Exception("角标超出失常范畴 i：" + i); //获取到第i个后面的结点，只须要让后面的结点指针域指到新要增加的结点上， // 本人的指针域指到第i个前面的结点上，就能够实现增加了 Node node = headNode; for(int j = 0;j < i;j++){ node = node.getNext();//继续拜访指针域，直到拜访到第i个结点 } //创立新要增加的结点 Node newNode = new Node(); //设置新结点的数据域 newNode.setData(g); //设置新结点的指针域，将后面获取到的结点的指针域的值，赋值给新要增加的结点 newNode.setNext(node.getNext()); //而后让后面取得的结点的指针域指向新增加的指针，即可胜利增加 node.setNext(newNode); //结点数加一 size++; } @Override public void add(Object g) throws Exception { //在最初增加结点 add(size, g); } @Override public boolean addBefore(Object x, Object g) throws Exception { //获取结点所在位置 int index = indexOf(x); //如果没有匹配的结点 if(index < 0) return false; //在x结点前增加结点，相当于就是查找到结点地位以后地位 add(index, g); return true; } @Override public boolean addAfter(Object x, Object g) throws Exception { //获取结点所在位置 int index = indexOf(x); //如果没有匹配的结点 if(index < 0) return false; //在x结点后增加结点 add(index + 1, g); return true; } @Override public void remove(int i) throws Exception { //如果i不在0-size范畴 if(i < 0 || i > size) throw new Exception("角标超出失常范畴 i：" + i); //删除结点，原理就是让此结点的前一个结点的指针域，指到此结点的下一个结点 Node node = headNode; for (int j = 0;j < i;j++){ node = node.getNext(); } //将前一个结点的指针域，指到此结点的下一个结点 node.setNext(node.getNext().getNext()); //结点数减1 size--; } @Override public void remove(Object g) throws Exception { //查找元素所在位置 int index = indexOf(g); //执行删除 remove(index); } @Override public boolean replace(int i, Object g) { //如果i不在0-size范畴 if(i < 0 || i > size) return false; //找到第i个结点 Node node = headNode; for (int j = 0;j < i + 1;j++){ //因为头结点是空结点，所以须要略过，就i + 1 node = node.getNext(); } //而后将第i个结点的数据域更换为g node.setData(g); return true; } @Override public boolean replaceAll(Object x, Object g) { return false; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void display() { Node node = headNode; for (int i = 0;i < size;i++){ node = node.getNext(); System.out.print(node.getData() + " "); } System.out.println("展现实现，结点长度为：" + size); }}第三步：测试
public static void main(String[] args) throws Exception { /** * 单链表 */ LinkedList linkedList = new LinkedList(); //增加 linkedList.add("1"); linkedList.add("2"); linkedList.add("3"); linkedList.display(); //在2之前增加 linkedList.addBefore("2", "4"); linkedList.display(); //在2之后增加 linkedList.addAfter("2", "5"); linkedList.display(); //查找地位 System.out.println(linkedList.indexOf("1")); System.out.println(linkedList.indexOf("2")); System.out.println(linkedList.indexOf("3")); //替换 linkedList.replace(1, "22 "); linkedList.display(); //删除 linkedList.remove("3"); linkedList.display(); }后果：
其它补充：
前驱：
数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。间接前驱：
某一元素的左侧相邻元素称为“间接前驱”前驱元素：
位于此元素左侧的所有元素都统称为“前驱元素”后继
间接后继：
某一元素的右侧相邻元素称为“间接后继”后继元素：
位于此元素右侧的所有元素都统称为“后继元素”————————————END—————————————
数据结构之线性表篇，在此完结，学习中的总结，心愿能够帮忙认真学习的你，如果总结有问题，也心愿贵人忘请斧正，谢谢！