文章目錄
- 🥇為何要使用鏈表
- 🥇 單鏈表是什么
- 單鏈表的資料存盤方式
- 🥇單鏈表之創建鏈表
- 🥇單鏈表之列印鏈表
- 🥇單鏈表之計算鏈表長度
- 🥇單鏈表之增刪查改
- 單鏈表之頭插法
- 單鏈表之尾插法
- 單鏈表之把一個節點插到鏈表中的任意位置
- 單鏈表之查找鏈表中是否某個元素
- 單鏈表之洗掉的一次出現value值的節點
- 單鏈表之洗掉鏈表中出現value值的所有節點
- 單鏈表之清空鏈表
- 總匯：
🥇為何要使用鏈表
博主在上一篇博客中詳細介紹了線性表的順序結構，也就是順序表的各種功能，例如增洗掉改等，詳細請看上一篇博客順序表
在這里先讓博主為大家回顧一下上一章的順序表的存盤結構
- 邏輯上：具有連續性
- 物理上：具有連續性
- 當資料的存盤空間不夠的時候，會開辟一段與原空間等長的空間來存盤資料
- 順序表的優點：
- 1.無須為表示表中元素邏輯關系而增添額外的存盤空間
- 2.可以快速的存取表中的任意位置的元素，
- 順序表的缺點：
- 1.插入和洗掉操作需要移動大量的資料，耗費時間
- 2.當線性表長度變化較大時，難以確定空間容量，比如說，線性表的原存1儲空間為100個單位，現在要存盤101個資料，先讓空間不夠用，就在開辟一倍等長的資料空間，儲存空間變為200，那么未被利用的有99個空間，就會造成儲存空間碎片，
今天博主介紹的是單鏈表，相比順序表，它在插入和洗掉方面，具有很大的優勢，
🥇 單鏈表是什么
反觀順序表要存盤資料，每次的都要一次性開辟非常大的空間，存盤資料，怎樣解決這個問題呢？
鏈表做出了以下回應，要利用資料時，需要一個資料，開辟一個空間，那有些童鞋就會問為什么不在順序表中這樣做呢？解答：如果利用一個資料，開辟一個空間，就會造成邏輯上的不連續，就不能成為線性表，
- 我們可以在第一個元素時，就知道第二個元素的位置(記憶體地址),而找到第二個元素的時候，就知道第三個元素的地址，這樣所有的元素我們就可以通過遍歷來找到
可能在上述的鏈表圖中，大家有點迷糊，那下來就看看博主的介紹：
在鏈表中，有資料域和指標域兩個概念 - 資料域：存放將要進行被操作的資料
- 指標域：存放下一個元素的地址
- 一個資料域和一個指標域合起來成為一個鏈表的節點(node)，在讀取到一個節點時，我們會知道這個節點所對應的資料，同時也會知道下一個節點的地址
單鏈表的資料存盤方式
特點：用一組任意的存盤單元，存盤順序表的元素，這組存盤元素可以是連續的，也可以是不連續的，這就意味著這些元素可以存在記憶體中未被占用的任意位置
鏈表的存盤結構：
🥇單鏈表之創建鏈表
說到實作這個鏈表，這也相當于一個小專案吧，那我們就創建一個測驗檔案 TestDemo.java 來測驗創建鏈表的功能，實作一個MyLinkedList.java檔案，來實作鏈表的各個功能
- 在
MyLinkedList.java檔案中，先創建一個節點類class Node，里面包括一個節點的資料元素，和下一個節點的地址， - ??代碼：
class Node {
public int val;
public Node next;//節點中的next地址，默認為空
public Node(int val) {
this.val = val; //為節點中的資料進行初始化
}
然后隨機利用一些資料進行對鏈表的定義，并且把每一個節點都連接起來，實作創建一個單鏈表方法
??代碼：
public void createList() {
Node node1 = new Node(12);
Node node2 = new Node(3);
Node node3 = new Node(5);
Node node4 = new Node(2);
node1.next = node2;
//連接每一個節點
node2.next = node3;
node3.next = node4;
this.head = node1; //定義一個頭節點，指向第一個節點
}
在TestDemo.java檔案中，創建一個物件，參考MyLinkedList.java檔案中的功能方法，
🥇單鏈表之列印鏈表
遍歷整個鏈表，直到鏈表結束，在MyLinkedList.java檔案實作print方法
📄演算法思想：
- 如果鏈表為空鏈表，即this.head == null ,那么鏈表為空，就直接回傳
- 創建一個跟隨節點，cur ，指向頭結點，每遍歷一個節點，cur = cur.next，就指向下一個節點
- 鏈表跟隨節點的結束標志為：cur != null ,如果是cur.next != null 只能遍歷到倒數第二個節點，因為當倒數第一格節點為null時，就不會進入回圈列印元素，
??代碼：
public void print() {
if(this.head == null){
return ;
}
Node cur = this.head;
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
列印新創建的單鏈表
在TestDemo.java檔案中呼叫print方法
🥇單鏈表之計算鏈表長度
在MyLinkedList.java檔案實作size方法
演算法思想：
1. 創建跟隨節點，遍歷整個鏈表
2. 創建一個計數器，每遍歷一個節點，count就加1，統計count
3. 當鏈表為空時，即this,head == null 時，回傳0，證明鏈表長度為0
??代碼：
//得到單鏈表的長度
public int size() {
if(this.head == null){
System.out.println("頭結點為空");
return -1;
}
Node cur = this.head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
🥇單鏈表之增刪查改
單鏈表之頭插法
在MyLinkedList.java檔案中實作addFirst()函式功能
📄演算法思想：
1. 判斷這個單鏈表是否為空，即this.head == null,如果等于的話，那么新插入的節點就是頭節點，即 this.head = node(要插入節點的地址)
2.在鏈表的頭部插入節點，也就是讓鏈表的頭結點的地址賦給新插入節點的next，即node.next = this.head,然后讓新鏈表的頭結點等于新插入的節點node的地址，即this.head = node.
看圖說話
??代碼：
//頭插法
public void addFirst(int data) {
Node node = new Node(data);
//如果鏈表本身為空
if(this.head == null){
this.head = node;
}else{
node.next = this.head;
this.head = node;
}
}
單鏈表之尾插法
在MyLinkedList.java檔案中實作addLast()函式功能
📄演算法思想：
1. 判斷這個單鏈表是否為空，即this.head == null,如果等于的話，那么新插入的節點就是頭節點，即 this.head = node(要插入節點的地址)
2.新建一個跟隨節點cur，遍歷鏈表
2.找到鏈表中的尾節點，并回傳此節點
3.讓cur.next = node,這樣就把插入的節點，放到了鏈表尾部
看圖說話：
??代碼：
//尾插法
public void addLast(int data) {
Node node = new Node(data);
//如果鏈表頭結點為空，就等于說鏈表本身為空
if(this.head == null){
this.head = node;
return;
}
Node cur = this.head;
//找到鏈表最后一個節點，讓最后一個節點，的next等于所在尾插點的地址
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
單鏈表之把一個節點插到鏈表中的任意位置
在MyLinkedList.java檔案中實作addIndex(int Index,int data)函式功能
📄演算法思想：
1. 判斷這個單鏈表是否為空，即this.head == null,如果等于的話，那么新插入的節點就是頭節點，即 this.head = node(要插入節點的地址)
2.判斷下標Index的合法性，如果Index等于0,那么就呼叫addFirst方法，如果Index等于size()-呼叫size方法,那么就呼叫addLast方法，如果Index < 0 或者 Index > size(),那么就列印下標不合法，直接return 退出，
3.如果Index合法，且要出入節點，不在鏈表首尾，那么就要找到所插節點的前驅節點，并回傳此節點，讓node.next = cur.next,然后讓cur.next = node，就可以連接所插節點，
看圖說話：
??代碼：
//找到插入節點的前一個位置
public Node find_cur(int index){
Node cur = this.head;
int count = 0;
while(count!=index-1){
count++;
cur = cur.next;
}
return cur;
}
//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index,int data){
//判斷indxx的合法性
if(index < 0 || index >size()){
System.out.println("下標不合法");
}
//插入頭結點
if(index == 0){
addFirst(data);
return;
}
//插入尾節點
if(index == size()){
addLast(data);
return;
}
//插入其他節點
Node node = new Node(data);
Node cur = find_cur(index);
node.next = cur.next;
cur.next = node;
}
單鏈表之查找鏈表中是否某個元素
在MyLinkedList.java檔案中實作contans(int data)函式功能
📄演算法思想：
1. 創建一個跟隨節點，cur 初始化為cur = this.head
2. 如果鏈表為空，即this,head == null ,就回傳false退出
3. 如果在鏈表中找不到要找的元素，也回傳false并退出
4. 遍歷鏈表，直到cur == null,每次回圈cur = cur.next 尋找對應的元素cur.next == value，找到回傳true，找不到回傳false.
看圖說話：
單鏈表之洗掉的一次出現value值的節點
在MyLinkedList.java檔案中實作remove(int data)函式功能
📄演算法思想：
1. 判斷鏈表是否為空，如果為空，就沒有必要洗掉
2. 如果不為空，就遍歷該鏈表，找到要洗掉的值的節點，回傳它的前驅節點
3.這個前驅節點的next 等于下下一個節點的地址，即cur.next = cur.next.next 這樣就巧妙的跳過了要洗掉的節點
看圖說話：
??代碼：
public Node seaarchPrevNode(int value){
Node cur = this.head;
while(cur!=null){
if(cur.next.val == value){
return cur;
}else{
cur = cur.next;
}
}
return null;
}
//洗掉第一次出現關鍵字為key的節點
public void remove(int value) {
//如果鏈表為空，頭結點為空
if(this.head == null){
System.out.println("鏈表為空，沒有洗掉的節點");
}
//如果頭結點為要洗掉的節點
if(this.head.val == value){
this.head = this.head.next;
}
//先找到這個要洗掉的節點
Node cur = seaarchPrevNode(value); //前驅節點
// Node del = cur.next;
// cur.next = del.next;
cur.next = cur.next.next;
}
單鏈表之洗掉鏈表中出現value值的所有節點
在MyLinkedList.java檔案中實作removeAllkey(int data)函式功能
📄演算法思想：
1. 設定頭結點head,前驅節點prev = this.head,跟隨節點 cur = this.head.next
2. 遍歷鏈表，依靠cur節點，遍歷除頭結點，以外的節點，如果某個節點的value值等于所要洗掉的value值，即cur.value == value，就讓前驅節點prev.next = cur.next,跳過cur節點，然后cur = cur.next 再向后遍歷，當cur.value不等于value時，讓前驅節點prev等于cur,最后如果頭結點等于前驅節點，那么洗掉頭結點，this.head = this.head.next
看圖說話：
??代碼
//洗掉所有值為key的節點
public void removeAllKey(int value) {
Node prev = this.head;
Node cur = this.head.next;
//判斷前面是否為要洗掉節點
while(cur!=null){
if(cur.val == value){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
//如果頭結點為可刪節點
if(this.head.val == value){
this.head = this.head.next;
}
}
單鏈表之清空鏈表
在MyLinkedList.java檔案中實作clear(int data)函式功能
📄演算法思想：
1. 建立一個節點保存head.next curNext = head.next
2. 將head.next 置為 null
3. 利用head = curNext回圈
4. 直到遍歷到做后一個節點為為止，
看圖說話
??代碼
//清空單鏈表
public void clear(){
while(head != null){
Node curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
總匯：
💯TestDemo.java檔案：
public class TestDemo {
public static void main(String[] args) {
MyLinkList myLinkList = new MyLinkList();
myLinkList.createList(); //創建鏈表
myLinkList.addIndex(0,5);
System.out.print("原鏈表");
myLinkList.print();
myLinkList.clear();
System.out.print("新鏈表");
myLinkList.print();
}
}
💯MyLinkedList.java檔案
class Node {
public int val;
public Node next;//null
public Node(int val) {
this.val = val;
}
}
//鏈表
public class MyLinkList {
public Node head;//標識單鏈表的頭節點
/**
* 窮舉的方式 創建鏈表 當然很low，此處只是為了好理解
*/
public void createList() {
Node node1 = new Node(12);
Node node2 = new Node(3);
Node node3 = new Node(5);
Node node4 = new Node(2);
node1.next = node2;
node2.next = node3;
node3.next = node4;
this.head = node1;
}
/**
* 列印單鏈表
*/
public void print() {
Node cur = this.head;
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//得到單鏈表的長度
public int size() {
if(this.head == null){
System.out.println("頭結點為空");
return -1;
}
Node cur = this.head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int value) {
if(this.head == null){
System.out.println("鏈表為空");
return false;
}
Node cur = this.head;
while(cur!=null){
if(cur.val == value){
return true;
}
cur = cur.next;
}
return false;
}
//頭插法
public void addFirst(int data) {
Node node = new Node(data);
//如果鏈表本身為空
if(this.head == null){
this.head = node;
}else{
node.next = this.head;
this.head = node;
}
}
//尾插法
public void addLast(int data) {
Node node = new Node(data);
//如果鏈表頭結點為空，就等于說鏈表本身為空
if(this.head == null){
this.head = node;
return;
}
Node cur = this.head;
//找到鏈表最后一個節點，讓最后一個節點，的next等于所在尾插點的地址
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
//找到插入節點的前一個位置
public Node find_cur(int index){
Node cur = this.head;
int count = 0;
while(count!=index-1){
count++;
cur = cur.next;
}
return cur;
}
//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index,int data){
//判斷indxx的合法性
if(index < 0 || index >size()){
System.out.println("下標不合法");
}
//插入頭結點
if(index == 0){
addFirst(data);
return;
}
//插入尾節點
if(index == size()){
addLast(data);
return;
}
//插入其他節點
Node node = new Node(data);
Node cur = find_cur(index);
node.next = cur.next;
cur.next = node;
}
public Node seaarchPrevNode(int value){
Node cur = this.head;
while(cur!=null){
if(cur.next.val == value){
return cur;
}else{
cur = cur.next;
}
}
return null;
}
//洗掉第一次出現關鍵字為key的節點
public void remove(int value) {
//如果鏈表為空，頭結點為空
if(this.head == null){
System.out.println("鏈表為空，沒有洗掉的節點");
}
//如果頭結點為要洗掉的節點
if(this.head.val == value){
this.head = this.head.next;
}
//先找到這個要洗掉的節點
Node cur = seaarchPrevNode(value); //前驅節點
// Node del = cur.next;
// cur.next = del.next;
cur.next = cur.next.next;
}
//洗掉所有值為key的節點
public void removeAllKey(int value) {
Node prev = this.head;
Node cur = this.head.next;
//判斷前面是否為要洗掉節點
while(cur!=null){
if(cur.val == value){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
//如果頭結點為可刪節點
if(this.head.val == value){
this.head = this.head.next;
}
}
//清空單鏈表
public void clear(){
while(head != null){
Node curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/293350.html
標籤：java