Java數(shù)據(jù)結(jié)構(gòu)之鏈表(動(dòng)力節(jié)點(diǎn)之Java學(xué)院整理)
更新時(shí)間：2017年04月14日 10:01:29 投稿：mrr
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之鏈表(動(dòng)力節(jié)點(diǎn)之Java學(xué)院整理)的相關(guān)資料,需要的朋友可以參考下
單鏈表：
insertFirst：在表頭插入一個(gè)新的鏈接點(diǎn)，時(shí)間復(fù)雜度為O(1)
deleteFirst：刪除表頭的鏈接點(diǎn)，時(shí)間復(fù)雜度為O(1)
find：查找包含指定關(guān)鍵字的鏈接點(diǎn)，由于需要遍歷查找，平均需要查找N/2次，即O(N)
remove：刪除包含指定關(guān)鍵字的鏈接點(diǎn)，由于需要遍歷查找，平均需要查找N/2次，即O(N)
public class LinkedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
data.next = first;
first = data;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty!");
Data temp = first;
first = first.next;
return temp.obj;
}
public Object find(Object obj) throws Exception{
if(first == null)
throw new Exception("LinkedList is empty!");
Data cur = first;
while(cur != null){
if(cur.obj.equals(obj)){
return cur.obj;
}
cur = cur.next;
}
return null;
}
public void remove(Object obj) throws Exception{
if(first == null)
throw new Exception("LinkedList is empty!");
if(first.obj.equals(obj)){
first = first.next;
}else{
Data pre = first;
Data cur = first.next;
while(cur != null){
if(cur.obj.equals(obj)){
pre.next = cur.next;
}
pre = cur;
cur = cur.next;
}
}
}
public boolean isEmpty(){
return (first == null);
}
public void display(){
if(first == null)
System.out.println("empty");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception {
LinkedList ll = new LinkedList();
ll.insertFirst(4);
ll.insertFirst(3);
ll.insertFirst(2);
ll.insertFirst(1);
ll.display();
ll.deleteFirst();
ll.display();
ll.remove(3);
ll.display();
System.out.println(ll.find(1));
System.out.println(ll.find(4));
}
}
1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2 -> 4 -> null 4
雙端鏈表(不是雙向鏈表)：
與單向鏈表的不同之處在保存有對(duì)最后一個(gè)鏈接點(diǎn)的引用(last)
insertFirst：在表頭插入一個(gè)新的鏈接點(diǎn)，時(shí)間復(fù)雜度O(1)
insertLast：在表尾插入一個(gè)新的鏈接點(diǎn)，時(shí)間復(fù)雜度O(1)
deleteFirst：刪除表頭的鏈接點(diǎn)，時(shí)間復(fù)雜度O(1)
deleteLast:：刪除表尾的鏈接點(diǎn)，由于只保存了表尾的鏈接點(diǎn)，而沒有保存表尾的前一個(gè)鏈接點(diǎn)(這里就體現(xiàn)出雙向鏈表的優(yōu)勢(shì)了)，所以在刪除表尾鏈接點(diǎn)時(shí)需要遍歷以找到表尾鏈接點(diǎn)的前一個(gè)鏈接點(diǎn)，需查找N-1次，也就是O(N)
有了這幾個(gè)方法就可以用雙端鏈表來實(shí)現(xiàn)一個(gè)隊(duì)列了
public class FirstLastList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
private Data last = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
if(first == null)
last = data;
data.next = first;
first = data;
}
public void insertLast(Object obj){
Data data = new Data(obj);
if(first == null){
first = data;
}else{
last.next = data;
}
last = data;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty");
Data temp = first;
if(first.next == null)
last = null;
first = first.next;
return temp.obj;
}
public void deleteLast() throws Exception{
if(first == null)
throw new Exception("empty");
if(first.next == null){
first = null;
last = null;
}else{
Data temp = first;
while(temp.next != null){
if(temp.next == last){
last = temp;
last.next = null;
break;
}
temp = temp.next;
}
}
}
public void display(){
if(first == null)
System.out.println("empty");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception {
FirstLastList fll = new FirstLastList();
fll.insertFirst(2);
fll.insertFirst(1);
fll.display();
fll.insertLast(3);
fll.display();
fll.deleteFirst();
fll.display();
fll.deleteLast();
fll.display();
}
}
1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 3 -> 2 ->
有序鏈表：
鏈表中的數(shù)據(jù)按從小到大排列
public class SortedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insert(Object obj){
Data data = new Data(obj);
Data pre = null;
Data cur = first;
while(cur != null && (Integer.valueOf(data.obj.toString())
.intValue() > Integer.valueOf(cur.obj.toString())
.intValue())){
pre = cur;
cur = cur.next;
}
if(pre == null)
first = data;
else
pre.next = data;
data.next = cur;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty!");
Data temp = first;
first = first.next;
return temp.obj;
}
public void display(){
if(first == null)
System.out.println("empty");
System.out.print("first -> last : ");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception{
SortedList sl = new SortedList();
sl.insert(80);
sl.insert(2);
sl.insert(100);
sl.display();
System.out.println(sl.deleteFirst());
sl.insert(33);
sl.display();
sl.insert(99);
sl.display();
}
}
first -> last : 2 -> 80 -> 100 -> 2 first -> last : 33 -> 80 -> 100 -> first -> last : 33 -> 80 -> 99 -> 100 ->
表的插入和刪除平均需要比較N/2次，即O(N)，但是獲取最小數(shù)據(jù)項(xiàng)只需O(1)，因?yàn)槠涫冀K處于表頭，對(duì)頻繁操作最小數(shù)據(jù)項(xiàng)的應(yīng)用，可以考慮使用有序鏈表實(shí)現(xiàn)，如：優(yōu)先級(jí)隊(duì)列和數(shù)組相比，鏈表的優(yōu)勢(shì)在于長(zhǎng)度不受限制，并且在進(jìn)行插入和刪除操作時(shí)，不需要移動(dòng)數(shù)據(jù)項(xiàng)，故盡管某些操作的時(shí)間復(fù)雜度與數(shù)組想同，實(shí)際效率上還是比數(shù)組要高很多。劣勢(shì)在于隨機(jī)訪問，無法像數(shù)組那樣直接通過下標(biāo)找到特定的數(shù)據(jù)項(xiàng) 。
以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)之鏈表(動(dòng)力節(jié)點(diǎn)之Java學(xué)院整理)，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
您可能感興趣的文章:
- Java數(shù)據(jù)結(jié)構(gòu)之鏈表詳解
- Java數(shù)據(jù)結(jié)構(gòu)之單鏈表詳解
- Java 單鏈表數(shù)據(jù)結(jié)構(gòu)的增刪改查教程
- Java數(shù)據(jù)結(jié)構(gòu)之鏈表、棧、隊(duì)列、樹的實(shí)現(xiàn)方法示例
- Java描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之鏈表的增刪改查詳解
- Java數(shù)據(jù)結(jié)構(gòu)之簡(jiǎn)單鏈表的定義與實(shí)現(xiàn)方法示例
- Java數(shù)據(jù)結(jié)構(gòu)之雙端鏈表原理與實(shí)現(xiàn)方法
- java 數(shù)據(jù)結(jié)構(gòu)單鏈表的實(shí)現(xiàn)
- 詳解java數(shù)據(jù)結(jié)構(gòu)與算法之雙鏈表設(shè)計(jì)與實(shí)現(xiàn)
- java 數(shù)據(jù)結(jié)構(gòu)之刪除鏈表中的元素實(shí)例代碼
- JAVA 數(shù)據(jù)結(jié)構(gòu)鏈表操作循環(huán)鏈表
- Java 數(shù)據(jù)結(jié)構(gòu)鏈表操作實(shí)現(xiàn)代碼
- Java模擬有序鏈表數(shù)據(jù)結(jié)構(gòu)的示例
- Java模擬單鏈表和雙端鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)例講解
- java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)雙向鏈表的示例
- java實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)單鏈表示例(java單鏈表)
- Java數(shù)據(jù)結(jié)構(gòu)之鏈表的增刪查改詳解
相關(guān)文章
mybatis 一對(duì)多嵌套查詢的實(shí)現(xiàn)
本文主要介紹了mybatis 一對(duì)多嵌套查詢的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-07-07
淺談springboot項(xiàng)目中定時(shí)任務(wù)如何優(yōu)雅退出
這篇文章主要介紹了淺談springboot項(xiàng)目中定時(shí)任務(wù)如何優(yōu)雅退出？具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-09-09
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)按層遍歷二叉樹，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
通過Java計(jì)算文件的MD5值實(shí)現(xiàn)方式
本文將詳細(xì)介紹如何使用Java語言來計(jì)算文件的MD5值,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2025-04-04 
Spring Boot是一個(gè)命令行工具，用于使用Spring進(jìn)行快速原型搭建。本文重點(diǎn)給大家介紹Spring Boot CLI安裝教程，感興趣的朋友參考下吧
2017-08-08 
這篇文章主要為大家詳細(xì)介紹了Java的Collection集合的常用方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-02-02 
SpringSecurity多認(rèn)證器配置多模式登錄自定義認(rèn)證器方式
這篇文章主要介紹了SpringSecurity多認(rèn)證器配置多模式登錄自定義認(rèn)證器方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2025-04-04 
后端如何接收格式為x-www-form-urlencoded的數(shù)據(jù)
x-www-form-urlencoded格式是一種常見的HTTP請(qǐng)求數(shù)據(jù)格式,它將請(qǐng)求參數(shù)編碼為鍵值對(duì)的形式,以便于傳輸和解析,下面這篇文章主要給大家介紹了關(guān)于后端如何接收格式為x-www-form-urlencoded的數(shù)據(jù),需要的朋友可以參考下
2023-05-05 
Spring boot基于ScheduledFuture實(shí)現(xiàn)定時(shí)任務(wù)
這篇文章主要介紹了Spring boot基于ScheduledFuture實(shí)現(xiàn)定時(shí)任務(wù),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-06-06