Java實現(xiàn)順序表和鏈表結(jié)構(gòu)
前言:
線性表(linear list)是n個具有相同特性的數(shù)據(jù)元素的有限序列。
線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu),常見的線性表:順序表、鏈表、棧、隊列、字符串。
順序表
定義:
用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)(邏輯上連續(xù),物理上也連續(xù))
(1)靜態(tài)順序表:使用定長數(shù)組存儲。
(2)動態(tài)順序表:使用動態(tài)開辟的數(shù)組存儲
【注意】靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了,空間開多了浪費,開少了不夠用,所以相比之下,動態(tài)數(shù)組更為靈活,可根據(jù)需要動態(tài)分配空間大小
實現(xiàn)方法:
增、刪、改、查
增加操作:從頭部插入、從尾部插入、在任意索引位置處插入
刪除操作:根據(jù)索引刪除元素、根據(jù)元素值刪除第一個出現(xiàn)的該元素、根據(jù)元素值刪除所有該值元素
查找操作:根據(jù)元素值查找是否存在某元素、根據(jù)索引下標(biāo)返回該處元素值、根據(jù)元素值返回索引下標(biāo)
修改操作:根據(jù)索引下標(biāo)修改該處元素
代碼實現(xiàn):
public class MyArray { private int[]data; private int size; // 無參構(gòu)造 public MyArray(){ this.data=new int[5]; } // 有參構(gòu)造 public MyArray(int n){ this.data=new int[n]; } // grow方法用于擴充內(nèi)存 private void grow() { int[] newdata= Arrays.copyOf(data,size*2); this.data=newdata; } // toString方法輸出順序表內(nèi)容 public String toString(){ String str="["; for (int i = 0; i <size ; i++) { str+=data[i]; if(i!=size-1){ str+=","; } } str+="]"; return str; } // 尾插法: public void addLast(int value){ if(size== data.length){ grow(); } data[size]=value; size++; } // 頭插法: 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]=value; size++; } // 中間任意位置插入: public void addIndex(int index,int value){ if(size==data.length) grow(); if(index<0||index>size){ System.err.println("插入位置不合理!"); return; } else { for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = value; size++; } } // 查看當(dāng)前數(shù)組中是否存在該元素 public boolean contains(int value){ for (int i = 0; i < size; i++) { if(data[i]==value) return true; } return false; } // 查找當(dāng)前數(shù)組元素對應(yīng)的下標(biāo) public int getIndex(int value){ for (int i = 0; i < size; i++) { if(data[i]==value){ return i; } } return -1; } // 查找數(shù)組下標(biāo)為index的元素 public int getValue(int index) { if (index < 0 || index > size - 1) { System.out.println("輸入下標(biāo)不合理"); return -1; } return data[index]; } // 根據(jù)索引刪除元素,注意將最后一個元素置為0 public void removeIndex(int index){ if(index<0||index>=size){ System.err.println("輸入不合法!"); } for (int i = index; i <size-1; i++) { data[i]=data[i+1]; } size--; data[size]=0; } // 刪除第一個元素值為value的元素 public void removeValueOnce(int value){ int a=getIndex(value); removeIndex(a); } // 刪除所有元素值為value的元素 public void removeValueAll(int value){ for (int i = 0; i < size; i++) { while(i!=size||data[i]==value) removeIndex(i); } } // 根據(jù)索引修改元素 public void recompose(int index,int newValue){ if(index<0||index>=size){ System.err.println("輸入不合法!"); } data[index]=newValue; } }
鏈表
定義:
邏輯上連續(xù),物理上非連續(xù)存儲。
鏈表由一個個節(jié)點組成,每個節(jié)點存儲該節(jié)點處的元素值val 以及下一個節(jié)點的地址next,由地址next實現(xiàn)邏輯上連續(xù)
分類:
分類方式:
(1)單鏈表、雙鏈表
(2)帶虛擬頭節(jié)點、不帶虛擬頭節(jié)點
(3)循環(huán)鏈表、非循環(huán)鏈表
按不同分類方式組合有8種:
非循環(huán)四種:
(1)不帶虛擬頭節(jié)點的單向鏈表(非循環(huán))
(2)帶虛擬頭節(jié)點的單向鏈表(非循環(huán))
(3)不帶虛擬頭節(jié)點的雙向鏈表(非循環(huán))
(4)帶虛擬頭節(jié)點的雙向鏈表(非循環(huán))
循環(huán)四種:
(5)不帶虛擬頭節(jié)點的單向鏈表(循環(huán))
(6)帶虛擬頭節(jié)點的單向鏈表(循環(huán))
(7)不帶虛擬頭節(jié)點的雙向鏈表(循環(huán))
(8)帶虛擬頭節(jié)點的雙向鏈表(循環(huán))
其中:
(1)不帶虛擬頭節(jié)點的單向鏈表(非循環(huán)):結(jié)構(gòu)簡單,一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu),如哈希桶、圖的鄰接表等等。這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多
(7)不帶虛擬頭節(jié)點的雙向鏈表(循環(huán)):在Java的集合框架庫中LinkedList底層實現(xiàn)就是無頭雙向循環(huán)鏈表
實現(xiàn)方法:
增、刪、查、改 和順序表實現(xiàn)方法基本一樣;
唯一注意:帶虛擬頭節(jié)點與不帶虛擬頭節(jié)點相比,帶虛擬頭節(jié)點避免了考慮頭節(jié)點為空的特殊情況
代碼實現(xiàn):
(1)不帶虛擬頭節(jié)點的單鏈表:
class Node { // val表示存儲的數(shù)值,next表示下一個節(jié)點的地址 int val; Node next; // 構(gòu)造方法 public Node(int val) { this.val = val; } } public class SingleList { // size表示節(jié)點個數(shù) // head表示頭節(jié)點 private int size; private Node head; //定義toString方法以輸出鏈表內(nèi)容 public String toString() { String str = ""; Node node = head; while (node != null) { str += node.val; str += "->"; node = node.next; } str += null; return str; } //將判斷輸入的索引是否合法抽象為方法islegal public boolean islegal(int index) { if (index < 0 || index > size) { return false; } else { return true; } } // 頭插法 public void addHead(int value) { Node node = new Node(value); if (head == null) { head = node; } else { node.next = head; head = node; } size++; } // 中間任意位置插入 public void addIndex(int index, int val) { if (!islegal(index)) { System.out.println("輸入數(shù)據(jù)不合法!"); return; } if (index == 0) { addHead(val); return; } Node node = new Node(val); Node pre = head; for (int i = 0; i < index - 1; i++) { pre = pre.next; } node.next = pre.next; pre.next = node; size++; return; } // 尾插法 public void addLast(int val) { if (head == null) { addHead(val); } else { addIndex(size, val); } } // 刪除指定索引位置的元素 public void removeIndex(int index) { if (islegal(index)) { if (index == 0) { Node temp = head; head = head.next; temp.next = null; size--; return; } else { Node pre = head; for (int i = 0; i < index - 1; i++) { pre = pre.next; } Node cur = pre.next; pre.next = cur.next; cur.next = null; size--; } } else { System.out.println("輸入數(shù)據(jù)不合法!"); } } // 根據(jù)元素值刪除元素,且只刪除第一次出現(xiàn)的該元素 public void removeValueOnce(int val) { if (head.next != null && head.val == val) { removeIndex(0); } else { Node pre = head; while (pre.next != null) { if (pre.next.val == val) { pre.next = pre.next.next; pre.next.next = null; size--; return; } pre = pre.next; } } } // 根據(jù)元素值刪除元素,且刪除所有該元素 public void removeValueAll(int val) { while (head.next != null && head.val == val) { Node temp = head; head = head.next; temp = null; size--; } if (head == null) { return; } else { Node pre = head; while (pre.next != null) { if (pre.next.val == val) { pre.next = pre.next.next; size--; return; } else { pre = pre.next; } } } } // 根據(jù)元素值刪除元素,且刪除所有該元素并返回頭節(jié)點(帶虛假節(jié)點) public Node removeValueAllWithDummy(int val) { Node dummyHead = new Node(-1); dummyHead.next = head; Node pre = dummyHead; while (pre.next != null) { if (pre.next.val == val) { Node cur = pre.next; pre.next = cur.next; cur.next = null; size--; } else { pre = pre.next; } } return dummyHead.next; } // 根據(jù)索引查元素值 public int get(int index) { if (islegal(index)) { Node cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; } else { System.out.println("輸入數(shù)據(jù)不合法!"); return -1; } } // 能否查到給定的某元素值(自己寫的,好像很復(fù)雜) public boolean contains(int val) { boolean a = false; if (head == null) { System.out.println("該鏈表為空!"); return false; } else { Node node = head; for (int i = 0; i < size; i++) { if (node.val == val) { a = true; } node = node.next; } } return a; } // 能否查到給定的某元素值,老師寫的方法 public boolean contains2(int val) { for (Node temp = head; temp != null; temp = temp.next) { if (temp.val == val) { return true; } } return false; } // 根據(jù)索引修改元素值 public void set(int index, int newValue) { if (islegal(index)) { Node node = head; for (int i = 0; i < index; i++) { node = node.next; } node.val = newValue; return; } System.out.println("輸入數(shù)據(jù)不合法!"); } }
(2)帶虛擬頭節(jié)點的單鏈表
以在指定索引位置插入元素為例,理解虛擬頭節(jié)點的作用即可
public class SingleListWithDummyHead { Node dummyNode=new Node(-1); int size; // 在指定位置插入元素,因為有虛擬頭節(jié)點故不用考慮index=0的情況,全部為在中間位置插入的情況 public void addIndex(int index,int value){ // 先判斷index是否合法 if(index<0||index>size){ System.out.println("illegal"); return; } Node a=new Node(value); Node pre=dummyNode; for(int i=0;i<index;i++){ pre=pre.next; } a.next=pre.next; pre.next=a; size++; } }
(3)帶虛擬頭節(jié)點的雙鏈表
public class DoubleLinkedList { private int size; private Node dummyHead = new Node(-1); private Node tail; // 定義toString方法用以方便輸出 public String toString() { String s = ""; Node node = dummyHead.next; while (node != null) { s = s + node.val; s = s + "->"; node = node.next; } s += "null"; return s; } // 判斷輸入的索引是否合法 private boolean isRange(int index) { if (index < 0 || index >= size) { System.out.println("輸入不合法!"); return false; } else return true; } // 頭插法 public void addHead(int val) { Node a = new Node(val, dummyHead, dummyHead.next); //鏈表為空 if (dummyHead.next == null) { tail = a; dummyHead.next = a; } // 否則鏈表不為空 else { dummyHead.next.prev = a; dummyHead.next = a; } size++; } // 尾插法 public void addTail(int val) { Node a = new Node(val, tail, null); // 鏈表為空 if (dummyHead.next == null) { dummyHead.next = a; } // 鏈表不為空 else { tail.next = a; } tail = a; size++; } // 中間位置插入 public void addMiddle(int index, int val) { // 判斷插入位置合理否 if (index < 0 || index > size) { System.out.println("輸入不合法!"); } // 頭部插入 else if (index == 0) { addHead(val); } // 尾部插入 else if (index == size) { addTail(val); } // 中間任意位置插入 else { //先找到要插入位置的前一個元素,可另一個方法找該元素 Node a = new Node(val, find(index), find(index).next); find(index).next.prev = a; find(index).next = a; size++; } } // 這里find的方法是找到index位置的前一個節(jié)點元素 public Node find(int index) { Node f = dummyHead; for (int i = 0; i < index; i++) { f = f.next; } return f; } // 根據(jù)索引刪除指定位置的元素 public void removeIndex(int index) { if (index < 0 || index >= size) { System.out.println("輸入不合法!"); return; } else { find(index).next.next.prev = find(index); find(index).next = find(index).next.next; size--; } } // 刪除指定節(jié)點 private void deleteNode(Node node) { // 分治思想,先處理node與左邊節(jié)點,再處理node與右邊節(jié)點 Node pre = node.prev; Node next = node.next; // 處理左邊,因為有虛擬頭節(jié)點,故不用另討論為頭節(jié)點的情況 pre.next = next; node.prev = null; // 處理右邊 if (next == null) { tail = pre; } else { next.prev = pre; node.next = null; } size--; } // 刪除指定元素值(只刪除第一次出現(xiàn)的) public void removeValueOnce(int val) { for (Node a = dummyHead.next; a != null; a = a.next) { if (a.val == val) { deleteNode(a); return; } } System.out.println("鏈表中無該元素故無法刪除"); } public void removeValueAll(int val) { for (Node a = dummyHead.next; a != null; ) { if (a.val == val) { Node b = a.next; deleteNode(a); a = b; } else a = a.next; } } // 根據(jù)索引查找元素值 public int get(int index) { if (isRange(index)) { return find(index).next.val; } else { return -1; } } // 查找是否存在某元素 public boolean contains(int val) { Node a = dummyHead; while (a.next != null) { if (a.next.val == val) { return true; } a = a.next; } return false; } // 修改,將指定位置元素修改為另一值 public void set(int index, int newValue) { if (isRange(index)) { find(index).next.val = newValue; } } } //節(jié)點類 class Node { int val; Node prev; Node next; public Node(int val) { this.val = val; } public Node(int val, Node prev, Node next) { this.val = val; this.prev = prev; this.next = next; } }
順序表 & 鏈表
順序表:
優(yōu)點:空間連續(xù)、支持隨機訪問
缺點:中間或前面部分的插入刪除時間復(fù)雜度O(N)
增容的代價比較大。
鏈表:
優(yōu)點:任意位置插入刪除時間復(fù)雜度為O(1)
沒有增容問題,插入一個開辟一個空間
缺點:以節(jié)點為單位存儲,不支持隨機訪問
總結(jié)
到此這篇關(guān)于Java實現(xiàn)順序表和鏈表結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java順序表和鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java tomcat環(huán)境變量及idea配置解析
這篇文章主要介紹了Java tomcat環(huán)境變量及idea配置解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-12-12關(guān)于SpringBoot mysql數(shù)據(jù)庫時區(qū)問題
在后端開發(fā)過程中經(jīng)常會遇到幾個時區(qū)設(shè)置問題,今天分幾種情況給大家介紹SpringBoot mysql數(shù)據(jù)庫時區(qū)問題,感興趣的朋友跟隨小編一起看看吧2021-06-06SpringCloud負(fù)載均衡實現(xiàn)定向路由詳情
這篇文章主要介紹了SpringCloud負(fù)載均衡實現(xiàn)定向路由詳情,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下2022-08-08IDEA2021.2永久激活碼最新超詳細(xì)(激活到2099)
這篇文章主要介紹了IDEA2021.2永久激活碼,是idea2021版最新激活方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-09-09IntelliJ IDEA像Eclipse一樣打開多個項目的圖文教程
這篇文章主要介紹了IntelliJ IDEA像Eclipse一樣打開多個項目的方法圖文教程講解,需要的朋友可以參考下2018-03-03SpringBoot3整合mybatis-plus的實現(xiàn)
MyBatis-Plus是一個MyBatis的增強工具,在MyBatis的基礎(chǔ)上只做增強不做改變,本文主要介紹了Mybatis-Plus3.x的具體使用,具有一定的參考價值,感興趣的可以了解一下2023-10-10SpringBoot整合liquibase的實現(xiàn)方法
這篇文章主要介紹了SpringBoot整合liquibase的實現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08