android知識鞏固(一.線性數(shù)據(jù)結(jié)構(gòu))

數(shù)據(jù)結(jié)構(gòu)(data structure):是計(jì)算機(jī)中存儲，組織數(shù)據(jù)的方式

1.前言

數(shù)據(jù)結(jié)構(gòu)是指相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合蔬顾。通常情況下,數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān),精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率

2.目錄

目錄.png

3.數(shù)據(jù)結(jié)構(gòu)

3.1.數(shù)組

3.1.1.描述

數(shù)組(Array)是一種復(fù)合型數(shù)據(jù)類型,由一系列相同的元素(Element)組成

3.1.2.特性

數(shù)組分為基本類型數(shù)據(jù)和引用類型數(shù)組

由連續(xù)的內(nèi)存空間存儲,查找可直接通過索引定位,效率高,增刪會涉及到數(shù)組的復(fù)制,效率較低

3.1.3.示例代碼

//創(chuàng)建數(shù)組的三種方式(可存儲基本數(shù)據(jù)類型和對象類型)
//靜態(tài)方式創(chuàng)建1
int[] array1 = {1,2,3};
//靜態(tài)方式創(chuàng)建2
int[] array2 = new int[]{1,2,3};
//動(dòng)態(tài)創(chuàng)建
int[] arrayValue3 = new int[5];
Integer[] arrayObject3 = new Integer[5];
System.out.println("基本數(shù)據(jù)類型數(shù)組arrayValue3：" + Arrays.toString(arrayValue3));
System.out.println("對象類型數(shù)組arrayObject3：" + Arrays.toString(arrayObject3));
System.out.println("原始的數(shù)組array1：" + Arrays.toString(array1));

//優(yōu)勢
//修改宴偿，賦值
array1[1] = 4;
//取值 超出長度時(shí)會報(bào)數(shù)組下標(biāo)越界異常
int a1 = array1[1];
System.out.println("修改后的數(shù)組array1：" + Arrays.toString(array1));

//劣勢：刪除時(shí)需數(shù)組的copy，且易產(chǎn)生碎片
//刪除(刪除索引為1的數(shù)據(jù))
//創(chuàng)建新數(shù)組存儲數(shù)據(jù)
int[] array4 = new int[array1.length - 1];
for (int i = 0; i < array4.length; i++) {
    if (i < 1) {
        array4[i] = array1[I];
    } else {
        array4[i] = array1[i + 1];
    }
}
array1 = array4;
System.out.println("刪除索引為1的數(shù)據(jù)后的數(shù)組array1：" + Arrays.toString(array1));
//插入(在索引1處插入數(shù)據(jù)5) 擴(kuò)容時(shí)需數(shù)組復(fù)制
//數(shù)組容量固定的話需創(chuàng)建新數(shù)組擴(kuò)容接受
int[] array5 = new int[array1.length + 1];
for (int i = 0; i < array5.length; i++) {
    if (i < 1) {
        array5[i] = array1[I];
    } else if (i == 1) {
        array5[i] = 5;
    } else {
        array5[i] = array1[i - 1];
    }
}
array1 = array5;
System.out.println("在索引為1的數(shù)據(jù)后的數(shù)組array1：" + Arrays.toString(array1));

3.1.4.運(yùn)行結(jié)果

基本數(shù)據(jù)類型數(shù)組arrayValue3：[0, 0, 0, 0, 0]
對象類型數(shù)組arrayObject3：[null, null, null, null, null]
原始的數(shù)組array1：[1, 2, 3]
修改后的數(shù)組array1：[1, 4, 3]
刪除索引為1的數(shù)據(jù)后的數(shù)組array1：[1, 3]
在索引為1的數(shù)據(jù)后的數(shù)組array1：[1, 5, 3]

3.1.5.可變數(shù)組集合(ArrayList)

封裝了數(shù)組插入和刪除在擴(kuò)容和復(fù)制進(jìn)行了優(yōu)化

//可變數(shù)組的集合(具體底層原理在后續(xù)分析)
//創(chuàng)建 只能存儲對象內(nèi)類
ArrayList<Integer> arrayList = new ArrayList();
//添加基本數(shù)據(jù)類型時(shí)會自動(dòng)裝箱(Integer i= 1)
//手動(dòng)裝箱(Integer i = Integer.valueOf(1))
//add時(shí)會涉及到數(shù)組的擴(kuò)容 復(fù)制
arrayList.add(1);
arrayList.add(1);
//索引刪除(刪除是也會涉及數(shù)組的復(fù)制)
arrayList.remove(1);
Integer integer = 1;
//對應(yīng)值刪除(刪除可能存在歧義,不知?jiǎng)h除對應(yīng)值還是索引位置)
//刪除時(shí)會對應(yīng)類型的equals方法
arrayList.remove(integer);
//超出長度時(shí)會報(bào)數(shù)組下標(biāo)越界異常
Integer integer1 = arrayList.get(0);

