Java實現(xiàn)單鏈表的操作
更新時間：2022年01月21日 08:16:30 作者：Sasura_321
這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)單鏈表的操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了Java實現(xiàn)單鏈表的基本操作，供大家參考，具體內(nèi)容如下
順序表：物理上邏輯上都連續(xù)；
鏈表：物理上不一定連續(xù)，邏輯上一定連續(xù)的。
鏈表的概念及結(jié)構(gòu)
概念：連表示一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是用過鏈表中的引用鏈接次序?qū)崿F(xiàn)的。
8種鏈表結(jié)構(gòu)：
單項、雙向
帶頭、不帶頭
循環(huán)、非循環(huán)
主要的三種鏈表：
無頭單項非循環(huán)鏈表、帶頭循環(huán)單鏈表、不帶頭雙向循環(huán)鏈表
代碼實現(xiàn)
1. 接口定義
package com.github.linked.Impl;
public interface ILinked {
? ? // 頭插法
? ? void addFirst(int data);
? ? // 尾插法
? ? void addLast(int data);
? ? // 任意位置插入，第一數(shù)據(jù)節(jié)點為0號下標(biāo)
? ? boolean addIndex(int index, int data);
? ? // 查找是否包含關(guān)鍵字 key 在單鏈表中
? ? boolean contains(int key);
? ? // 刪除第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點
? ? int remove(int key);
? ? // 刪除所有值為 key 的節(jié)點
? ? void removeAllKey(int key);
? ? // 得到單鏈表的長度
? ? int getLength();
? ? // 打印單鏈表
? ? void display();
? ? // 清空單鏈表以防內(nèi)存泄漏
? ? void clear();
}2. 代碼實現(xiàn)接口
package com.github.linked.Impl;
public class SingleListed implements ILinked {
? ? // 節(jié)點類
? ? class Node {
? ? ? ? private int data;
? ? ? ? private Node next;
? ? ? ? public Node(int data) {
? ? ? ? ? ? this.data = data;
? ? ? ? ? ? this.next = next;
? ? ? ? }
? ? }
? ? private Node head; //頭節(jié)點
? ? public SingleListed() {
? ? ? ? this.head = head;
? ? }
? ? /**
? ? ?* 頭插法
? ? ?* @param data 要插入的數(shù)據(jù)
? ? ?*/
? ? @Override
? ? public void addFirst(int data) {
? ? ? ? // 1. 拿到一個實體
? ? ? ? Node node = new Node(data);
? ? ? ? // 2. 插入
? ? ? ? // 如果是第一次插入，直接到頭節(jié)點
? ? ? ? if (this.head == null) {
? ? ? ? ? ? this.head = node;
? ? ? ? } else { //不是第一次插入
? ? ? ? ? ? node.next = this.head; // 插入的節(jié)點指向頭節(jié)點
? ? ? ? ? ? this.head = node; ? ? ?// 更新頭節(jié)點
? ? ? ? }
? ? }
? ? /**
? ? ?* 尾插法
? ? ?* @param data 要插入的數(shù)據(jù)
? ? ?*/
? ? @Override
? ? public void addLast(int data) {
? ? ? ? // 1. 拿到一個實體
? ? ? ? Node node = new Node(data);
? ? ? ? Node cur = this.head;
? ? ? ? // 2. 插入
? ? ? ? // 如果是第一次插入，直接到頭節(jié)點
? ? ? ? if (this.head == null) {
? ? ? ? ? ? this.head = node;
? ? ? ? } else {
? ? ? ? ? ? // 找尾巴
? ? ? ? ? ? while (cur.next != null) {
? ? ? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? }
? ? ? ? ? ? // 退出上面的循環(huán)，cur所執(zhí)行的位置就是尾節(jié)點
? ? ? ? ? ? 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é)點
? ? 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é)點為 0號下標(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é)點
? ? ? ? if (cur == null) {
? ? ? ? ? ? node.next = this.head;
? ? ? ? ? ? this.head = node;
? ? ? ? } else { // 鏈表不為空，插入到 cur 的位置處
? ? ? ? ? ? node.next = cur.next; ?// 將node鏈接到cur的下一個節(jié)點
? ? ? ? ? ? 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é)點的前驅(qū)
? ? private Node searchPre(int key) {
? ? ? ? // 1. 是不是第一個節(jié)點 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é)點
? ? ?* @param key 要刪除的關(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. 找到了，并且在第一個節(jié)點
? ? ? ? if (pre == this.head && pre.data == key){
? ? ? ? ? ? oldData = this.head.data;
? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? return oldData;
? ? ? ? }
? ? ? ? // 3. 找到了，并且不在第一個節(jié)點
? ? ? ? Node delNode = pre.next; // 確定要刪除的節(jié)點的位置
? ? ? ? pre.next = delNode.next; // 讓要刪除的節(jié)點的前驅(qū)指向要刪除的節(jié)點的后一個節(jié)點，進(jìn)而刪除該節(jié)點
? ? ? ? return 0;
? ? }
? ? /**
? ? ?* 刪除所有值為 key 的節(jié)點
? ? ?* @param key 要刪除的節(jié)點的值
? ? ?*/
? ? @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ù)查看鏈表的下一個
? ? ? ? ? ? ? ? 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é)點的個數(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é)點：");
? ? ? ? System.out.println("刪除頭節(jié)點50：");
? ? ? ? mySingleList.remove(50); //刪除頭節(jié)點
? ? ? ? mySingleList.display();
? ? ? ? System.out.println("刪除中間節(jié)點30：");
? ? ? ? mySingleList.remove(30); // 刪除中間節(jié)點
? ? ? ? mySingleList.display();
? ? ? ? System.out.println("刪除尾節(jié)點200：");
? ? ? ? mySingleList.remove(200); // 刪除尾節(jié)點
? ? ? ? mySingleList.display();
? ? ? ? System.out.println();
? ? ? ? System.out.println("刪除第一次出現(xiàn)的關(guān)鍵字為 key 的節(jié)點：");
? ? ? ? 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 數(shù)組交集的實現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
Java list與set中contains()方法效率案例詳解
這篇文章主要介紹了Java list與set中contains()方法效率案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
Mybatis查詢時數(shù)據(jù)丟失的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-01-01
這篇文章主要介紹了spring-cloud-gateway啟動踩坑及解決方案，具有很好的參考價值，希望對大家有所幫助。2021-08-08
這篇文章主要介紹了Java 跨域問題的處理方式，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-11-11
詳解Java設(shè)計模式編程中的Flyweight享元模式的開發(fā)結(jié)構(gòu)
這篇文章主要介紹了Java設(shè)計模式編程中的Flyweight享元模式的開發(fā)結(jié)構(gòu),享元模式能夠最大限度地重用現(xiàn)有的同類對象,需要的朋友可以參考下2016-04-04
這篇文章主要介紹了Java自定義數(shù)組列表的實現(xiàn)操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
spring cloud hystrix 超時時間使用方式詳解
這篇文章主要介紹了spring cloud hystrix 超時時間使用方式,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
SpringBoot JWT接口驗證實現(xiàn)流程詳細(xì)介紹
這篇文章主要介紹了SpringBoot+JWT實現(xiàn)接口驗證，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-09-09
教你在Spring Boot微服務(wù)中集成gRPC通訊的方法
這篇文章主要介紹了教你在Spring Boot微服務(wù)中集成gRPC通訊的方法,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09