1.線性表
1.1線性表的概念
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列…
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結(jié)構(gòu)的形式存儲。
如圖所示：
2.順序表
2.1順序表的概念
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
2.2順序表的實現(xiàn)
因為順序表存儲數(shù)據(jù)是在一段連續(xù)的物理地址依次存儲的線性結(jié)構(gòu)，我們一般采用數(shù)組的形式來進行存儲，通過在數(shù)組中完成數(shù)據(jù)的增刪查改的操作。
2.2.1數(shù)組的創(chuàng)建
public class MyArrayList {
//定義一個未被初始化的數(shù)組elem
public int[] elem;
//定義一個記錄該數(shù)組存了多少容量
public int size;
//將該容量設(shè)置為一個常量，為了到后面調(diào)構(gòu)造方法的時候初始化數(shù)組的大小
public static final int DEFAULT_CAPACITY = 5;
//調(diào)用構(gòu)造函數(shù)的時候初始化數(shù)組的大小，而size成員變量不需要初始化，因為一開始未被初始化，默認初始化為0.
public MyArrayList() {
this.elem = new int[DEFAULT_CAPACITY];
}
}
2.2.2提供一些接口
public interface Ilist {
// 新增元素,默認在數(shù)組最后新增
void add(int data);
// 在 pos 位置新增元素
void add(int pos, int data);
// 判定是否包含某個元素
boolean contains(int toFind);
// 查找某個元素對應(yīng)的位置
int indexOf(int toFind);
// 獲取 pos 位置的元素
int get(int pos);
// 給 pos 位置的元素設(shè)為 value
void set(int pos, int value);
//刪除第一次出現(xiàn)的關(guān)鍵字key
void remove(int toRemove);
// 獲取順序表長度
int size();
// 清空順序表
void clear();
//打印這個數(shù)組的內(nèi)容
void display();
//判斷是否空間滿了
boolean isFuul();
boolean isEmpty();
}
2.2.3提供一些異常類
1.判斷數(shù)組中是否為空的異常
2.判斷下標是否合法的異常
//1.判斷數(shù)組中是否為空的異常
public class EmptyException extends RuntimeException{
public EmptyException() {
}
public EmptyException(String message) {
super(message);
}
}
//2.判斷下標是否合法的異常
public class PosException extends RuntimeException{
public PosException() {
}
public PosException(String message) {
super(message);
}
}
2.3接口的實現(xiàn)(對數(shù)組增刪查改操作)
2.3.1 新增元素,(默認在數(shù)組最后新增)
//往最后位置插入數(shù)據(jù)
public void add(int data) {
//判斷空間是否滿了，如果滿了就擴容2倍
if(isFuul()) {
elem = Arrays.copyOf(elem,2*elem.length);
System.out.println("擴容成功");
}
elem[size] = data;
size++;
}
@Override
public boolean isFuul() {
return size == elem.length;
}
2.3.2打印數(shù)組全部內(nèi)容
//打印數(shù)組全部內(nèi)容
@Override
public void display() {
for (int i = 0; i < size; i++) {
System.out.println(elem[i]);
}
}
2.3.3在 pos 位置新增元素
// 在 pos 位置新增元素
@Override
public void add(int pos, int data) {
//判斷pos是否合法
checkPosOfAdd(pos);
//判斷是否需要擴容
if(isFuul()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
//最后在pos位置插入新元素
for(int i=size-1;i>=pos;i--) {
elem[i+1] = elem[i];
}
elem[pos] = data;
size++;
}
//判斷pos是否合法的方法，在順序表中插入數(shù)據(jù)的時候，插入的位置前面必須要有數(shù)據(jù)。
private void checkPosOfAdd (int pos) {
if(pos<0 || pos>size) {
throw new PosException("pos的位置不合法:"+pos);
}
}
2.3.4判定是否包含某個元素
// 判定是否包含某個元素
//直接遍歷數(shù)組然后一一和目標元素比較，有就返回true，沒有就返回false。
@Override
public boolean contains(int toFind) {
for(int i=0;i< elem.length;i++) {
if(toFind == elem[i]) {
return true;
}
}
return false;
}
2.3.5查找某個元素對應(yīng)的位置
// 查找某個元素對應(yīng)的位置
//直接遍歷數(shù)組然后一一和目標元素比較，有就返回對應(yīng)的下標，沒有就返回-1。
@Override
public int indexOf(int toFind) {
for(int i=0;i< elem.length;i++) {
if(toFind == elem[i]) {
return i;
}
}
return -1;
}
2.3.6 獲取 pos 位置的元素 如果順序表為空返回-1或者拋出異常，不為空返回pos位置的元素
// 獲取 pos 位置的元素 如果順序表為空返回-1或者拋出異常，不為空返回pos位置的元素
@Override
public int get(int pos) {
//判斷pos位置是否合法
checkPosOfGet(pos);
//判斷這個順序表是否為空
if(isEmpty()) {
throw new EmptyException("順序表為空");
}
return elem[pos];
}
2.3.7判斷順序表是否為空
//判斷順序表是否為空
@Override
public boolean isEmpty() {
return size == 0;
}
//判斷pos合不合法的方法
private void checkPosOfGet (int pos) {
if(pos<0 || pos>size) {
throw new PosException("pos的位置不合法:"+pos);
}
}
2.3.8給 pos 位置的元素設(shè)為 value
// 給 pos 位置的元素設(shè)為 value
@Override
public void set(int pos, int value) {
//判斷pos是否合法
checkPosOfSet(pos);
//判斷順序表是否為空
if(isEmpty()) {
throw new EmptyException("順序表為空");
}
//修改pos位置的內(nèi)容
this.elem[pos] = value;
}
private void checkPosOfSet (int pos) {
if (pos < 0 || pos > size) {
throw new PosException("pos的位置不合法:" + pos);
}
}
2.3.9刪除元素 如果順序表中為空，則刪不了，之后我們先找到我們要刪的這個數(shù)。
//刪除元素 如果順序表中為空，則刪不了，之后我們先找到我們要刪的這個數(shù)。
@Override
public void remove(int toRemove) {
//判斷順序表中是否為空
if(isEmpty()) {
throw new EmptyException("順序表為空");
}
//找到我們需要刪的這個數(shù)
int indexof = indexOf(toRemove);
for(int i = indexof;i<size-1;i++) {
elem[i] = elem[i+1];
}
size--;
}
2.3.10獲取順序表長度 直接返回size
// 獲取順序表長度 直接返回size
@Override
public int size() {
return this.size;
}
2.3.11清空順序表
// 清空順序表
@Override
public void clear() {
size = 0;
}
3.ArrayList簡介
在集合框架中，ArrayList是一個普通的類，實現(xiàn)了List接口，具體框架圖如下：
【說明】
- ArrayList是以泛型方式實現(xiàn)的，使用時必須要先實例化
- ArrayList實現(xiàn)了RandomAccess接口，表明ArrayList支持隨機訪問
- ArrayList實現(xiàn)了Cloneable接口，表明ArrayList是可以clone的
- ArrayList實現(xiàn)了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList
- ArrayList底層是一段連續(xù)的空間，并且可以動態(tài)擴容，是一個動態(tài)類型的順序表
4. ArrayList使用
4.1ArrayList的構(gòu)造
1.ArrayList() 無參構(gòu)造：
List<Integer> list1 = new ArrayList<>();
2.ArrayList(int initialCapacity)指定順序表初始容量:
List<Integer> list2 = new ArrayList<>(5);
3.ArrayList(Collection<? extends E> c) 利用其他 Collection 構(gòu)建 ArrayList:相當于傳入其他的ArrayList順序表，使得這個順序表的大小容量與數(shù)據(jù)類型和傳入的順序表是一致的。
List<Integer> list3 = new ArrayList<>(list2);
4.2 ArrayList的方法
4.2.1尾插法
public static void main(String[] args) {
List<Integer> list2 = new ArrayList<>(5);
list2.add(1);
list2.add(2);
list2.add(3);
list2.add(4);
list2.add(5);
System.out.println(list2);
}
結(jié)果顯示：
4.2.2將目標值插到指定index位置
list2.add(1,6);
System.out.println(list2);
結(jié)果顯示：
4.2.3刪除 index 位置元素
list2.remove(2);
System.out.println(list2);
結(jié)果顯示：
4.2.4獲取下標 index 位置元素
System.out.println(list2.get(3));
結(jié)果顯示：
4.3 ArrayList的遍歷
ArrayList 可以使用三方方式遍歷：for循環(huán)+下標、foreach。
1.for循環(huán)+下標：
public static void main(String[] args) {
List<Integer> list2 = new ArrayList<>(5);
list2.add(1);
list2.add(2);
list2.add(3);
list2.add(4);
list2.add(5);
for (int i = 0; i < list2.size(); i++) {
System.out.print(list2.get(i)+" ");
}
}
結(jié)果顯示：
2.foreach：
public static void main(String[] args) {
List<Integer> list2 = new ArrayList<>(5);
list2.add(1);
list2.add(2);
list2.add(3);
list2.add(4);
list2.add(5);
System.out.println("foreach循環(huán)下：");
for (Integer integer:list2) {
System.out.print(integer+" ");
}
}
結(jié)果顯示：
最后，ArrayList是一個動態(tài)類型的順序表，不夠空間會自動擴容。文章來源：http://www.zghlxwxcb.cn/news/detail-821003.html
好久沒更新了，在這我向我的老鐵們道個歉，從今天開始更新關(guān)于java的數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，希望大家多多支持。????????????????????????????文章來源地址http://www.zghlxwxcb.cn/news/detail-821003.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】從順序表到ArrayList類的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[java數(shù)據(jù)結(jié)構(gòu)] ArrayList和LinkedList介紹與使用](https://imgs.yssmx.com/Uploads/2024/01/809850-1.png)
![java八股文面試[數(shù)據(jù)結(jié)構(gòu)]——ArrayList和LinkedList區(qū)別](https://imgs.yssmx.com/Uploads/2024/02/666186-1.png)
