---

一、线性表

线性表:数据存储时，按照逻辑连续存储，成线性结构（特点：都有索引概念，索引较小的元素一定逻辑排在索引较大的元素之前）

线性表子集：顺序表,链表，栈，队列，字符串

线性表存储分为两种结构：
基于数组的线性表：顺序表（元素不仅逻辑连续，物理上也连续）
基于链表的线性表：值是元素之间得到逻辑连续

二、顺序表

java中的基本数组问题：数组长度固定，声明后只能存放固定长度的数值
顺序表：基于数组的线性表——动态数组（根据数据的大小动态调整）

package seqlist;
//基于数组的顺序表
public class MyArray {//存储元素还在数组中private  int[] data;//当前动态数组中实际存储的元素个数private  int size;//data.length-此时数组最多存储元素个数，size-实际用的空间//默认开辟数字大小为10public MyArray(){data = new int[10];}//用户想要传入的数组大小public MyArray(int capacity){data = new int[capacity];}
}

CURD四大操作：增删查改

1.增加：

addFirst(int val):在数组头部插入
addLast(int val):在数组尾部插入
addIndex(int index, int val){}:在数组中间插入

①.打印

//打印当前数组内容public String toString(){String ret = "[";//遍历data数组for (int i = 0; i < size; i++) {//任何数和String型相加自动变为String型ret+=data[i];if(i!=size-1) {ret +=",";}}ret+="]";return ret;}

②.扩容及尾插

