Java-數構鏈表

1.鏈表

1.1鏈表的概念和結構

鏈表是一種物理存儲結構上非連續存儲結構，數據元素的邏輯順序是通過鏈表中引用鏈接次序實現的。

這里大多討論無頭單向非循環鏈表。這種結構，結構簡單，一般與其他數據結構結合，作為其他數據結構的子數據。

1.2鏈表的實現

public class MysingleList {static class ListNode{public  int val;//節點的值域public ListNode next;//下一個節點為地址public ListNode(int val){this.val=val;}}public ListNode head;//當前鏈表的頭節點public  void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}}

1.3方法

這里仍然嘗試自己創建方法了解一些基礎的操作

//頭插法public void addFirst(int data){ListNode node=new ListNode(data);node.next=head;head=node;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);ListNode cur=head;if (cur==null){head=node;return ;}while(cur.next!=null){cur=cur.next;}cur.next=node;}//任意位置插入,第一個數據節點為0號下標public void addIndex(int index,int data) {if (index<0||index>size()){System.out.println("位置不合法");return;}if (index==0){addFirst(data);}if (index==size()){addLast(data);}ListNode node = new ListNode(data);ListNode cur=findIndex(index);node.next=cur.next;cur.next=node;}private ListNode findIndex(int index){ListNode cur=head;int count=0;while (cur!=null){cur=cur.next;count++;if (count==index-1){break;}}return cur;}//查找是否包含關鍵字key是否在單鏈表當中public boolean contains(int key){ListNode cur=head;while (cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//刪除第一次出現關鍵字為key的節點public void remove(int key){if (head==null){return;}if (head.val==key){head=head.next;return;}ListNode cur=findKey(key);if(cur==null){System.out.println("沒有對應的數值");return ;}ListNode del=cur.next;cur.next=del.next;}private ListNode findKey(int key){ListNode cur=head;while (cur.next!=null){if (cur.next.val==key){return cur;}cur=cur.next;}return null;}//刪除所有值為key的節點public void removeAllKey(int key){if (head==null){return;}ListNode cur=head.next;ListNode pre=head;while(cur!=null){if(cur.val==key){pre.next=cur.next;cur=cur.next;}else {pre=cur;cur=cur.next;}}if (head.val==key){head=head.next;//需要放在最后不然找不到后面的數據了。}}//得到單鏈表的長度public int size(){int count=0;ListNode cur=head;while(cur!=null){count++;cur=cur.next;}return count;}public void clear() {this.head=null;}public void display() {ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

另外在管理員中使用jps可以顯示當前系統中所有正在運行的 Java 進程的 進程 ID（PID） 和 主類名 或 JAR 包名。jmap語言可以用于查看 Java 進程的內存使用情況、生成堆轉儲（heap dump）等。

這里再補充幾道常見鏈表操作的題目：

876. 鏈表的中間結點

這一題可以使用快慢指針，快指針永遠是慢支針步數的兩倍。

class Solution {public ListNode middleNode(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}
}

206. 反轉鏈表

class Solution {public ListNode reverseList(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curNext=cur.next;//保存下一個節點cur.next=head;head=cur;cur=curNext;}return head;}
}

LCR 027. 回文鏈表

class Solution {public boolean isPalindrome(ListNode head) {ListNode fast=head;ListNode slow=head;//找到中間節點while (fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}//翻轉后半部分的鏈表ListNode cur=slow.next;while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}//判斷回文while(head!=slow){if(head.val!=slow.val){return false;}if(head.next==slow){return true;}head=head.next;slow=slow.next;}return true;}
}

鏈表分割_牛客題霸_牛客網

public ListNode partition(ListNode pHead, int x) {// write code hereListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;//沒有遍歷完 整個鏈表while(cur != null) {if(cur.val < x) {//第一次插入if(bs == null) {bs = be = cur;}else {be.next = cur;be = be.next;}}else {//第一次插入if(as == null) {as = ae = cur;}else {ae.next = cur;ae = ae.next;}}cur = cur.next;}//第一個段 沒有數據if(bs == null) {return as;}be.next = as;//防止 最大的數據 不是最后一個if(as!=null) {ae.next = null;}return bs;}

141. 環形鏈表 - 力扣（LeetCode）

public class Solution {public boolean hasCycle(ListNode head) {if(head==null){return false;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){return true;}}return false;}
}

?160. 相交鏈表 - 力扣（LeetCode）

一定是Y型

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA=0;int lenB=0;ListNode pl=headA;ListNode ps=headB;while(pl!=null){lenA++;pl=pl.next;}while(ps!=null){lenA++;ps=ps.next;}pl=headA;ps=headB;int len=lenA-lenB;if(len<0){pl=headB;ps=headA;len=lenB-lenA;//讓len能夠一定是正數}}//讓最長的鏈表先走差值步while(len>0){pl=pl.next;len--;}//找到相遇的點while(pl!=ps){pl=pl.next;ps=ps.next;}return pl; 
}

?142. 環形鏈表 II - 力扣（LeetCode）

public class Solution {public ListNode detectCycle(ListNode head) {if(head==null){return null;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){break;}}if(fast==null||fast.next==null){return null;}fast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;}
}

2.LinkedList

2.1概念

LinkedList的底層是雙向鏈表結構，由于鏈表沒有將元素儲存在連續空間中，元素存儲在單獨節點中，通過引用將節點鏈接，因此在進行插入和刪除元素的操作的時候，不需要搬移元素，效率較高。

2.2方法

為幫助理解常用方法的底層邏輯，這里再自己對方法進行實現。

public class MyLinkList {//雙向鏈表static class ListNode{private int  val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val=val;}}public ListNode head;public ListNode last;//得到單鏈表的長度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}public void display(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}//查找是否包含關鍵字key是否在單鏈表當中public boolean contains(int key){ListNode cur=head;while(cur!=null){if (cur.val==key){return true;}cur=cur.next;}return false;}//頭插法public void addFirst(int data){ListNode node=new ListNode(data);if (head==null){head=node;last=node;}else{node.next=head;head.prev=node;head=node;}}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if (head==null){head=node;last=node;}else {last.next=node;node.prev=last;last=last.next;}}//任意位置插入,第一個數據節點為0號下標public void addIndex(int index,int data){checkIndex(index);if (index==0){addFirst(data);}if (index==size()){addLast(data);}ListNode cur=findIndex(index);ListNode node=new ListNode(data);node.next=cur.next;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}private void checkIndex(int index){if (index<0||index>size()){throw new IndexOutOfException("index位置不合法");}}private ListNode findIndex(int index){ListNode cur=head;while(index !=0){cur=cur.next;index--;}return cur;}//刪除第一次出現關鍵字為key的節點public void remove(int key){ListNode cur=head;while (cur!=null){if (cur.val==key){if (cur==head){//如果頭節點正好是目標節點head=head.next;//如果只有這一個節點則為空if (head!=null){head.prev=null;}else {last=null;}}else {//中間節點if (cur.next!=null){cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//如果正好是last為目標節點cur.prev.next=cur.next;last=last.prev;}}return ;}else {cur=cur.next;}}}//刪除所有值為key的節點public void removeAllKey(int key){ListNode cur=head;while (cur!=null){if (cur.val==key){if (cur==head){//如果頭節點正好是目標節點head=head.next;//如果只有這一個節點則為空if (head!=null){head.prev=null;}else {last=null;}}else {//中間節點if (cur.next!=null){cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//如果正好是last為目標節點cur.prev.next=cur.next;last=last.prev;}}cur=cur.next;}}}public void clear(){ListNode cur=head;while(cur!=head){ListNode curNext=cur.next;//保存一下cur.prev=null;cur.next=null;cur=curNext;}head=null;last=null;}
}

2.3LinkedList的使用

LinkedList實現了List接口。

1.LinkedList的構造

LinkedList()? ? ? ?--無參構造

public LinkedList(Collection<? extends E> c) --使用其他集合容器中元素構造List
    public static void main(String[] args) {List<Integer>list1=new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);}

?2.4遍歷

