Java實(shí)現(xiàn)單鏈表的操作
更新時(shí)間：2022年01月21日 08:16:30 作者：Sasura_321
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)單鏈表的操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
本文實(shí)例為大家分享了Java實(shí)現(xiàn)單鏈表的基本操作，供大家參考，具體內(nèi)容如下
順序表：物理上邏輯上都連續(xù)；
鏈表：物理上不一定連續(xù)，邏輯上一定連續(xù)的。
鏈表的概念及結(jié)構(gòu)
概念：連表示一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是用過鏈表中的引用鏈接次序?qū)崿F(xiàn)的。
8種鏈表結(jié)構(gòu)：
單項(xiàng)、雙向
帶頭、不帶頭
循環(huán)、非循環(huán)
主要的三種鏈表：
無頭單項(xiàng)非循環(huán)鏈表、帶頭循環(huán)單鏈表、不帶頭雙向循環(huán)鏈表
代碼實(shí)現(xiàn)
1. 接口定義
package com.github.linked.Impl;
public interface ILinked {
? ? // 頭插法
? ? void addFirst(int data);
? ? // 尾插法
? ? void addLast(int data);
? ? // 任意位置插入，第一數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
? ? boolean addIndex(int index, int data);
? ? // 查找是否包含關(guān)鍵字 key 在單鏈表中
? ? boolean contains(int key);
? ? // 刪除第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點(diǎn)
? ? int remove(int key);
? ? // 刪除所有值為 key 的節(jié)點(diǎn)
? ? void removeAllKey(int key);
? ? // 得到單鏈表的長度
? ? int getLength();
? ? // 打印單鏈表
? ? void display();
? ? // 清空單鏈表以防內(nèi)存泄漏
? ? void clear();
}2. 代碼實(shí)現(xiàn)接口
package com.github.linked.Impl;
public class SingleListed implements ILinked {
? ? // 節(jié)點(diǎn)類
? ? class Node {
? ? ? ? private int data;
? ? ? ? private Node next;
? ? ? ? public Node(int data) {
? ? ? ? ? ? this.data = data;
? ? ? ? ? ? this.next = next;
? ? ? ? }
? ? }
? ? private Node head; //頭節(jié)點(diǎn)
? ? public SingleListed() {
? ? ? ? this.head = head;
? ? }
? ? /**
? ? ?* 頭插法
? ? ?* @param data 要插入的數(shù)據(jù)
? ? ?*/
? ? @Override
? ? public void addFirst(int data) {
? ? ? ? // 1. 拿到一個(gè)實(shí)體
? ? ? ? Node node = new Node(data);
? ? ? ? // 2. 插入
? ? ? ? // 如果是第一次插入，直接到頭節(jié)點(diǎn)
? ? ? ? if (this.head == null) {
? ? ? ? ? ? this.head = node;
? ? ? ? } else { //不是第一次插入
? ? ? ? ? ? node.next = this.head; // 插入的節(jié)點(diǎn)指向頭節(jié)點(diǎn)
? ? ? ? ? ? this.head = node; ? ? ?// 更新頭節(jié)點(diǎn)
? ? ? ? }
? ? }
? ? /**
? ? ?* 尾插法
? ? ?* @param data 要插入的數(shù)據(jù)
? ? ?*/
? ? @Override
? ? public void addLast(int data) {
? ? ? ? // 1. 拿到一個(gè)實(shí)體
? ? ? ? Node node = new Node(data);
? ? ? ? Node cur = this.head;
? ? ? ? // 2. 插入
? ? ? ? // 如果是第一次插入，直接到頭節(jié)點(diǎn)
? ? ? ? if (this.head == null) {
? ? ? ? ? ? this.head = node;
? ? ? ? } else {
? ? ? ? ? ? // 找尾巴
? ? ? ? ? ? while (cur.next != null) {
? ? ? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? }
? ? ? ? ? ? // 退出上面的循環(huán)，cur所執(zhí)行的位置就是尾節(jié)點(diǎn)
? ? ? ? ? ? cur.next = node;
? ? ? ? }
? ? }
? ? // 檢測 index 該下標(biāo)是否合法
? ? private void checkIndex(int index) {
? ? ? ? if (index < 0 || index > getLength())
? ? ? ? ? ? throw new IndexOutOfBoundsException("下標(biāo)不合法！");
? ? }
? ? // 找到下標(biāo)為 index-1 位置的節(jié)點(diǎn)
? ? private Node searchIndex(int index) {
? ? ? ? checkIndex(index);
? ? ? ? if (index == 0)
? ? ? ? ? ? return null;
? ? ? ? int count = 0; // 記錄行走的步數(shù)
? ? ? ? Node cur = this.head;
? ? ? ? while (cur.next != null && count < index-1) {
? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? count++;
? ? ? ? }
? ? ? ? return cur;
? ? }
? ? /**
? ? ?* 任意位置插入，第一數(shù)據(jù)節(jié)點(diǎn)為 0號(hào)下標(biāo)
? ? ?* @param index 插入的下標(biāo)
? ? ?* @param data 要插入的數(shù)據(jù)
? ? ?* @return true
? ? ?*/
? ? @Override
? ? public boolean addIndex(int index, int data) {
? ? ? ? Node node = new Node(data);
? ? ? ? Node cur = searchIndex(index);
? ? ? ? // 如果鏈表為空，直接插入到頭節(jié)點(diǎn)
? ? ? ? if (cur == null) {
? ? ? ? ? ? node.next = this.head;
? ? ? ? ? ? this.head = node;
? ? ? ? } else { // 鏈表不為空，插入到 cur 的位置處
? ? ? ? ? ? node.next = cur.next; ?// 將node鏈接到cur的下一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? cur.next = node; ? ? ? // 再將cur鏈接到node
? ? ? ? }
? ? ? ? return true;
? ? }
? ? /**
? ? ?* 查找是否包含關(guān)鍵字 key 在單鏈表中
? ? ?* @param key 要查找的關(guān)鍵字
? ? ?* @return 找到key返回true，否則返回false
? ? ?*/
? ? @Override
? ? public boolean contains(int key) {
? ? ? ? Node cur = this.head;
? ? ? ? while (cur != null) {
? ? ? ? ? ? if (cur.data == key) {
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? return false;
? ? }
? ? // 找第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點(diǎn)的前驅(qū)
? ? private Node searchPre(int key) {
? ? ? ? // 1. 是不是第一個(gè)節(jié)點(diǎn) if(head,data == key)
? ? ? ? Node pre = this.head;
? ? ? ? if (pre.data == key) {
? ? ? ? ? ? // 或者 return null;
? ? ? ? ? ? return this.head;
? ? ? ? }
? ? ? ? // 2. if(cur.next.data == key)
? ? ? ? while (pre.next != null) {
? ? ? ? ? ? if (pre.next.data == key) {
? ? ? ? ? ? ? ? return pre;
? ? ? ? ? ? }
? ? ? ? ? ? pre = pre.next;
? ? ? ? }
? ? ? ? return null;
? ? }
? ? /**
? ? ?* 刪除第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點(diǎn)
? ? ?* @param key 要?jiǎng)h除的關(guān)鍵字
? ? ?* @return oldData
? ? ?*/
? ? @Override
? ? public int remove(int key) {
? ? ? ? int oldData = 0;
? ? ? ? Node pre = searchPre(key);
? ? ? ? // 1. 若沒有找到
? ? ? ? if (pre == null) {
? ? ? ? ? ? // return -1;
? ? ? ? ? ? throw new UnsupportedOperationException("沒有key的前驅(qū)");
? ? ? ? }
? ? ? ? // 2. 找到了，并且在第一個(gè)節(jié)點(diǎn)
? ? ? ? if (pre == this.head && pre.data == key){
? ? ? ? ? ? oldData = this.head.data;
? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? return oldData;
? ? ? ? }
? ? ? ? // 3. 找到了，并且不在第一個(gè)節(jié)點(diǎn)
? ? ? ? Node delNode = pre.next; // 確定要?jiǎng)h除的節(jié)點(diǎn)的位置
? ? ? ? pre.next = delNode.next; // 讓要?jiǎng)h除的節(jié)點(diǎn)的前驅(qū)指向要?jiǎng)h除的節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，進(jìn)而刪除該節(jié)點(diǎn)
? ? ? ? return 0;
? ? }
? ? /**
? ? ?* 刪除所有值為 key 的節(jié)點(diǎn)
? ? ?* @param key 要?jiǎng)h除的節(jié)點(diǎn)的值
? ? ?*/
? ? @Override
? ? public void removeAllKey(int key) {
? ? ? ? Node pre = this.head;
? ? ? ? Node cur = this.head.next;
? ? ? ? // 遍歷一遍鏈表
? ? ? ? while (cur != null) {
? ? ? ? ? ? // 若找到了關(guān)鍵字，進(jìn)行刪除
? ? ? ? ? ? if (cur.data == key) {
? ? ? ? ? ? ? ? pre.next = cur.next;
? ? ? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? } else { // 若不是關(guān)鍵字，繼續(xù)查看鏈表的下一個(gè)
? ? ? ? ? ? ? ? pre = cur;
? ? ? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? }
? ? ? ? ? ? if (this.head.data == key) {
? ? ? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? }
? ? ? ? }
? ? }
?? ?/**
? ? ?* 得到單鏈表的長度
? ? ?* @return 單鏈表長度
? ? ?*/
? ? @Override
? ? public int getLength() {
? ? ? ? Node cur = this.head;
? ? ? ? int count = 0; ?// 節(jié)點(diǎn)的個(gè)數(shù)
? ? ? ? while (cur != null) {
? ? ? ? ? ? count++;
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? return count;
? ? }
? ? /**
? ? ?* 打印單鏈表
? ? ?*/
? ? @Override
? ? public void display() {
? ? ? ? Node cur = this.head;
? ? ? ? while (cur != null) {
? ? ? ? ? ? System.out.print(cur.data + " ");
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? System.out.println();
? ? }
? ? /**
? ? ?* 清空單鏈表以防內(nèi)存泄漏
? ? ?*/
? ? @Override
? ? public void clear() {
? ? ? ? while (this.head != null) {
? ? ? ? ? ? Node cur = this.head.next;
? ? ? ? ? ? this.head.next = null;
? ? ? ? ? ? this.head = cur;
? ? ? ? }
? ? }
}3. 測試代碼
package com.github.linked.Impl;
public class TestDemo {
? ? public static void main(String[] args) {
? ? ? ? //MySingleListImpl mySingleList = new MySingleListImpl();
? ? ? ? SingleListed mySingleList = new SingleListed();
? ? ? ? mySingleList.addFirst(10);
? ? ? ? mySingleList.addFirst(20);
? ? ? ? mySingleList.addFirst(30);
? ? ? ? mySingleList.addFirst(40);
? ? ? ? mySingleList.addFirst(50);
? ? ? ? System.out.println("頭插：");
? ? ? ? mySingleList.display();
? ? ? ? mySingleList.addLast(100);
? ? ? ? mySingleList.addLast(200);
? ? ? ? System.out.println("尾插：");
? ? ? ? mySingleList.display();
? ? ? ? System.out.println();
? ? ? ? System.out.print("單鏈表的長度：");
? ? ? ? System.out.println(mySingleList.getLength());
? ? ? ? System.out.println();
? ? ? ? mySingleList.addIndex(1,15);
? ? ? ? System.out.println("任意位置插入：");
? ? ? ? mySingleList.display();
? ? ? ? System.out.println();
? ? ? ? System.out.println("查找是否包含關(guān)鍵字 key 在單鏈表中：");
? ? ? ? System.out.println("查找關(guān)鍵字125："+mySingleList.contains(125));
? ? ? ? System.out.println("查找關(guān)鍵字30："+mySingleList.contains(30));
? ? ? ? System.out.println();
? ? ? ? System.out.println("刪除第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點(diǎn)：");
? ? ? ? System.out.println("刪除頭節(jié)點(diǎn)50：");
? ? ? ? mySingleList.remove(50); //刪除頭節(jié)點(diǎn)
? ? ? ? mySingleList.display();
? ? ? ? System.out.println("刪除中間節(jié)點(diǎn)30：");
? ? ? ? mySingleList.remove(30); // 刪除中間節(jié)點(diǎn)
? ? ? ? mySingleList.display();
? ? ? ? System.out.println("刪除尾節(jié)點(diǎn)200：");
? ? ? ? mySingleList.remove(200); // 刪除尾節(jié)點(diǎn)
? ? ? ? mySingleList.display();
? ? ? ? System.out.println();
? ? ? ? System.out.println("刪除第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點(diǎn)：");
? ? ? ? mySingleList.addFirst(20);
? ? ? ? mySingleList.display();
? ? ? ? mySingleList.removeAllKey(20);
? ? ? ? mySingleList.display();
? ? ? ? System.out.println();
? ? ? ? System.out.print("單鏈表的長度：");
? ? ? ? System.out.println(mySingleList.getLength());
? ? ? ? System.out.println();
? ? ? ? // 測試內(nèi)存泄漏
? ? ? ? try {
? ? ? ? ? ? Thread.sleep(1000);
? ? ? ? ? ? System.out.println("睡醒了");
? ? ? ? } catch (InterruptedException e) {
? ? ? ? ? ? e.printStackTrace();
? ? ? ? }
? ? }
}4. 測試結(jié)果
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java中Dijkstra算法求解最短路徑的實(shí)現(xiàn)
Dijkstra算法是一種解決最短路徑問題的常用算法,本文主要介紹了Java中Dijkstra算法求解最短路徑的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
Windows下Java環(huán)境配置的超詳細(xì)教程
這篇文章主要給大家介紹了關(guān)于Windows下Java環(huán)境配置的超詳細(xì)教程,文中通過圖文將配置的過程介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2023-01-01
這篇文章主要介紹了JDK9對String字符串的新一輪優(yōu)化,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-03-03
這篇文章主要介紹了Java實(shí)現(xiàn)的簡單擲骰子游戲,涉及Java隨機(jī)數(shù)的簡單生成、運(yùn)算與判定相關(guān)操作技巧,需要的朋友可以參考下2018-01-01
Java實(shí)現(xiàn)樹形菜單的方法總結(jié)
當(dāng)我們想要展示層級(jí)結(jié)構(gòu),如文件目錄、組織結(jié)構(gòu)或分類目錄時(shí),樹形菜單是一個(gè)直觀且有效的解決方案,本文為大家整理了java中幾種常見方法,希望對大家有所幫助2023-08-08
JAVA生產(chǎn)者消費(fèi)者(線程同步)代碼學(xué)習(xí)示例
這篇文章主要介紹了JAVA線程同步的代碼學(xué)習(xí)示例，大家參考使用吧2013-11-11
這篇文章主要介紹了如何利用JavaWeb實(shí)現(xiàn)表單提交功能，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)JavaWeb有一定幫助，感興趣的可以了解一下2022-03-03
Redis實(shí)現(xiàn)延遲隊(duì)列的全流程詳解
Redisson是Redis服務(wù)器上的分布式可伸縮Java數(shù)據(jù)結(jié)構(gòu)，這篇文中主要為大家介紹了Redisson實(shí)現(xiàn)的優(yōu)雅的延遲隊(duì)列的方法，需要的可以參考一下2023-03-03
這篇文章主要介紹了Spring如何自定義加載配置文件(分層次加載)問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
jstat命令可以查看堆內(nèi)存各部分的使用量,以及加載類的數(shù)量,下面這篇文章主要給大家介紹了關(guān)于Java中jstat命令使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03