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