java有链表吗_Java数据结构之链表（Linked List）
1.鏈表(Linked List)介紹
鏈表是有序的列表，但是它在內存存儲結構如下：
2.特點：
鏈表是以節點的方式來存儲,是鏈式存儲
每個節點包含 data 域， next 域：指向下一個節點.
鏈表的各個節點不一定是連續存儲.
鏈表分帶頭節點的鏈表和沒有頭節點的鏈表，根據實際的需求來確定
3.單鏈表介紹
單鏈表(帶頭結點) 邏輯結構示意圖如下：
4.應用示例：
使用帶head頭的單向鏈表實現 –水滸英雄排行榜管理，完成對英雄人物的增刪改查操作
第一種方法在添加英雄時，直接添加到鏈表的尾部
思路分析
添加(創建)
先創建一個head頭節點，表示單鏈表的頭
在添加英雄時，根據排名將英雄插入到指定位置(如果有這個排名，則添加失敗，并給出提示)
遍歷
通過一個輔助變量遍歷，幫助遍歷整個鏈表。
刪除節點
鏈表數據結構實現：
//定義HeroNode ， 每個HeroNode 對象就是一個節點
classHeroNode {public intno; // 排名publicString name;publicString nickname;public HeroNode next; //指向下一個節點//構造器
public HeroNode(intno, String name, String nickname) {this.no =no;this.name =name;this.nickname =nickname;
}//為了顯示方法，我們重新toString
@OverridepublicString toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
輔助管理鏈表類：
需要注意，鏈表維護的表頭節點head 不能動，因此處理時需要一個temp輔助節點找到待刪除節點的前一個節點
//定義SingleLinkedList 管理我們的英雄
classSingleLinkedList {//先初始化一個頭節點, 頭節點不要動, 不存放具體的數據
private HeroNode head = new HeroNode(0, "", "");//返回頭節點
publicHeroNode getHead() {returnhead;
}//添加節點到單向鏈表//思路，當不考慮編號順序時//1. 找到當前鏈表的最后節點//2. 將最后這個節點的next 指向 新的節點
public voidadd(HeroNode heroNode) {//因為head節點不能動，因此我們需要一個輔助遍歷 temp
HeroNode temp =head;//遍歷鏈表，找到最后
while(true) {//找到鏈表的最后
if(temp.next == null) {// break;
}//如果沒有找到最后, 將將temp后移
temp =temp.next;
}//當退出while循環時，temp就指向了鏈表的最后//將最后這個節點的next 指向 新的節點
temp.next =heroNode;
}//第二種方式在添加英雄時，根據排名將英雄插入到指定位置//(如果有這個排名，則添加失敗，并給出提示)
public voidaddByOrder(HeroNode heroNode) {//因為頭節點不能動，因此我們仍然通過一個輔助指針(變量)來幫助找到添加的位置//因為單鏈表，因為我們找的temp 是位于 添加位置的前一個節點，否則插入不了
HeroNode temp =head;boolean flag = false; //flag標志添加的編號是否存在，默認為false
while(true) {if(temp.next == null) {//說明temp已經在鏈表的最后
break; //}if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
break;
}else if (temp.next.no == heroNode.no) {//說明希望添加的heroNode的編號已然存在
flag= true; //說明編號存在
break;
}
temp= temp.next; //后移，遍歷當前鏈表
}//判斷flag 的值
if(flag) { //不能添加，說明編號存在
System.out.printf("準備插入的英雄的編號 %d 已經存在了, 不能加入\n", heroNode.no);
}else{//插入到鏈表中, temp的后面
heroNode.next =temp.next;
temp.next=heroNode;
}
}//修改節點的信息, 根據no編號來修改，即no編號不能改.//說明//1. 根據 newHeroNode 的 no 來修改即可
public voidupdate(HeroNode newHeroNode) {//判斷是否空
if(head.next == null) {
System.out.println("鏈表為空~");return;
}//找到需要修改的節點, 根據no編號//定義一個輔助變量
HeroNode temp =head.next;boolean flag = false; //表示是否找到該節點
while(true) {if (temp == null) {break; //已經遍歷完鏈表
}if(temp.no ==newHeroNode.no) {//找到
flag = true;break;
}
temp=temp.next;
}//根據flag 判斷是否找到要修改的節點
if(flag) {
temp.name=newHeroNode.name;
temp.nickname=newHeroNode.nickname;
}else { //沒有找到
System.out.printf("沒有找到 編號 %d 的節點，不能修改\n", newHeroNode.no);
}
}//刪除節點//思路//1. head 不能動，因此我們需要一個temp輔助節點找到待刪除節點的前一個節點//2. 說明我們在比較時，是temp.next.no 和 需要刪除的節點的no比較
public void del(intno) {
HeroNode temp=head;boolean flag = false; //標志是否找到待刪除節點的
while(true) {if(temp.next == null) { //已經到鏈表的最后
break;
}if(temp.next.no ==no) {//找到的待刪除節點的前一個節點temp
flag = true;break;
}
temp= temp.next; //temp后移，遍歷
}//判斷flag
if(flag) { //找到//可以刪除
temp.next =temp.next.next;
}else{
System.out.printf("要刪除的 %d 節點不存在\n", no);
}
}//顯示鏈表[遍歷]
public voidlist() {//判斷鏈表是否為空
if(head.next == null) {
System.out.println("鏈表為空");return;
}//因為頭節點，不能動，因此我們需要一個輔助變量來遍歷
HeroNode temp =head.next;while(true) {//判斷是否到鏈表最后
if(temp == null) {break;
}//輸出節點的信息
System.out.println(temp);//將temp后移， 一定小心
temp =temp.next;
}
}
}
View Code
【騰訊面試題】單鏈表的反轉
思路：
先定義一個節點reverseHead = new HeroNode();
從頭到尾遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放在新的鏈表reverseHead的最前端
原來的鏈表的head.next = reverseHead.net
代碼實現
//將單鏈表反轉
public static voidreversetList(HeroNode head){//如果當前鏈表為空，或者只有一個節點，無需反轉，直接返回
if(head.next == null || head.next.next == null){return;
}//定義一個輔助的指針(變量)，幫助我們遍歷原來的鏈表
HeroNode cur =head.next;
HeroNode next= null; //指向當前節點[cur]的下一個節點
HeroNode reverseHead = new HeroNode(0,"","");//遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放在新的鏈表 reverseHead的最前端
while(cur != null){
next= cur.next; //先暫時保存當前節點的下一個節點
cur.next = reverseHead.next; //將cur的下一個節點指向新的鏈表的最前端
reverseHead.next = cur; //將cur鏈接到新的鏈表上
cur = next; //將cur后移
}//將head.next指向reverseHead.next，實現單鏈表的反轉
head.next =reverseHead.next;
}
View Code
【百度面試題】從尾到頭打印單鏈表(要求方式1：反向遍歷，方式2：Stack棧)
思路：
方式1：先將單鏈表進行反轉操作，然后再遍歷即可，這樣做的問題是會破壞原來的單鏈表結構，不建議
方式2：可以利用棧這個數據結構，將各個節點壓入到棧中，然后利用棧的先進后出的特點，就實現了逆序打印的效果。
方式2代碼實現
//單鏈表逆序打印
public static voidreversePrint(HeroNode head){if(head.next == null){return;
}//創建一個棧
Stack stack = new Stach();
HeroNode cur=head.next;//遍歷鏈表將所有的節點壓入棧
while(cur != null){
stack.push(cur);
cur=cur.next;
}//將棧中的節點進行打印，pop出棧
while(stack.size() > 0){
System.out.println(stack.pop());//利用stack先入后出的特點
}
}
總結
以上是生活随笔為你收集整理的java有链表吗_Java数据结构之链表（Linked List）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python3.7安装pyspider安
- 下一篇： java 多线程数量_java多线程之计