前言
此篇是對(duì)單鏈表知識(shí)的學(xué)習(xí)和實(shí)現(xiàn)，基本上大體的方法實(shí)現(xiàn)和思路都已經(jīng)表達(dá)，如果有不對(duì)的地方，還請(qǐng)各位大佬多多指教！
一、單鏈表的概念
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。
二、單鏈表內(nèi)一些方法的實(shí)現(xiàn)
2.1 單鏈表長(zhǎng)什么樣子？
像上面這樣式的就是一種單鏈表！
由上圖可以看出我們一些屬性來表示單鏈表！
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
2.2 創(chuàng)建單鏈表
創(chuàng)建鏈表之前我們需要定義一個(gè)成員變量head表示鏈表的頭結(jié)點(diǎn)！
//成員變量
public ListNode head;//鏈表的頭引用
由于咱們是初步學(xué)習(xí)單鏈表，所有咱們就簡(jiǎn)單的創(chuàng)建的單鏈表
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
2.3 打印單鏈表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
為什么會(huì)定義一個(gè)cur來指向head了？
那是因?yàn)槿绻胔ead來遍歷鏈表，那么最后head就指向了null，就找不到鏈表的頭了，所以使用cur來完成操作！
2.4 查找是否包含關(guān)鍵字key是否在單鏈表中
我們只需要拿cur去遍歷鏈表，看cur是否等于key，如果有就返回true，沒有就返回false。
實(shí)現(xiàn)cur遍歷的過程的代碼就是：cur = cur.next;
//查找是否包含關(guān)鍵字key是否在單鏈表中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
2.5 得到單鏈表的長(zhǎng)度
一樣的操作，此處通過定義一個(gè)count作為計(jì)數(shù)器，直到cur遍歷完整個(gè)鏈表就停止.
//得到單鏈表的長(zhǎng)度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
2.6 addFirst – 頭插
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
/*if (this.head == null) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}*/
}
2.7 addLast – 尾插
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
2.8 addIndex – 任意位置插入
/**
* 找到index - 1 位置結(jié)點(diǎn)的地址
* @param index
* @return
*/
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入，第一個(gè)數(shù)據(jù)結(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
System.out.println("index位置不合法!");
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
2.9 remove – 刪除第一次出現(xiàn)的key
/**
* 找到要?jiǎng)h除關(guān)鍵字的前驅(qū)
* @param key
* @return
*/
public ListNode searchPrev(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//刪除第一次出現(xiàn)的關(guān)鍵字key的結(jié)點(diǎn)
public void remove(int key) {
if (this.head == null) {
System.out.println("單鏈表為空，不能刪除！");
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPrev(key);
if (cur == null) {
System.out.println("沒有你要?jiǎng)h除的結(jié)點(diǎn)！");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
2.10 removeAllkey – 刪除所有值為key的結(jié)點(diǎn)
//刪除所有值為key的結(jié)點(diǎn)
public ListNode removeAllKey(int key) {
if (this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
//最后處理頭
if (this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}
1.如果先處理頭，則需要寫成循環(huán)，因?yàn)楫?dāng)鏈表所有結(jié)點(diǎn)都是待刪除的情況時(shí)，一個(gè)if條件語(yǔ)句處 理不了文章來源：http://www.zghlxwxcb.cn/news/detail-827737.html
2.while循環(huán)里面的條件不能寫成cur.next == null，因?yàn)閞emoveSubOne函數(shù)如果沒找到待刪除 的結(jié)點(diǎn)，它返回的是一個(gè)null，如果寫成cur.next != null，則可能會(huì)報(bào)空指針異常文章來源地址http://www.zghlxwxcb.cn/news/detail-827737.html
2.11 清空單鏈表
public void clear() {
this.head = null;
}
三、MyLinkedList.java
import java.util.LinkedList;
@SuppressWarnings({"all"})
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class MyLinkedList {
//成員變量
public ListNode head;//鏈表的頭引用
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//查找是否包含關(guān)鍵字key是否在單鏈表中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//得到單鏈表的長(zhǎng)度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
/*if (this.head == null) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}*/
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
/**
* 找到index - 1 位置結(jié)點(diǎn)的地址
* @param index
* @return
*/
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入，第一個(gè)數(shù)據(jù)結(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
System.out.println("index位置不合法!");
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
/**
* 找到要?jiǎng)h除關(guān)鍵字的前驅(qū)
* @param key
* @return
*/
public ListNode searchPrev(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//刪除第一次出現(xiàn)的關(guān)鍵字key的結(jié)點(diǎn)
public void remove(int key) {
if (this.head == null) {
System.out.println("單鏈表為空，不能刪除！");
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPrev(key);
if (cur == null) {
System.out.println("沒有你要?jiǎng)h除的結(jié)點(diǎn)！");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
//刪除所有值為key的結(jié)點(diǎn)
public ListNode removeAllKey(int key) {
if (this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
//最后處理頭
if (this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}
public void clear() {
this.head = null;
}
}
四、Test.java
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
/* myLinkedList.createList();
myLinkedList.display();
boolean flag = myLinkedList.contains(34);
System.out.println(flag);
int size = myLinkedList.size();
System.out.println(size);*/
myLinkedList.addFirst(12);
myLinkedList.addFirst(23);
myLinkedList.addLast(39);
myLinkedList.addLast(37);
myLinkedList.addIndex(0,99);
myLinkedList.addIndex(5,99);
myLinkedList.addIndex(3,99);
myLinkedList.display();
myLinkedList.remove(12);
myLinkedList.removeAllKey(99);
myLinkedList.display();
myLinkedList.clear();
myLinkedList.display();
}
}
到了這里，關(guān)于【一起學(xué)數(shù)據(jù)結(jié)構(gòu)與算法】快速教你了解并實(shí)現(xiàn)單鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
