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ù)元素的邏輯順序是用過(guò)鏈表中的引用鏈接次序?qū)崿F(xiàn)的。

8種鏈表結(jié)構(gòu)：

單項(xiàng)、雙向
帶頭、不帶頭
循環(huán)、非循環(huán)

主要的三種鏈表：

無(wú)頭單項(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);

? ? // 得到單鏈表的長(zhǎng)度
? ? 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;
? ? ? ? }
? ? }

? ? // 檢測(cè) 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. 若沒(méi)有找到
? ? ? ? if (pre == null) {
? ? ? ? ? ? // return -1;
? ? ? ? ? ? throw new UnsupportedOperationException("沒(méi)有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;
? ? ? ? ? ? }
? ? ? ? }
? ? }

?? ?/**
? ? ?* 得到單鏈表的長(zhǎng)度
? ? ?* @return 單鏈表長(zhǎng)度
? ? ?*/
? ? @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. 測(cè)試代碼

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("單鏈表的長(zhǎng)度：");
? ? ? ? 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("單鏈表的長(zhǎng)度：");
? ? ? ? System.out.println(mySingleList.getLength());
? ? ? ? System.out.println();

? ? ? ? // 測(cè)試內(nèi)存泄漏
? ? ? ? try {
? ? ? ? ? ? Thread.sleep(1000);
? ? ? ? ? ? System.out.println("睡醒了");
? ? ? ? } catch (InterruptedException e) {
? ? ? ? ? ? e.printStackTrace();
? ? ? ? }
? ? }
}

4. 測(cè)試結(jié)果