單項鏈表

鏈表介紹：

鏈表是有序的列表，但是它在內存中是存儲如下

1)鏈表是以節點的方式來存儲, 是鏈式存儲

2) 每個節點包含 data 域， next 域：指向下一個節點.

3) 如圖：發現 鏈表的各個節點不一定是連續存儲.

4) 鏈表分 帶頭節點的鏈表和 沒有頭節點的鏈表，根據實際的需求來確定

單鏈表(帶頭結點) 邏輯結構示意圖如下

單鏈表的應用實例

1)第一種方式是添加節點時直接添加在鏈表尾部

2)第二種方式在添加節點時，根據排名將節點插入到指定位置(如果有這個排名，則添加失敗，并給出提示)

3)修改節點功能，通過遍歷找到該節點進行修改即可

4) 刪除節點，找到該節點，將該節點的上一個節點的下一個節點位置修改為該節點的下一個位置。示意圖：

代碼實現單鏈表的增刪改查

package com.pierce.algorithm;

class SingleLinkedList {

//先初始化一個頭節點, 頭節點不要動, 不存放具體的數據

private HeroNode head = new HeroNode(0, "", "");

//添加節點到單向鏈表

//思路，當不考慮編號順序時

//1. 找到當前鏈表的最后節點

//2. 將最后這個節點的 next 指向 新的節點

public void add(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 void addByOrder(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 void update(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(int no) {

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 void list() {

//判斷鏈表是否為空

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;

}

}

}

實體類

package com.pierce.algorithm;

class HeroNode {

public int no;

public String name;

public String nickname;

public HeroNode next; //指向下一個節點

//構造器

public HeroNode(int no, String name, String nickname) {

this.no = no;

this.name = name;

this.nickname = nickname;

}

//為了顯示方法，我們重新 toString

@Override

public String toString() {

return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";

}

}

總結

以上是生活随笔為你收集整理的java 链表算法_JAVA数据结构与算法之链表（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。