3.2.棧

3.2.1.描述

棧(stack):只能在棧頂進(jìn)行插入移除的線性表

3.2.2.特性

按照先進(jìn)后出的原則存儲數(shù)據(jù)

存取速度快,但缺乏靈活性

3.2.3.示例代碼

//創(chuàng)建棧 先進(jìn)后出
Stack<Integer> stack = new Stack<>();
//判斷棧是否為空
boolean empty = stack.empty();
//往棧中插入數(shù)據(jù)(插入的新數(shù)據(jù)位于棧頂部)
Integer push = stack.push(1);
//獲取棧頂部元素 為empty報(bào)EmptyStackException
Integer peek = stack.peek();
//獲取棧頂部元素 且從堆棧中移除 為empty報(bào)EmptyStackException
Integer pop = stack.pop();
System.out.println(stack);
//獲取元素在棧中的位置 不同于其它索引 需從1開始 沒有返回-1
int search = stack.search(1);

3.3.隊(duì)列

3.3.1.描述

隊(duì)列(Queue):只能在隊(duì)尾添加,隊(duì)頭刪除的線性表

3.3.2.特性

遵循先進(jìn)先出的原則存儲數(shù)據(jù)

可有數(shù)組和鏈表實(shí)現(xiàn),數(shù)組實(shí)現(xiàn)時(shí),隊(duì)滿可以選擇丟棄或者等待策略

3.3.3.示例代碼

//創(chuàng)建隊(duì)列(LinkedList實(shí)現(xiàn)了Queue,擁有queue的特性)
//特性:先進(jìn)先出
Queue<Integer> queue = new LinkedList<>();
//進(jìn)隊(duì) 往隊(duì)尾插入
queue.offer(1);
//獲取隊(duì)頭元素 不可為empty(empty NoSuchElementException)
Integer element = queue.element();
//獲取隊(duì)頭元素 可以empty(empty返回null)
Integer peek = queue.peek();
//獲取隊(duì)頭元素 并刪除(empty返回null)
Integer poll = queue.poll();
//獲取隊(duì)頭元素 并刪除(empty NoSuchElementException)
Integer remove = queue.remove();

3.4.鏈表

3.4.1.描述

鏈表(LikedList):由結(jié)點(diǎn)和指針引用組成的遞歸數(shù)據(jù)結(jié)構(gòu)

3.4.2.特性

可由不連續(xù)的內(nèi)存空間存儲,創(chuàng)建時(shí)無需指定長度

元素由數(shù)據(jù)和指針組成,指針指向下一個(gè)數(shù)據(jù)的地址,形成鏈表

增刪可操作指針效率較高,查詢需遍歷遍歷效率較低

3.4.3.示例代碼

//創(chuàng)建鏈表(通過指針連接實(shí)現(xiàn),原理后面分析)
LinkedList<Integer> linkedList = new LinkedList<>();
//在鏈表尾部插入數(shù)據(jù) 成功插入返回true
boolean add = linkedList.add(1);
//獲取位置0處的節(jié)點(diǎn)值 越界IndexOutOfBoundsException
//查找時(shí)會根據(jù)下標(biāo)判斷是從頭結(jié)點(diǎn)還是尾結(jié)點(diǎn)遍歷
Integer integer = linkedList.get(0);
//獲取頭結(jié)點(diǎn)的值 empty則NoSuchElementException
Integer first = linkedList.getFirst();
//獲取尾結(jié)點(diǎn)的值 empty則NoSuchElementException
Integer last = linkedList.getLast();
//移除第一個(gè)結(jié)點(diǎn) 越界IndexOutOfBoundsException 返回結(jié)點(diǎn)值
Integer remove = linkedList.remove(0);
//對應(yīng)值的結(jié)點(diǎn)刪除(刪除可能存在歧義,不知?jiǎng)h除對應(yīng)值還是索引位置)
//刪除時(shí)會對應(yīng)類型的equals方法 不存在返回false
boolean remove1 = linkedList.remove(new Integer(1));

4.總結(jié)

本節(jié)主要講述了android中基本數(shù)據(jù)結(jié)構(gòu),涉及一些基本的概念,特性和簡單的使用;下節(jié)我們將繼續(xù)學(xué)習(xí)一些非線性的數(shù)據(jù)結(jié)構(gòu),包括樹,圖,映射表,后續(xù)也會講述常用數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn),方便我們學(xué)習(xí)和工作中使用自如,得心應(yīng)手

代碼地址:github
視頻地址:(鏈接:https://pan.baidu.com/s/1Tci754eI52uFtt1_5s3keA 密碼:4vgf)
下一章:android知識鞏固(二.非線性數(shù)據(jù)結(jié)構(gòu))