Java實現單鏈表的操作
本文實例為大傢分享瞭Java實現單鏈表的基本操作，供大傢參考，具體內容如下
順序表：物理上邏輯上都連續；
鏈表：物理上不一定連續，邏輯上一定連續的。
鏈表的概念及結構
概念：連表示一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是用過鏈表中的引用鏈接次序實現的。
8種鏈表結構：
單項、雙向
帶頭、不帶頭
循環、非循環
主要的三種鏈表：
無頭單項非循環鏈表、帶頭循環單鏈表、不帶頭雙向循環鏈表
代碼實現
1. 接口定義
package com.github.linked.Impl;
public interface ILinked {
// 頭插法
void addFirst(int data);
// 尾插法
void addLast(int data);
// 任意位置插入，第一數據節點為0號下標
boolean addIndex(int index, int data);
// 查找是否包含關鍵字 key 在單鏈表中
boolean contains(int key);
// 刪除第一次出現的關鍵字為 key 的節點
int remove(int key);
// 刪除所有值為 key 的節點
void removeAllKey(int key);
// 得到單鏈表的長度
int getLength();
// 打印單鏈表
void display();
// 清空單鏈表以防內存泄漏
void clear();
}
2. 代碼實現接口
package com.github.linked.Impl;
public class SingleListed implements ILinked {
// 節點類
class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
this.next = next;
}
}
private Node head; //頭節點
public SingleListed() {
this.head = head;
}
/**
* 頭插法
* @param data 要插入的數據
*/
@Override
public void addFirst(int data) {
// 1. 拿到一個實體
Node node = new Node(data);
// 2. 插入
// 如果是第一次插入，直接到頭節點
if (this.head == null) {
this.head = node;
} else { //不是第一次插入
node.next = this.head; // 插入的節點指向頭節點
this.head = node; // 更新頭節點
}
}
/**
* 尾插法
* @param data 要插入的數據
*/
@Override
public void addLast(int data) {
// 1. 拿到一個實體
Node node = new Node(data);
Node cur = this.head;
// 2. 插入
// 如果是第一次插入，直接到頭節點
if (this.head == null) {
this.head = node;
} else {
// 找尾巴
while (cur.next != null) {
cur = cur.next;
}
// 退出上面的循環，cur所執行的位置就是尾節點
cur.next = node;
}
}
// 檢測 index 該下標是否合法
private void checkIndex(int index) {
if (index < 0 || index > getLength())
throw new IndexOutOfBoundsException("下標不合法！");
}
// 找到下標為 index-1 位置的節點
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;
}
/**
* 任意位置插入，第一數據節點為 0號下標
* @param index 插入的下標
* @param data 要插入的數據
* @return true
*/
@Override
public boolean addIndex(int index, int data) {
Node node = new Node(data);
Node cur = searchIndex(index);
// 如果鏈表為空，直接插入到頭節點
if (cur == null) {
node.next = this.head;
this.head = node;
} else { // 鏈表不為空，插入到 cur 的位置處
node.next = cur.next; // 將node鏈接到cur的下一個節點
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 的節點的前驅
private Node searchPre(int key) {
// 1. 是不是第一個節點 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 的節點
* @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. 找到瞭，並且在第一個節點
if (pre == this.head && pre.data == key){
oldData = this.head.data;
this.head = this.head.next;
return oldData;
}
// 3. 找到瞭，並且不在第一個節點
Node delNode = pre.next; // 確定要刪除的節點的位置
pre.next = delNode.next; // 讓要刪除的節點的前驅指向要刪除的節點的後一個節點，進而刪除該節點
return 0;
}
/**
* 刪除所有值為 key 的節點
* @param key 要刪除的節點的值
*/
@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 { // 若不是關鍵字，繼續查看鏈表的下一個
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; // 節點的個數
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 的節點：");
System.out.println("刪除頭節點50：");
mySingleList.remove(50); //刪除頭節點
mySingleList.display();
System.out.println("刪除中間節點30：");
mySingleList.remove(30); // 刪除中間節點
mySingleList.display();
System.out.println("刪除尾節點200：");
mySingleList.remove(200); // 刪除尾節點
mySingleList.display();
System.out.println();
System.out.println("刪除第一次出現的關鍵字為 key 的節點：");
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. 測試結果
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。