文章目錄
- 🥇雙鏈表簡單介紹：
- 🥇雙鏈表基本實作和各種功能實作：
- 🥇 雙鏈表和單鏈表的比較
- 🥇鏈表和順序表的優劣
🥇雙鏈表簡單介紹：
博主在前面介紹了單鏈表，并實作了它的基本功能，詳細請看博客單鏈表，相信有一點鏈表基礎的同學肯定會知道，單鏈表的每個節點都有兩部分組成那就是資料域和指標域，指標域指向下一個節點中資料域的地址，而雙鏈表一個節點中包含三個部分，數值域，指向后繼節點的指標，還有指向前驅節點的指標，它在單鏈表的基礎上優化了很多，例如尾插法等就不用了逐個遍歷鏈表節點，直接就可以找到鏈表的為節點，實作與添加的新節點連接，
那讓我們看看他的廬山真面目吧
🥇雙鏈表基本實作和各種功能實作：
新建MydoubleLinkedList.java檔案在該檔案中實作雙向鏈表的所有基礎操作
新建TestDemo，java檔案在檔案中實作雙向鏈表的測驗，測驗雙向鏈表的功能，
class Node{
public int val; //數值域
public Node next; //后繼
public Node prev; //前驅
public Node(int val){
this.val = val;
}
}
public class MydoubleLinkedList {
//創建頭節點
public Node head;
//創建尾節點
public Node tail;
}
雙鏈表之列印鏈表：
public void print(){
Node cur = this.head;
while(cur!=null){
System.out.print(cur.val + " ");
cur = cur.next;
}
}
雙鏈表之求鏈表長度
public int size(){
Node cur = this.head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
雙鏈表之尋找鏈表中是否含有某個數字:
public boolean isContains(int val){
if(this.head == null){
return false;
}
Node cur = this.head;
while(cur!=null){
if(cur.val == val){
return true;
}
cur = cur.next;
}
return false;
}
雙鏈表之頭插法：
終于到我要給大家介紹的重點了，前面的三種功能和單鏈表基本沒有區別，沒有使用雙向鏈表中的前驅節點，
💡演算法思想：
- 第一步還是判斷鏈表是否為空，為空就回傳新加節點node
- 將新節點插入鏈表頭部，新的頭節點就要發生變化，
它的后繼node.next = this.head;也就是新鏈表的頭節點的后繼指標域指向原鏈表頭節點的地址當然原鏈表頭節點的前驅也就變成了新加入的node，即this.head.prev = node,然后新鏈表真正的頭節點this.head = node;
看圖說話：
💯代碼：
public Node addFirst(int val){
Node node = new Node(val);
if(this.head == null){
return node;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
return head;
}
雙鏈表之尾插法：
💡演算法思想：
- 還是判斷鏈表是否為空，為空就回傳新加節點node
- 因為在建立鏈表時，已經規定了尾節點tail，所以在這里不用在鏈表中從頭節點遍歷，找到尾節點，我們直接就可以讓鏈表的
尾節點tail的后繼指標指向新加節點，即this.tail.next = node,還要把新節點的前驅指標指向原鏈表的尾節點即node.prev = this.tail,然后新節點就變成鏈表中新的尾節點 即this.tail = node
看圖說話：
💯 代碼：
public Node addLast(int val){
Node node = new Node(val);
if(this.head == null){
return node;
}
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
return this.head;
}
雙鏈表之在鏈表任意節點添加
💡演算法思想：
- 判斷傳來的陣列下標是否合法，如果不合法就回傳下標不合法
- 如果下標為0，也就是頭插法，呼叫頭插法方法就是了
- 如果下標為鏈表的長度，那么就直接呼叫尾插法就是了
- 如果所插節點的下標既不是0也不是和鏈表等長的下標，那么
先遍歷到原鏈表的這個下標，讓所添加節點的后繼指標指向下標這個節點，即node.next = cur，然后讓原下標節點的前驅節點的后繼指標指向所添加節點，即cur.prev.next = node;然后讓所添加節點的前驅指標指向原下標節點的前驅節點,即node.prev = cur.prev;最后讓原下標節點的前驅指標指向所添加節點，即cur.prev = node;
看圖說話：
💯 代碼：
public void addNode(int index,int val){
if(index < 0 || index > size()){
System.out.println("下標不合法！！！");
return;
}
if(index == 0){
addFirst(val);
return;
}
if(index == size()){
addLast(val);
return;
}
//如果添加的位置不是下標為0，或者是鏈表最后一位添加
//先找到具體下標
Node node = new Node(val);
Node cur = findIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
node.prev = node;
}
public Node findIndex(int index){
int count = 0;
Node cur = this.head;
while(count != index && cur != null){
count++;
cur = cur.next;
}
return cur;
}
雙向鏈表之洗掉第一次出現的的val值
💡 演算法思想：
- 在洗掉節點時，我們不需要像單鏈表一樣從后向前找到鏈表可刪節點的前驅節點，我們只需要找到這個可刪節點，讓
可刪節點的前驅節點的后繼指標指向可刪節點的后繼節點，即node.prev.next = node.next;讓可刪節點的后繼節點的前驅指標指向可刪接單的前驅即node.next.prev = node.prev; - 當頭節點為可刪節點，讓鏈表的新頭節點向原鏈表頭節點的后繼節點，即
this.head = this.head.next,還有將新頭節點的前驅置為null，即this.head.prev = null - 當鏈表的尾節點為可刪節點，那么就讓尾節點的前驅節點的后繼指標為null,即
this.tail.prev.next = null,也可以寫成this.tail.prev.next = this.tail.next,然后指向新的尾節點this.tail = this.tail.prev
看圖說話：
💯 代碼：
public void remove(int key) {
Node cur = this.head;
while (cur != null) {
if(cur.val == key) {
//判斷是不是頭節點
if(cur == this.head) {
this.head = this.head.next;
if(this.head == null) {//防止只有1個節點的
this.tail = null;
}else {
this.head.prev = null;
}
}else {
cur.prev.next = cur.next;
//尾巴節點
if(cur.next == null) {
this.tail = cur.prev;
}else {
cur.next.prev = cur.prev;
}
}
return;
}else {
cur = cur.next;
}
}
}
雙鏈表之洗掉鏈表中所有的val值
💡演算法思想：
- 和洗掉節點一樣只是要去掉代碼中的return，讓代碼回圈，直到把val值全部洗掉完，
💯 代碼：
public void remove(int key) {
Node cur = this.head;
while (cur != null) {
if(cur.val == key) {
//判斷是不是頭節點
if(cur == this.head) {
this.head = this.head.next;
if(this.head == null) {//防止只有1個節點的
this.tail = null;
}else {
this.head.prev = null;
}
}else {
cur.prev.next = cur.next;
//尾巴節點
if(cur.next == null) {
this.tail = cur.prev;
}else {
cur.next.prev = cur.prev;
}
}
return;
}else {
cur = cur.next;
}
}
}
🥇 雙鏈表和單鏈表的比較
- 雙鏈表和單鏈表比較，雖然雙鏈表添加了一個前驅指標域，但是他在實作某些功能時，是真的比單鏈表方便，比如我們要洗掉節點就不需要遍歷可刪節點的前驅節點，就少了一步遍歷鏈表的步驟，還有雙向鏈表可以雙向遍歷，單鏈表只可以從頭節點依次遍歷到鏈表的尾節點，為實作功能帶來諸多不便，
🥇鏈表和順序表的優劣
和陣列相比，鏈表更適合儲存一個大小動態變化的資料集，如果需要在一個資料集中頻繁的添加新的資料并且不需要考慮資料集的順序，那么可以用鏈表來實作這個資料集，鏈表中的插入操作可以用O(1)的時間來實作，其次鏈表的洗掉操作也可以用O(1)的時間來實作，所以是當要實作某些資料集的插入或洗掉時，可以考慮鏈表使用，當時在查找時鏈表又有了弊端，他只能從鏈表的頭節點遍歷到鏈表的尾節點找到要查找的數值，時間復雜度為O(n).
和鏈表相比，陣列在讀取數值時，用著很大的優勢，可以憑借陣列下標來讀取陣列中的每個數字，但是要實作添加數字，和洗掉數字時，要移動大量的數值，并且時間復雜度為O(n),還有在創建陣列時，要預先指定陣列的容量大小，然后根據容量的大小分配記憶體，即使只在陣列中存盤一個數字，也需要為所有的資料預先分配記憶體，依次陣列的空間利用率不高，可能會有空閑的空間沒有得到充分使用，并且當陣列容量不夠時，需要重新分配一個較大的空間，通常增加后的陣列容量時原來的兩倍，每次擴充陣列容量時，都會有大量操作，這是時間性能有負面影響，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298367.html
標籤：其他