java數(shù)據(jù)結構基礎:線性表
前言
其實線性表在生活中和棧的結構差不多。昨天總結了一篇單鏈表,也是線性表的一種。
今天用另一種寫法來控制指針的移動實現(xiàn)數(shù)據(jù)的順序存儲結構。
需求分析
首先要明確,這種順序存儲結構的線性表底層用什么。根據(jù)之前查看過的源碼來看,list一般都是以數(shù)組為底層。我們也不例外。
其次,我們還得去定義好線性表的長度,以及每個元素的指針。
private Object[] arr; // 底層的結構 private int index = -1; // 代表元素的索引位置 private int size; // 當前線性表的長度 private int LinearListLength = 4; // 線性表的默認長度
我們這兒只演示添加、刪除、獲取指定位置、獲取全部以及判斷是否為空這五種形式。
編碼
add方法
add方法為向線性表中添加元素,需要傳入一個泛型參數(shù)。實現(xiàn)思路是讓index+1然后把index賦值給數(shù)組得到索引區(qū)域,再讓size+1
總體設計比較簡單,看代碼。
public E add(E item) { // 先初始化線性表 capacity(); // 初始化完成后先把index指針后移一位,也就是+1 // 后移一位之后將要添加的元素賦值到數(shù)組中 this.arr[++index] = item; System.out.println(index); // 添加完成后長度+1 this.size++; return item; }
getIndex方法
getIndex方法主要是用來獲取指定位置的元素,這個就很簡單了,因為底層是數(shù)組,所以我們可以直接用數(shù)組的索引去獲取。
public E getIndex(int index) { return (E) this.arr[index]; }
pop方法
pop方法作用是刪除指定位置的元素。需要傳入一個int類型的索引。由于特殊性,我們必須得借用上面的獲取指定位置的元素的方法來實現(xiàn)這一步驟。
在元素刪除后,通過遍歷循環(huán)去將index位置向前移動一位。具體代碼如下:
/** * 刪除指定位置的元素 */ public E pop(int index) { E e = getIndex(index); if (e != null) { for (int i = index; i < size; i++) { arr[i] = arr[i + 1]; } this.size--; return e; } else { return null; } }
insert方法
insert方法需要傳入兩個參數(shù),一個int類型的索引值,一個泛型數(shù)據(jù)。在指定位置插入該泛型值,然后將后面的值全部后移一位。
public E insert(int index, E item) { System.out.println(size); for (int i = index; i < size; i++) { arr[i + 1] = arr[i]; } arr[index] = item; this.size++; return item; }
getAll
這個方法不用我多說了,一個簡單的遍歷循環(huán)
public void getAll() { for (Object o : this.arr) { System.out.println(o); } }
這兒遍歷的Object類型會自動轉化成添加元素時的類型
全部代碼
package com.zxy.xianxingbiao; /** * @Author Zxy * @Date 2021/2/4 16:54 * @Version 1.0 */ import java.util.Arrays; /** * 演示線性表的使用 底層使用數(shù)組 */ public class MyLinearList<E> { private Object[] arr; // 底層的結構 private int index = -1; // 代表元素的索引位置 private int size; // 當前線性表的長度 private int LinearListLength = 4; // 線性表的默認長度 /** * 判斷線性表是否為空 */ public boolean empty() { return this.size == 0 ? true : false; } /** * 給線性表中添加元素 */ public E add(E item) { // 先初始化線性表 capacity(); // 初始化完成后先把index指針后移一位,也就是+1 // 后移一位之后將要添加的元素賦值到數(shù)組中 this.arr[++index] = item; System.out.println(index); // 添加完成后長度+1 this.size++; return item; } /** * 在指定位置插入元素 */ public E insert(int index, E item) { System.out.println(size); for (int i = index; i < size; i++) { arr[i + 1] = arr[i]; } arr[index] = item; this.size++; return item; } /** * 獲取指定位置的元素 */ public E getIndex(int index) { return (E) this.arr[index]; } /** * 刪除指定位置的元素 */ public E pop(int index) { E e = getIndex(index); if (e != null) { for (int i = index; i < size; i++) { arr[i] = arr[i + 1]; } this.size--; return e; } else { return null; } } /** * 獲取全部的元素 */ public void getAll() { for (Object o : this.arr) { System.out.println(o); } } /** * 數(shù)組初始化或者以1.5倍容量對數(shù)組擴容 */ private void capacity() { // 數(shù)組初始化 if (this.arr == null) { this.arr = new Object[this.LinearListLength]; } // 以1.5倍對數(shù)組擴容 if (this.size - (this.LinearListLength - 1) >= 0) { // 如果當前數(shù)組的元素個數(shù)大于了當前數(shù)組的最后一個索引值 this.LinearListLength = this.LinearListLength + (this.LinearListLength >> 1); // 位運算,讓長度變成原來的1/2 this.arr = Arrays.copyOf(this.arr, this.LinearListLength); // 復制一個新的數(shù)組,用新開辟的長度 } } public static void main(String[] args) { MyLinearList<String> list = new MyLinearList<>(); list.add("a"); list.add("b"); list.add("c"); System.out.println(list.getIndex(1)); list.pop(1); System.out.println(list.getIndex(1)); list.getAll(); } }
總結
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關注腳本之家的更多內(nèi)容!
相關文章
Java 實戰(zhàn)項目之在線點餐系統(tǒng)的實現(xiàn)流程
讀萬卷書不如行萬里路,只學書上的理論是遠遠不夠的,只有在實戰(zhàn)中才能獲得能力的提升,本篇文章手把手帶你用java+SSM+jsp+mysql+maven實現(xiàn)在線點餐系統(tǒng),大家可以在過程中查缺補漏,提升水平2021-11-11Java啟動參數(shù)(-,?-X,?-XX參數(shù))的使用
本文主要介紹了Java啟動參數(shù)(-,?-X,?-XX參數(shù))的使用,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-06-06使用IntelliJ IDEA 進行代碼對比的方法(兩種方法)
這篇文章給大家?guī)砹藘煞NIntelliJ IDEA 進行代碼對比的方法,非常不錯,具有參考借鑒價值,需要的朋友可以參考下2018-01-01SpringCloud?LoadBalancerClient?負載均衡原理解析
LoadBalancerClient?是?SpringCloud?提供的一種負載均衡客戶端,Ribbon?負載均衡組件內(nèi)部也是集成了?LoadBalancerClient?來實現(xiàn)負載均衡,本文給大家深入解析?LoadBalancerClient?接口源碼,感興趣的朋友跟隨小編一起看看吧2022-02-02