添加就要考虑原数组是否已满，若size==data.length说明已满，此时应该扩容

    /*** 在数组的尾部插入* @param value 待插入的新元素值*/public void addLast(int value){//先判断当前数组是否已满if (size== data.length){//当前数组已满//数组要扩容grow();}data[size]=value;size++;}private void grow(){//原先数组为data然后扩容为原来大小的两倍data.length<<1,返回一个扩容后新数组int[] newData=Arrays.copyOf(this.data,this.data.length<<1);//指向扩容后新数组this.data=newData;}

③.头插

    /***  在数组头部插入* @param value 待插入的新元素值*/public void addFirst(int value){if(size== data.length){grow();}//在数组头部插入//先将原先数组从最后一个元素开始依次向后移动一个单位for (int size-1 = 0; i>=0 ; i--) {data[i+1]=data[i];}//此时data[0]就空出来了data[0]=value;size++;}

④.索引插入

/*** 在数组任意位置插入* @param index 传入的索引值* @param value 要插入的新元素*/public void addIndex(int index ,int value){//index<0//index>size，size表示当前有效数组保证连续性，判断index的合法性if(index<0||index>size){System.err.println("add inedx illegal!");return;}//判断数组是否满if(size== data.length){grow();}if (index == 0) {addFirst(value);return;}if (index == size) {addLast(value);return;}else {//将index位置空出来for (int i = size-1; i >=index ; i--) {data[i+1]=data[i];}data[index]=value;size++;}}

⑤.编写测试代码及结果

public class Test {public static void main(String[] args) {MyArray myArray = new MyArray(3);myArray.addLast(1);myArray.addLast(3);myArray.addLast(5);myArray.addLast(7);System.out.println(myArray);myArray.addFirst(10);System.out.println(myArray);myArray.addIndex(1,22);myArray.addIndex(0,33);myArray.addIndex(7,44);myArray.addIndex(10,55);System.out.println(myArray);}
}

2.查找

boolean contains(int value):查看当前数组中是否存在
int get (int index):根据索引取得相应位置
int getByValue(int value):查找当前数组中元素value对应的下标index

①.int getByValue(int value)

/*** 在数组中查找value值对应的索引下标* @param value* @return*/public int getByValue(int value){//遍历数组for (int i = 0; i <size ; i++) {if(data[i]==value){return i;}}//此时循环走完还没找到return -1;}

②.boolean contains(int value)

/*** 查看是否存在value* @param value* @return*/public  boolean contains(int value){int index=getByValue(value);if(index==-1){return false;}return true;}

③.int get (int index)

/*** 根据索引查询元素* @param  index 索引值* @return*/public int get(int index){//判断合法性if(index<0||index>=size){System.err.println("get index illegal!");return -1;}return data[index];}

④.测试代码及结果

        System.out.println(myArray);System.out.println(myArray.contains(7));System.out.println(myArray.getByValue(22));System.out.println(myArray.get(3));

3.改

根据索引修改原先元素
int set (int index,int newValue)：将指定索引位置元素修改为newValue，返回修改前元素值

①.int set (int index,int newValue)

 /*** 将指定索引位置元素修改为newValue，返回修改前元素值* @param index* @param newValue* @return*/public int set(int index,int newValue){//判断合法性if(index<0||index>=size) {System.err.println("get index illegal!");return -1;}else{int oldValue=data[index];data[index]=newValue;return oldValue;}}

②.测试代码及结果

        System.out.println(myArray);//[33,10,22,1,3,5,7,44]System.out.println(myArray.set(1,100));System.out.println(myArray);

4.删除

 void removeFirst():删除头元素void removeLast():删除尾元素void removeIndex(int index):根据索引index删除元素void removeValueOnce(int value):删除数组中第一个元素值为value的元素void removeValueAll(int value):删除数组中所有值为value的元素

①.删除指定位置元素

/*** 删除指定索引位置的元素* @param index*/public  void removeIndex(int index){if(index<0||index>=size) {System.err.println("remove index illegal!");return;}//为保证data[i+1]仍然不越界，判断条件为i<size-1for (int i = index; i <size-1 ; i++) {data[i]=data[i+1];}size--;//删除原先数组的最后一个位置元素data[size]=0;}

②.删除头元素

public void removeFirst(){removeIndex(0);}

③.删除尾元素

   public void removeLast(){removeIndex(size-1);}

④.删除出现一次值为value的元素

   public void removeValueOnce(int value){for (int i = 0; i <size ; i++) {if(value==data[i]){//此时i对应的索引是第一个值为value的元素removeIndex(i);return;}}}

⑤.删除所有值为value的元素

public void removeValueAll(in value){for (int i = 0; i <size; i++) {//重复删除元素时使用while//i！=size极端情况后面的全部及当前元素全部删除while(value==data[i]&&i!=size){//此时i对应的索引是第一个值为value的元素removeIndex(i);return;}}}

⑥.测试代码及结果

myArray.removeFirst();myArray.removeLast();myArray.removeIndex(1);System.out.println(myArray);

总结

1.MyArray-包装了一下数组，使其具备可以动态扩容的功能
2.当使用println方法进行一个对象的输出时，需要在该对象所在的类中实现toString(),将一个对象->String
3.成员变量初始化：构造方法
4.动态数组：①缺点：头部删除和添加O(N)，扩容：O(N)扩容是一个非常耗时的操作，空间复杂度：O(N) ②优点：根据索引查找元素O(N)
5.完整代码

package seqlist;import com.sun.media.sound.RIFFInvalidDataException;import java.util.Arrays;//基于数组的顺序表
public class MyArray {//存储元素还在数组中private  int[] data;//当前动态数组中实际存储的元素个数private  int size;//data.length-此时数组最多存储元素个数，size-实际用的空间//默认开辟数字大小为10public MyArray(){data = new int[10];}//用户想要传入的数组大小public MyArray(int capacity){data = new int[capacity];}/*** 在数组的尾部插入* @param value 待插入的新元素值*/public void addLast(int value){//先判断当前数组是否已满if (size== data.length){//当前数组已满//数组要扩容grow();}data[size]=value;size++;}/***  在数组头部插入* @param value 待插入的新元素值*/public void addFirst(int value){if(size== data.length){grow();}//在数组头部插入//先将原先数组从最后一个元素开始依次向后移动一个单位for (int i=size-1; i>=0; i--) {data[i+1]=data[i];}//此时data[0]就空出来了data[0]=value;size++;}/*** 在数组任意位置插入* @param index 传入的索引值* @param value 要插入的新元素*/public void addIndex(int index ,int value){//判断数组是否满if(size== data.length){grow();}//index<0//index>size，size表示当前有效数组保证连续性，判断index的合法性if(index<0||index>size){System.err.println("add inedx illegal!");return;}if (index == 0) {addFirst(value);return;}if (index == size) {addLast(value);return;}else {//将index位置空出来for (int i = size-1; i >=index ; i--) {data[i+1]=data[i];}data[index]=value;size++;}}//打印当前数组内容public String toString(){String ret = "[";//遍历data数组for (int i = 0; i < size; i++) {//任何数和String型相加自动变为String型ret += data[i];if(i!=size-1) {ret +=",";}}ret+="]";return ret;}private void grow(){//原先数组为data然后扩容为原来大小的两倍data.length<<1,返回一个扩容后新数组int[] newData=Arrays.copyOf(this.data,this.data.length<<1);//指向扩容后新数组this.data=newData;}/*** 在数组中查找value值对应的索引下标* @param value* @return*/public int getByValue(int value){//遍历数组for (int i = 0; i <size ; i++) {if(data[i]==value){return i;}}//此时循环走完还没找到return -1;}/*** 查看是否存在value* @param value* @return*/public  boolean contains(int value){int index=getByValue(value);if(index==-1){return false;}return true;}/*** 根据索引查询元素* @param  index 索引值* @return*/public int get(int index){//判断合法性if(index<0||index>=size){System.err.println("get index illegal!");return -1;}return data[index];}/*** 将指定索引位置元素修改为newValue，返回修改前元素值* @param index* @param newValue* @return*/public int set(int index,int newValue){//判断合法性if(index<0||index>=size) {System.err.println("get index illegal!");return -1;}else{int oldValue=data[index];data[index]=newValue;return oldValue;}}/*** 删除指定索引位置的元素* @param index*/public  void removeIndex(int index){if(index<0||index>=size) {System.err.println("remove index illegal!");return;}//为保证data[i+1]仍然不越界，判断条件为i<size-1for (int i = index; i <size-1 ; i++) {data[i]=data[i+1];}size--;//删除原先数组的最后一个位置元素data[size]=0;}public void removeFirst(){removeIndex(0);}public void removeLast(){removeIndex(size-1);}public void removeValueOnce(int value){for (int i = 0; i <size ; i++) {if(value==data[i]){//此时i对应的索引是第一个值为value的元素removeIndex(i);return;}}}public void removeValueAll(int value){for (int i = 0; i <size; i++) {//重复删除元素时使用while//i！=size极端情况后面的全部及当前元素全部删除while((value==data[i]) && (i!=size)){//此时i对应的索引是第一个值为value的元素removeIndex(i);return;}}}
}

package seqlist;public class Test {public static void main(String[] args) {MyArray myArray = new MyArray(3);myArray.addLast(1);myArray.addLast(3);myArray.addLast(5);myArray.addLast(7);System.out.println(myArray);myArray.addFirst(10);System.out.println(myArray);myArray.addIndex(1,22);myArray.addIndex(0,33);myArray.addIndex(7,44);System.out.println(myArray);//[33,10,22,1,3,5,7,44]//        System.out.println(myArray.contains(7));
//        //2
//        System.out.println(myArray.getByValue(22));
//        //1
//        System.out.println(myArray.get(3));//        System.out.println(myArray.contains(7));
//        System.out.println(myArray.getByValue(22));
//        System.out.println(myArray.get(3));myArray.removeFirst();myArray.removeLast();myArray.removeIndex(1);System.out.println(myArray);}
}

链表

链表：逻辑上连续，多个节点采用挂载的方式进行链接，物理上不连续。类比：火车
火车这种结构：都是从头开始遍历，走到火车尾

车厢：具体存储元素的类

class Node{int data;//具体存储数据Node next;//存储下一节车厢的地址}

火车：就是尤一系列车厢拼起来
单列表：只能从头部开始遍历，依次走到尾部，单项遍历

//单链表-火车类
class SingList{int size;//车厢个数Node head;//第一节车厢的地址（头节点）
}

1.增加：

①.火车类和车厢类

package seqlist;/*** 火车类，拼接是由多个车厢拼接在一起*/
public class SingleLinkedList {//当前火车中车厢的节点个数（实际就是具体元素的个数）private  int size;//当前火车的火车头private Node head;
}/*** 火车的车厢类,一个车厢只能保存一个元素*/
class Node{//存储具体数据int val;//保存下一个车厢的地址Node next;public  Node (int val){this.val=val;}
}

②.头插法

 /*** 在火车头部添加元素-添加一个车厢的节点* @param val*/public  void addFirst(int val){//新建一个车厢节点Node node = new Node(val);//判断当前的火车是否为空if(head==null){head =node;}else {//火车中有节点，要把当前新车厢挂载到火车头部node.next=head;head=node;}size++;}

③.toString方法

    public String toString(){String ret="";//遍历火车这个类//从火车头（head）走到火车尾部（）//暂时存储当前头节点地址Node node =head;while(node!=null){ret+=node.val;ret+="->";//继续访问下一节点；node=node.next;}//表示当前走到尾ret+="NULL";return ret;}

④.任意位置插入

/*** 在单列表的任意一个索引位置插入元素val* @param index* @param val*/public void addIndex(int index,int val){//1.合法性if (index<0|index>size){System.err.println("add index illegal!");return ;}//头插法if (index==0){addFirst(val);return;}//2.插入元素Node node = new Node(val);//需要找到待插入的前去Node prev = head;for (int i = 0; i < index-1; i++) {prev=prev.next;}//此时prev指向待插入位置的前驱节点node.next=prev.next;prev.next=node;size++;}

⑤.尾插法

    /*** 在单列表的尾部插入元素* @param index* @param val*/public void addLast(int val){addIndex(size,val);}//测试代码SingleLinkedList singleLinkedList=new SingleLinkedList();singleLinkedList.addLast(1);singleLinkedList.addLast(2);singleLinkedList.addLast(3);singleLinkedList.addIndex(1,10);//1,10,2,3->NULLSystem.out.println(singleLinkedList);

2.查找：

get(int index):返回index位置的元素值//合法性，index<0||index>=size
contains(int value):查询值为value的元素是否在单链表中存在

①.判断合法性

    /*** 判断用户输入的index是否合法（改，查，删除使用）* @param index* @return*/private boolean rangeCheck(int index){if (index < 0||index>=size) {return false;}return true;}

②.get(int index)方法

 public int get(int index){if (rangeCheck(index)){//index合法//从头节点开始遍历链表，走到index位置Node node=head;//规定了走的步数for (int i = 0; i < index; i++) {node =node.next;}return node.val;}else{System.err.println("get index illegal!");return -1;}}

②.contains(int value)方法

 /*** 判断当前链表中是否有包含值为val的节点* @param val* @return*/public boolean contains(int val){for (Node temp= head; temp!=null ; temp=temp.next) {if(temp.val==val){return true;}}return false;}

3.改：

set(int index,int newValue):修改index位置的值为newValue//合法性index<0||index>=size

①.set(int index,int newValue)方法

  /*** 将单链表索引为index的节点值改为newVal* @param index* @param newVal* @return*/public int set(int index,int newVal){if (rangeCheck(index)) {Node node=head;for (int i = 0; i <index ; i++) {node=node.next;}int oldVal= node.val;node.val=newVal;return oldVal;}else{System.err.println("set index illegal!");return -1;}}

②.测试代码

  SingleLinkedList singleLinkedList=new SingleLinkedList();singleLinkedList.addLast(1);singleLinkedList.addLast(2);singleLinkedList.addLast(3);singleLinkedList.addIndex(1,10);//1,10,2,3->NULLSystem.out.println(singleLinkedList);//2System.out.println(singleLinkedList.get(2));//falseSystem.out.println(singleLinkedList.contains(100));singleLinkedList.set(2,200); System.out.println(singleLinkedList);

4.删除：

removeIndex(int index)；//删除index节点
removeValueOnce(int value);//删除单链表中第一个值为value的节点
removeValueAll(int value);//删除单链表中所有值为value的节点

在单链表的插入余删除中都需要找到前驱节点，只有头节点没有前驱节点，因此需要特殊处理

①.removeIndex(int index)代码

public void removeIndex(int index){//合法性if(rangeCheck(index)) {if (index == 0) {//边界 删除头节点的情况Node temp = head;head = head.next;temp.next = null;size--;} else {//index中间位置//找到前驱节点Node prev = head;for (int i = 0; i < index - 1; i++) {prev = prev.next;}//待删除节点Node cur = prev.next;prev.next = cur.next;cur.next = null;size--;}}else{System.err.println("remove index illegal!");}
}public void removeFirst(){removeIndex(0);
}public  void removeLast(){removeIndex(size-1);
}

②.removeValueOnce(int value)代码

 /*** 删除链表中第一次出现的待删除元素* @param val*/public void removeValueOnce(int val){//遍历链表，找到值为val的节点//找到删除节点（正常删除都要找前驱，只有头节点没有前驱）if(head.val==val){//头结点是待删除结点Node temp=head;head=head.next;temp.next=null;size--;}else{//此时head一定不是待删除节点Node prev=head;//判断前驱的下一个节点是否等于val//看你取值用的是哪一个引用，就判断哪个引用不为空while(prev.next!=null) {//存在空指针问题if (prev.next.val == val) {Node cur=prev.next;prev.next=cur.next;cur.next=null;size--;return;}prev=prev.next;}}}

③.removeValueAll(int value)代码

 public void removeIndexAll(int val){while(head!=null&&head.val==val){head=head.next;size--;}if(head==null){//此时链表中的值全是valreturn ;}else{//此时head一定不是待删除节点，链表中还有节点Node prev=head;while(prev.next!=null){if (prev.next.val == val) {Node cur=prev.next;prev.next=cur.next;cur.next=null;size--;}else{//只有确保prev.next不是待删除节点才能移动prev指向//prev一定不是待删除节点prev=prev.next;}}}}

4.完整代码：

package seqlist;import java.rmi.ServerError;/*** 火车类，拼接是由多个车厢拼接在一起*/
public class SingleLinkedList {//当前火车中车厢的节点个数（实际就是具体元素的个数）private  int size;//当前火车的火车头private Node head;/*** 在火车头部添加元素-添加一个车厢的节点* @param val*/public  void addFirst(int val){//新建一个车厢节点Node node = new Node(val);//判断当前的火车是否为空if(head == null){head =node;}else {//火车中有节点，要把当前新车厢挂载到火车头部node.next=head;head=node;}size++;}/*** 在单列表的任意一个索引位置插入元素val* @param index* @param val*/public void addIndex(int index,int val){//1.合法性if (index<0|index>size){System.err.println("add index illegal!");return ;}//头插法if (index==0){addFirst(val);return;}//2.插入元素Node node = new Node(val);//需要找到待插入的前去Node prev = head;for (int i = 0; i < index-1; i++) {prev=prev.next;}//此时prev指向待插入位置的前驱节点node.next=prev.next;prev.next=node;size++;}/*** 在单列表的尾部插入元素* @param in dex* @param val*/public void addLast(int val){addIndex(size,val);}public String toString(){String ret="";//遍历火车这个类//从火车头（head）走到火车尾部（）//暂时存储当前头节点地址Node node =head;while(node!=null){ret+=node.val;ret+="->";//继续访问下一节点；node=node.next;}//表示当前走到尾ret+="NULL";return ret;}/*** 判断用户输入的index是否合法（改，查，删除使用）* @param index* @return*/private boolean rangeCheck(int index){if (index < 0||index>=0) {return false;}return true;}public int get(int index){if (rangeCheck(index)){//index合法//从头节点开始遍历链表，走到index位置Node node=head;//规定了走的步数for (int i = 0; i < index; i++) {node =node.next;}return node.val;}else{System.err.println("get index illegal!");return -1;}}/*** 判断当前链表中是否有包含值为val的节点* @param val* @return*/public boolean contains(int val){for (Node temp= head; temp!=null ; temp=temp.next) {if(temp.val==val){return true;}}return false;}/*** 将单链表索引为index的节点值改为newVal* @param index* @param newVal* @return*/public int set(int index,int newVal){if (rangeCheck(index)) {Node node=head;for (int i = 0; i <index ; i++) {node=node.next;}int oldVal= node.val;node.val=newVal;return oldVal;}else{System.err.println("set index illegal!");return -1;}}}/*** 火车的车厢类,一个车厢只能保存一个元素*/
class Node{//存储具体数据int val;//保存下一个车厢的地址Node next;public  Node (int val){this.val=val;}
}

package seqlist;public class Test {public static void main(String[] args) {
//        MyArray myArray = new MyArray(3);
//        myArray.addLast(1);
//        myArray.addLast(3);
//        myArray.addLast(5);
//        myArray.addLast(7);
//        System.out.println(myArray);
//        myArray.addFirst(10);
//        System.out.println(myArray);
//        myArray.addIndex(1,22);
//        myArray.addIndex(0,33);
//        myArray.addIndex(7,44);
//        System.out.println(myArray);
//        //[33,10,22,1,3,5,7,44]//        System.out.println(myArray.contains(7));
//        //2
//        System.out.println(myArray.getByValue(22));
//        //1
//        System.out.println(myArray.get(3));//        System.out.println(myArray.contains(7));
//        System.out.println(myArray.getByValue(22));
//        System.out.println(myArray.get(3));//        myArray.removeFirst();
//        myArray.removeLast();
//        myArray.removeIndex(1);
//        System.out.println(myArray);//        使用者的是火车类
//        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.addFirst(1);
//        singleLinkedList.addFirst(3);
//        singleLinkedList.addFirst(5);
//        System.out.println(singleLinkedList);SingleLinkedList singleLinkedList=new SingleLinkedList();singleLinkedList.addLast(1);singleLinkedList.addLast(2);singleLinkedList.addLast(3);singleLinkedList.addIndex(1,10);//1,10,2,3->NULLSystem.out.println(singleLinkedList);//2System.out.println(singleLinkedList.get(2));//falseSystem.out.println(singleLinkedList.contains(100));singleLinkedList.set(2,200);System.out.println(singleLinkedList);}}

三、练习题

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

方法一：常规解法

package leetcode;/*** LeetCode第203号问题-* 删除链表中所有Node.val == val节点，并返回新的头节点*/
public class Num203 {public ListNode removeElements(ListNode head, int val) {//头节点就是待删除节点while(head!=null&&head.val==val){head=head.next;}if (head == null) {return null;}else{//头节点一定不是待删除结点且链表不为空ListNode prev=head;while(prev.next!=null){if(prev.next.val==val){ListNode cur=prev.next;prev.next=cur.next;}else{//只有当prev.next.val!=valprev=prev.next;}}}return head;}
}

方法二：利用递归方法

  //递归方法求解public class Num203 {public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}//将haed.next以及之后的节点处理，交给removeElements(head.next,val)head.next=removeElements(head.next,val);//自己处理下一个头节点if (head.val == val) {return head.next;}return head;}
}