數據結構：順序表+鏈表

一。順序表：

首先在了解順序表和鏈表之前，先了解一下線性表，**線性表（linear list）**是n個具有相同特征元素的有限序列，在邏輯上是線性結構，也就是一條連續的直線，但是在物理上不一定是連續的。常見的線性表：順序表，鏈表，棧，隊列…

順序表是用一段物理地址連續的存儲單元一次儲存數據元素的線性結構，一般情況下使用數組存儲。在數組上完成數據的增刪查改

下面將了解順序表的底層實現邏輯：

接口：

public interface SeqList {public void add(int data);//新增元素，默認在數組最后進行新增public void add(int pos,int data);//新增元素，在pos這個位置加上data這個數據public boolean contain(int toFind);//查看toFind這個元素是否在數組中存在public int index(int toFind);//查看這個元素在數組中的下標public int get(int pos);//獲取pos位置的元素public void set(int pos,int value);//給pos位置的值修改為valuepublic int remove(int toRemove);//刪除第一次出現的的關鍵字keypublic int size();//獲取順序表的長度public void display();//打印順序表
}

接口的實現：

import java.util.Arrays;public class Main implements SeqList{private int[] elem=new int[10];private int usedSize;@Overridepublic void add(int data) {if(isFull()){elem= Arrays.copyOf(elem,elem.length*2);}this.elem[usedSize]=data;usedSize++;}public boolean isFull(){if(usedSize==elem.length){return true;}return false;}@Overridepublic void add(int pos, int data) {if(pos<0 || pos>usedSize){System.out.println("輸入不合法");//可以把這個寫進一個方法中，然后寫一個異常，如果pos不合法就拋出異常}if(isFull()){elem=Arrays.copyOf(elem,elem.length*2);}for(int i=usedSize-1;i >=pos;i--){//先把所有的元素向后移動一個單元，當i<pos的時候就結束elem[i+1]=elem[i];}elem[pos]=data;usedSize++;}@Overridepublic boolean contain(int toFind) {for(int i=0;i<usedSize;i++){if(elem[i]==toFind){return true;}}return false;}@Overridepublic int index(int toFind) {if(this.contain(toFind)){for(int i=0;i<usedSize;i++){if(elem[i] == toFind){return i;}}}return 0;}@Overridepublic int get(int pos) {if(pos<0||pos>usedSize-1){System.out.println("輸入的元素不合法");}else {for (int i=0;i<usedSize;i++){if(pos==i){//System.out.println(elem[pos]);return elem[pos];}}}return 0;}@Overridepublic void set(int pos, int value) {if(pos<0||pos>usedSize){System.out.println("輸入不合法");}elem[pos]=value;}@Overridepublic void remove(int toRemove) {int ret=this.index(toRemove);//獲取刪除元素的下標for(int i=ret;i<usedSize-1;i++){elem[i]=elem[i+1];}elem[usedSize-1]=0;usedSize--;}@Overridepublic int size() {int count=0;for(int i=0;i<elem.length;i++){count++;}return count;}@Overridepublic void display() {for(int i=0;i<usedSize;i++){System.out.println(elem[i]+" ");}}
}

二。ArrayList的使用

ArrayList是以泛型方式實現的，使用時必須先要將其實例化

1.ArrayList的構造：

List<Integer> list1=new ArrayList<>();//構造一個空的列表
List<Integer> list1=new ArrayList<>(10);//構造一個列表，其中含有10個元素

2.ArrayList的常見操作；

import java.util.ArrayList;public class Main {public static void main(String[] args) {ArrayList<Integer> list1=new ArrayList<>();list1.add(10);//加入元素list1.add(0,10)//在0下標的位置插入數字10list1.remove(1);//刪除下標為1的值list1.get(2);//獲取下標為2的值list1.set(1,3);//把下標為1的位置的值改為3list1.contain(12);//是否有12這個值在此線性表中list1.indexOf(10);//返回第一個值為10的下標list1.size();//獲取整個順序表的元素個數  }
}

注意：

當實例一個空的列表時，第一次add默認分配一個大小為10的內存（在實例化階段不分配內存）

擴容是自動以1.5倍的形式擴容

3.順序表的遍歷

//法一：
for(int i=0;i<list.size();i++){System.out.println(list.get(i));
}
//法二：
System.out.println(list);

三。ArrayList的具體使用例子

楊輝三角的實現：

在這里插入圖片描述

上述這個圖片就是我們常說的楊輝三角，在高中的時候沒少接觸這個東西

這個楊輝三角主要的實現方式是通過二維順序表實現的，下面將對用二維順序表來實現楊輝三角的實現

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Soulation {public static void main(String[] args) {Scanner sc=new Scanner(System.in);System.out.println("請輸入");int input=sc.nextInt();List<List<Integer>> list=new ArrayList<>();//第一行的導入List<Integer> arr=new ArrayList<>();arr.add(1);list.add(arr);//從第二行開始，進行計算、for(int i=1;i<input;i++){List<Integer> curRow=new ArrayList<>();curRow.add(1);List<Integer> prevRow=list.get(i-1);for(int j=1;j<i;j++){int val=prevRow.get(j)+prevRow.get(j-1);}curRow.add(1);list.add(curRow);}}
}

四。鏈表：

在介紹鏈表之前，先說一下ArrayList的缺點；當在ArrayList任意位置進行刪除元素或者增加元素的時候，就需要將所有元素進行前移或者后移，這樣時間復雜度就是O(n)，效率非常低，因此涉及到數據的大量插入和刪除的操作就不太適合ArrayList了，因此引入了鏈表來解決這個問題

鏈表是一種物理存儲上非連續的存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接的次序進行實現的（物理上是不連續的，但是邏輯上是連續的）

圖示：

五。無頭單向鏈表的實現

接口：

public interface SingleLinkedList {public void add(int data);//頭插法public void addLast(int data);//尾插法public void addIndex(int index,int data);//把data插入到index位置public boolean contains(int key);//鏈表中是否存在數據keypublic void remove(int key);//刪除第一次出現key數據的節點public void display();//展示鏈表中所有的元素
}

接口的實現：

public class SingleList implements SingleLinkedList{static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val=val;}}public ListNode head;@Overridepublic void add(int data) {ListNode node=new ListNode(data);if(this.head==null){head=node;}else {node.next=head;head=node;}}@Overridepublic void addLast(int data) {ListNode node=new ListNode(data);ListNode cur=head;if(head==null){head=node;}else{while(cur.next!=null){cur=cur.next;}cur.next=node;}}@Overridepublic void addIndex(int index, int data) {ListNode node=new ListNode(data);int count=0;ListNode cur=head;if(head==null){head=node;}else{while(cur.next!=null){if(count==index-1){ListNode hi=cur.next;cur.next=node;node.next=hi;break;}count++;}}}@Overridepublic boolean contains(int key) {ListNode cur=head;if(head==null){return false;}else{while(cur.next!=null){if(cur.val==key){return true;}cur=cur.next;}}return false;}@Overridepublic void remove(int key) {ListNode cur=head;ListNode last=head;if(head.val==key){head=head.next;}//當要刪除的值是鏈表的第一位的時候while(cur.next!=null){cur=cur.next;if(cur.val==key){last.next=cur.next;}last=last.next;}}@Overridepublic void display() {ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}}
}

主函數：

public class Main {public static void main(String[] args) {SingleList singleList=new SingleList();singleList.addLast(12);singleList.addLast(23);singleList.addLast(34);singleList.addLast(45);singleList.addIndex(1,2);singleList.display();System.out.println(singleList.contains(2));singleList.remove(23);singleList.display();}
}

以上就是單鏈表的增刪查所有的代碼，大家可以嘗試自己寫一遍

六。LinkedList的使用

1.LinkedList介紹：

LinkedList本質上是一個雙向鏈表，由于鏈表沒有將元素存儲在連續的空間之中，元素存儲在單獨的節點之中，然后通過引用節點將節點連接起來了，因此在插入或刪除元素的時候，不需要搬移元素，效率較高

2.LinkedList的構造：

List<Integer> list1=new LinkedList<>();

3.LinkedList的其他方法的介紹：

list1.add(45);//尾插45
list1.add(3,10);//在3這個位置插入10這個數字
list1.remove(2);//刪除2位置這個元素
list1.get(2);//獲取下標為2的元素的值
list1.set(2,199);//把下標為2的位置的值改為199
list1.contains(199);//查看此鏈表中是否含有199這個數字
list1.indexOf(199);//返回這個鏈表中第一次出現199這個元素的下標

4.LinkedList的遍歷：

法一：

System.out.println(list);

法二：

for(int i=0;i<list.size;i++){System.out.println(list.get(i));
}

七。ArrayList與LinkedList的區別

不同點	ArrayList	LinkedList
存儲空間上	物理上連續	邏輯上連續，但是物理上不一定連續
隨機訪問	支持	不支持
頭插	需要搬移元素，效率低，O（n）	只用修改引用的指向，空間復雜讀：O（1）
插入	空間不夠時可以進行擴容	沒有容量大概念
應用場景	元素高效存儲+頻繁訪問	任意位置刪除添加頻繁