 public static void main(String[] args) {List<Integer>list1=new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);for (int x: list1) {System.out.print(x+" ");}System.out.println();ListIterator<Integer>it=list1.listIterator();while (it.hasNext()){System.out.print(it.next()+" ");}System.out.println();ListIterator<Integer>it2=list1.listIterator(list1.size());while (it.hasPrevious()){System.out.print(it.previous()+" ");}System.out.println();}

2.5ArrayList和LinkedList的區別

又可以說是鏈表和順序表的區別

不同點ArrayListLinkedList
存儲空間上物理地址上連續邏輯上連續，但物理地址不一定連續
隨機訪問支持O（1）不支持：O（N）
頭插法

需要搬移元素，效率低

O（N）

只需要修改引用的指向，時間復雜度為

O（1）

插入法空間不夠，需要進行擴容沒有容量
應用場景元素高效存儲，頻繁訪問任意位置插入和刪除頻繁

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/89495.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/89495.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/89495.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Windows系統軟件游戲丟失找不到mgmtapi.dll修復解決方法

Windows系統軟件游戲丟失找不到mgmtapi.dll修復解決方法

在使用電腦系統時經常會出現丟失找不到某些文件的情況&#xff0c;由于很多常用軟件都是采用 Microsoft Visual Studio 編寫的&#xff0c;所以這類軟件的運行需要依賴微軟Visual C運行庫&#xff0c;比如像 QQ、迅雷、Adobe 軟件等等&#xff0c;如果沒有安裝VC運行庫或者安裝…
閱讀更多...
初識C++——開啟新旅途

初識C++——開啟新旅途

從今天開始主包也是掉入C這個深坑&#xff0c;上完課也是跟沒上一樣&#xff0c;所以寫好博客復習還是很重要的&#xff0c;話不多說&#xff0c;進入正題~~1、命名空間(1)namespace的價值與作用在C/C中&#xff0c;變量、函數和后面要學到的類都是大量存在的&#xff0c;這些變…
閱讀更多...
vue2 面試題及詳細答案150道（141 - 150）

vue2 面試題及詳細答案150道（141 - 150）

《前后端面試題》專欄集合了前后端各個知識模塊的面試題&#xff0c;包括html&#xff0c;javascript&#xff0c;css&#xff0c;vue&#xff0c;react&#xff0c;java&#xff0c;Openlayers&#xff0c;leaflet&#xff0c;cesium&#xff0c;mapboxGL&#xff0c;threejs&…
閱讀更多...
第十三章 Go包管理

第十三章 Go包管理

文章目錄使用logurs處理程序日志logrus 常用配置使用viper處理程序配置使用logurs處理程序日志 下載包&#xff0c;在終端執行命令 go get github.com/sirupsen/logrus官方示例 package mainimport (log "github.com/sirupsen/logrus" )func main() {log.WithFiel…
閱讀更多...
EP01：【Python 第一彈】基礎入門知識

EP01：【Python 第一彈】基礎入門知識

一、基礎入門知識 1.1 代碼規范 1.1.1 語句分隔符 ; 換行 1.1.2 格式化 對 Windows 和 Linux 操作系統&#xff0c;快捷鍵是Ctrl Alt L對 macOS 操作系統&#xff0c;快捷鍵是Cmd Option L 1.1.3 注釋 單行注釋 # 這是一行注釋多行注釋 """ 這 是 …
閱讀更多...
實用的文件和文件夾批量重命名工具

實用的文件和文件夾批量重命名工具

在日常工作中&#xff0c;文件和文件夾的命名管理常常讓人頭疼。尤其是面對大量文件時&#xff0c;手動重命名不僅耗時&#xff0c;還容易出錯。今天&#xff0c;我要給大家推薦一款超級實用的工具——OncePower 文件批量重命名&#xff0c;它不僅能批量重命名文件和文件夾&…
閱讀更多...
【Git】報錯：git config --global http.sslBackend “openssl“

【Git】報錯：git config --global http.sslBackend “openssl“

問題解決 報錯&#xff1a;git config --global http.sslBackend “openssl”解決方法&#xff1a; git config --global http.sslBackend "openssl"之后再 push 即可正常提交。 &#x1f50d; 原因分析 ??系統環境不支持 OpenSSL 后端?? Git 在某些平臺&#xf…
閱讀更多...
Redisson RLocalCachedMap 核心參詳解

Redisson RLocalCachedMap 核心參詳解

&#x1f9d1; 博主簡介&#xff1a;CSDN博客專家&#xff0c;歷代文學網&#xff08;PC端可以訪問&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移動端可微信小程序搜索“歷代文學”&#xff09;總架構師&#xff0c;15年工作經驗&#xff0c;精通Java編…
閱讀更多...
AI輔助編程時代的高效規范開發指南：工具、原則與提效策略

AI輔助編程時代的高效規范開發指南：工具、原則與提效策略

引言&#xff1a;AI輔助編程的時代背景與核心挑戰 人工智能在編程領域的應用雖可追溯至20世紀50年代&#xff0c;但近十年實現了革命性突破&#xff0c;推動其從早期的代碼補全工具演進為能理解上下文、生成完整函數乃至項目架構的智能系統。關鍵發展里程碑包括&#xff1a;20…
閱讀更多...
百度網盤TV版1.21.0 |支持倍速播放，大屏云看片

百度網盤TV版1.21.0 |支持倍速播放，大屏云看片

百度網盤TV版是專為智能電視設計的應用程序&#xff0c;讓用戶可以直接在大屏幕上觀看保存在云端的視頻資源。此應用提供了與手機端幾乎相同的功能&#xff0c;包括倍速播放功能&#xff0c;使得用戶可以更方便地享受高清視頻內容。無需繁瑣的操作步驟&#xff0c;即可實現云端…
閱讀更多...
C++控制臺貪吃蛇開發(二)：讓靈蛇舞動起來！

C++控制臺貪吃蛇開發(二)：讓靈蛇舞動起來！

資料合集下載鏈接： ??https://pan.quark.cn/s/472bbdfcd014? 本文將深入講解蛇移動的機制，并帶你一步步實現以下功能： 理解蛇移動的核心算法：為什么蛇的移動是“倒著”更新的？ 用代碼表示方向：如何使用??dx??和??dy??變量優雅地控制方向。 編寫核心??move…
閱讀更多...
Elasticsearch+Logstash+Filebeat+Kibana部署

Elasticsearch+Logstash+Filebeat+Kibana部署

目錄 軟件說明&#xff1a; 架構拓撲 集群模式&#xff1a; 單機模式 環境準備 部署&#xff1a; kibana es logstash filebeat es 檢查能否啟動 logstash 命令設置 es 修改es配置文件 啟用es kibana 修改kibana配置文件&#xff08;方便查看索引&#xff09…
閱讀更多...
GLM（General Language Model，通用語言模型）

GLM（General Language Model，通用語言模型）

&#x1f9e0; 一、GLM是什么&#xff1f;一句話概括 GLM&#xff08;General Language Model&#xff0c;通用語言模型&#xff09;是一個“大腦”&#xff0c;它通過閱讀海量書籍、網頁、對話記錄學會了人類的語言規則&#xff0c;不僅能“聽懂”你說的話&#xff0c;還能“…
閱讀更多...
【科研繪圖系列】R語言繪制顯著性標記的熱圖

【科研繪圖系列】R語言繪制顯著性標記的熱圖

文章目錄 介紹 加載R包 數據下載 導入數據 數據預處理 畫圖 系統信息 參考 介紹 【科研繪圖系列】R語言繪制顯著性標記的熱圖 加載R包 library(ggplot2) library(patchwork)rm(list = ls()) options(stringsAsFactors = F)
閱讀更多...
若依部署項目到服務器

若依部署項目到服務器

目錄 一、環境配置 redis nginx&#xff08;宿主機|dokcer&#xff09; 1.宿主機 2.docker 二、打包jar包 0.查看后端配置 1.打包后端 2.打包前端 三、啟動 1.后端 2.前端 四、以上部署常見命令/錯誤 一、環境配置 之前的課都配過&#xff0c;先看看自己配了沒 看看…
閱讀更多...
零基礎學習性能測試-linux服務器監控：CPU監控

零基礎學習性能測試-linux服務器監控：CPU監控

目錄學習內容與快速應用路徑第一階段&#xff1a;理解 CPU 核心概念 (0.5天)第二階段&#xff1a;掌握核心監控命令與指標 (1-2天)第三階段&#xff1a;識別 CPU 問題與瓶頸 (核心技能)第四階段&#xff1a;整合到性能測試工作流程 (快速應用落地)快速應用到工作中的關鍵策略零…
閱讀更多...
智能Agent場景實戰指南 Day 15：游戲NPC Agent互動設計

智能Agent場景實戰指南 Day 15：游戲NPC Agent互動設計

【智能Agent場景實戰指南 Day 15】游戲NPC Agent互動設計 文章內容 開篇 歡迎來到"智能Agent場景實戰指南"系列的第15天&#xff01;今天我們將深入探討游戲開發中一個極具挑戰性和創新性的領域——游戲NPC Agent互動設計。在當今游戲產業中&#xff0c;玩家對游戲…
閱讀更多...
Vite的優缺點（精簡版）

Vite的優缺點（精簡版）

優點 作為一款前端構建工具&#xff0c;它的核心特點是“快”&#xff0c;并且充分利用了現代瀏覽器對ES Modules的原生支持&#xff0c;一切圍繞這一點展開 快啟動&#xff1a;通過ES Modules&#xff0c;它省去了打包整個應用的時間&#xff0c;可以直接在瀏覽器中加載模塊&a…
閱讀更多...
【深度學習】神經網絡-part2

【深度學習】神經網絡-part2

一、數據加載器 數據集和加載器 1.1構建數據類 1.1.1 Dataset類 Dataset是一個抽象類&#xff0c;是所有自定義數據集應該繼承的基類。它定義了數據集必須實現的方法。 必須實現的方法 __len__: 返回數據集的大小 __getitem__: 支持整數索引&#xff0c;返回對應的樣本 …
閱讀更多...
nextjs+react項目如何代理本地請求解決跨域

nextjs+react項目如何代理本地請求解決跨域

在 Next.js React 項目中解決本地開發跨域問題&#xff0c;可以通過以下幾種方式實現代理請求&#xff1a;方案1&#xff1a;使用 Next.js 內置的 Rewrites 功能&#xff08;推薦&#xff09; 1. 修改 next.config.js /** type {import(next).NextConfig} */ const nextConfig…
閱讀更多...
最新文章

Copyright @ 2022~2023