Java實現(xiàn)順序表和鏈表結(jié)構(gòu)
更新時間：2022年02月11日 08:46:51 作者：?????*
大家好，本篇文章主要講的是Java實現(xiàn)順序表和鏈表結(jié)構(gòu)，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下
前言：
線性表（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ù)索引下標返回該處元素值、根據(jù)元素值返回索引下標
修改操作：根據(jù)索引下標修改該處元素
代碼實現(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++;
}
}
// 查看當前數(shù)組中是否存在該元素
public boolean contains(int value){
for (int i = 0; i < size; i++) {
if(data[i]==value)
return true;
}
return false;
}
// 查找當前數(shù)組元素對應(yīng)的下標
public int getIndex(int value){
for (int i = 0; i < size; i++) {
if(data[i]==value){
return i;
}
}
return -1;
}
// 查找數(shù)組下標為index的元素
public int getValue(int index) {
if (index < 0 || index > size - 1) {
System.out.println("輸入下標不合理");
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配置解析,文中通過示例代碼介紹的非常詳細，對大家的學(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-06
這篇文章主要給大家介紹了關(guān)于Spring5中WebClient使用方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用Spring5具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11
這篇文章主要介紹了SpringCloud負載均衡實現(xiàn)定向路由詳情，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要介紹了IDEA2021.2永久激活碼，是idea2021版最新激活方法,本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
IntelliJ IDEA像Eclipse一樣打開多個項目的圖文教程
這篇文章主要介紹了IntelliJ IDEA像Eclipse一樣打開多個項目的方法圖文教程講解,需要的朋友可以參考下2018-03-03
SpringBoot3整合mybatis-plus的實現(xiàn)
MyBatis-Plus是一個MyBatis的增強工具,在MyBatis的基礎(chǔ)上只做增強不做改變,本文主要介紹了Mybatis-Plus3.x的具體使用,具有一定的參考價值,感興趣的可以了解一下2023-10-10
這篇文章主要介紹了Spring中的事務(wù)管理,以實例形式詳細分析了事務(wù)的概念與特性以及事物管理的具體用法,需要的朋友可以參考下2014-11-11
這篇文章主要介紹了SpringMVC異步處理的 5 種方式,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
SpringBoot整合liquibase的實現(xiàn)方法
這篇文章主要介紹了SpringBoot整合liquibase的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08