1.1鏈表的概念及結構
鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的 ，
實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：
單向、雙向
帶頭、不帶頭
回圈、非回圈
-
不帶頭結點的非回圈單向鏈表
-
不帶頭結點的非回圈雙向鏈表
-
不帶頭結點的回圈單向鏈表
-
不帶頭結點的回圈雙向鏈表
-
帶頭結點的非回圈單向鏈表(頭結點不存放資料)
-
帶頭結點的非回圈雙向鏈表(頭結點不存放資料)
-
帶頭結點的回圈單向鏈表(頭結點不存放資料)
-
帶頭結點的回圈雙向鏈表(頭結點不存放資料)
雖然有這么多的鏈表的結構，但是現在先重點實作無頭單向非回圈鏈表和無頭雙向非回圈鏈表，其余的后面在實作，
1.2鏈表的簡單實作
1.2.1無頭單向非回圈鏈表的實作
首先先創建一個節點類，里面包含了data資料域和next域
class Node{
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
然后就是鏈表的介面和方法實作
public class MyLinkNode {
//定義一個鏈表的頭待連接鏈表
public Node head;
}
注意：以下方法均在MyLinkNode 類中
（1）顯示單鏈表
public void disPlay() {
if(this.head==null) {
System.out.println("Over!");
return;
}
Node p = this.head;
while(p!=null) {
System.out.print(p.data+"->");
p = p.next;
}
System.out.println("Over!");
}
（2）頭插法
頭插法不需要判空
圖示：
代碼：
public void addFirst(int data) {
Node node = new Node(data); //創建一個新的節點
Node node = new Node(data);
node.next = this.head;
this.head = node;
}
（2）尾插法
尾插法需要判空
圖示：
代碼：
public void addEnd(int data) {
Node node = new Node(data);
//如果頭為空，則直接讓頭指向新節點
if(this.head == null) {
this.head = node;
}else {
Node p = this.head;
//先找到鏈表的最后一個結點
while(p.next!=null) {
//如果當前結點的next不為空，則說明后面還有結點
//如果為空，則說明已找到最后一個結點的位置
p = p.next;
}
//讓最后一個結點的next等于新結點
p.next = node;
}
}
（3）獲取單鏈表的長度
public int size() {
int count = 0;
if(this.head == null) {
//如果頭為空，回傳0
return 0;
}else {
Node p = this.head;
//采用遍歷單鏈表的思路
//每走過一個結點，count++，直到當前結點為空
while(p!=null) {
count++;
p = p.next;
}
}
return count;
}
（4）任意位置插入,第一個資料節點為0號下標
要在任意位置插入，首先要判斷下標合法性
public boolean checkIndex(int index) {
if(index < 0||index > this.size()) {
return false;
}
return true;
}
然后，查找 (index-1)節點的位置，也就是[前驅節點]的位置，找到回傳該節點
public Node searchPrev(int index) {
Node prev = this.head;
int i = 0;
while(i<index-1) {
prev = prev.next;
i++;
}
return prev;
}
最后，根據下標插入節點(當然，你也可以將這些都寫到一個方法中)
圖示：
代碼：
public void addIndex(int index,int data) {
Node node = new Node(data);
Node prev = null;
//如果下標位置非法，直接return
if(!this.checkIndex(index))
{
return;
}
if(index==0) {
//如果下標位置為0，則直接呼叫頭插法
addFirst(data);
return;
}
if(index==this.size()) {
//如果下標位置等于鏈表的長度，呼叫尾插法
addEnd(data);
return;
}else {
//接收前驅節點
prev = this.searchPrev(index);
node.next = prev.next;
prev.next = node;
}
}
（5）查找是否包含關鍵字key是否在單鏈表當中
public boolean findVal(int data) {
//思路簡單，采用遍歷的方法
Node p = this.head;
while(p!=null) {
if(p.data==data) {
return true;
}
p = p.next;
}
return false;
}
（6）洗掉第一次出現關鍵字為key的節點
首先找到要洗掉的結點的前驅節點
public Node searchPrevNode(int key) {
Node prev = this.head;
//同樣采用遍歷的思路
if(findVal(key)) {
while(prev.next!=null) {
if(prev.next.data==key) {
return prev;
}
prev = prev.next;
}
}
return null;
}
然后分情況洗掉節點
圖示：
代碼：
public void remove(int key) {
//接收待洗掉結點的前驅節點
Node prev = this.searchPrevNode(key);
Node p = null;
//如果鏈表為空，則直接回傳
if(this.head==null) {
return;
}
//特殊情況 頭刪
if(this.head.data==key) {
this.head = this.head.next;
System.out.println("洗掉成功!");
return;
}
//如果不存在前驅節點，說明要洗掉的節點不存在
if(prev==null) {
System.out.println("不存在該值!");
return;
}else {
p = prev.next;
prev.next = p.next;
System.out.println("洗掉成功!");
}
}
（7）洗掉所有值為key的節點
圖示：(假設洗掉所有值為1的節點)
代碼：
public void removeAllKey(int key) {
if(head==null){
return;
}
Node p = this.head.next;
Node prev = this.head;
//先呼叫查找方法確定待洗掉的結點是否存在
if(!findVal(key)) {
System.out.println("不存在該值!");
return;
}
//也可以對頭節點的判斷放到下面的while回圈里
// while(this.head.data==key&&this.head.next!=null) {
// this.head = this.head.next;
// p = this.head.next;
// prev = this.head;
// }
// if(p==null&&this.head.data==key) {
// this.head=null;
// }
while(p!=null) {
if(p.data==key) {
prev.next = p.next;
p = p.next;
}else {
prev = p;
p = p.next;
}
if(this.head.data==key) {
this.head = this.head.next;
}
}
System.out.println("洗掉成功!");
}
（8）尾刪法
public void popBack() {
Node p = this.head;
Node prev = null;
if(this.head==null) {
//如果鏈表頭為空，則直接回傳
return;
}
if(this.head.next==null) {
//如果表頭的next為空，則說明要洗掉的為鏈表頭
this.head = null;
System.out.println("尾刪成功!");
return;
}
//通過遍歷找到最后一個節點的前驅節點位置
while(p.next!=null) {
prev = p;
p= p.next;
}
prev.next = null;
System.out.println("尾刪成功!");
}
（9）清空單鏈表
public void clear() {
if(this.head==null) {
return;
}
this.head = null;
}
1.2.2無頭雙向非回圈鏈表的實作
首先先創建一個節點類，里面包含了data資料域、next域、prev域
class Node{
public int data;
public Node next;
public Node prev;
public Node(int data) {
this.data = data;
}
}
然后就是鏈表的介面和方法實作
public class MyDoubleLinkNode {
//定義雙向鏈表的頭和尾節點用來標記鏈表的頭部和尾部
public Node head;//頭節點
public Node tail;//尾節點
}
注意：以下方法均在MyDoubleLinkNode類中
（1）顯示單鏈表
public void display() {
if(this.head==null) {
System.out.println("Over!");
return;
}
Node p = this.head;
while(p!=null) {
//依舊采用回圈遍歷的方式
System.out.print(p.data+"->");
p = p.next;
}
System.out.println("Over!");
}
（2）頭插法
圖示：
代碼：
public void addFirst(int data) {
Node node = new Node(data);
if(this.head==null) {
//如果表頭為空，則讓head和tail都指向新節點node
this.head = node;
this.tail = node;
}else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
（3）尾插法
圖示：
代碼：
public void addLast(int data) {
Node node = new Node(data);
if(this.head==null) {
//如果表頭為空，則讓head和tail都指向新節點node
this.head = node;
this.tail = node;
}
//由于有表尾指標，所以不用遍歷尋找最后一個節點的位置
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
（4）單鏈表長度
public int size() {
int count = 0;
Node p = this.head;
while(p!=null) {
//依然采用遍歷思路
count++;
p = p.next;
}
return count;
}
（5）任意位置插入,第一個資料節點為0號下標
圖示：
代碼：
public boolean addIndex(int index,int data) {
if(index < 0) {
return false;
}
int size = this.size();
if(index == 0) {
//index==0呼叫頭插法
this.addFirst(data);
return true;
}
if(index == size) {
//index==size呼叫尾插法
this.addLast(data);
return true;
}
Node p = this.head;
Node node = new Node(data);
int n = index - 1;
while(n>0) {
//通過遍歷index-1次找到插入位置的前驅節點
p = p.next;
n--;
}
p.next.prev = node;
node.next = p.next;
node.prev = p;
p.next = node;
return true;
}
（6）查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key) {
if(this.head==null) {
return false;
}
Node p = this.head;
while(p!=null) {
//依然采用遍歷思路
if(p.data == key) {
return true;
}
p = p.next;
}
return false;
}
（7）洗掉第一次出現關鍵字為key的節點
圖示：
代碼：
public void remove(int key) {
//如果表中沒有該關鍵字直接回傳
if(!this.contains(key)) {
return;
}
Node p = this.head;
while(p!=null) {
//當關鍵字相等時，需要分情況
if(p.data==key) {
if(p == this.head) {
//當洗掉表頭節點時
this.head = this.head.next;
this.head.prev = null;
}else {
p.prev.next = p.next;
if(p.next!=null) {
//洗掉的不是尾節點
p.next.prev = p.prev;
}else {
//說明洗掉的是尾節點
this.tail = p.prev;
}
}
//到這洗掉完畢
return;
}else {
//只要關鍵值相等p就不往下走了，換言之不相等，p才會往下走
p = p.next;
}
}
}
（8）洗掉所有值為key的節點
public void removeAllKey(int key) {
if(this.head==null) {
return;
}
Node p = this.head;
while(p!=null) {
if(p.data==key) {
if(p == this.head) {
this.head = this.head.next;
this.head.prev = null;
}else {
p.prev.next = p.next;
if(p.next!=null) {
//洗掉的不是尾節點
p.next.prev = p.prev;
}else {
this.tail = p.prev;
}
}
}
//跟洗掉第一次出現關鍵字為key的節點不同的是讓p一直往下走，直到p==null,就可以洗掉所有的值為關鍵字的節點了
p = p.next;
}
}
（9）清空單鏈表
public void clear() {
if(this.head == null) {
return;
}
Node p = this.head;
while(p!=null) {
//通過遍歷讓每個節點的next和prev都指向null
Node s = p.next;
p.next = null;
p.prev = null;
p = s;
}
this.head = null;
this.tail = null;
}
1.3總結
- 鏈表以節點為單位存盤，不支持隨機訪問
- 任意位置插入時間復雜度為O(1)，
- 無擴容問題，插入一個開辟一個空間，
- 對于鏈表一些方法，建議多畫圖，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/254792.html
標籤：其他
上一篇：服務注冊中心：Eureka