---
title: 'Array鏈結串列'
disqus: kyleAlien
---

Array 鏈結串列
===

## OverView of Content
如有引用參考請詳註出處，感謝 :smile_cat:

> 注意: 鏈結的首節點很重要

[TOC]

## 動態記憶體配置
| Compare | dynamic配置 | static配置 |
| ---------- | ------------------------------------------------------------------------ | -------------------------------------------- |
| 配置時間 | 執行期間(Running Time) | 編譯期間 |
| 執行效能 | 效能較低，因為在執行期才決定 Addr | 效能較高，由於在靜態時配置所以 Addr 不會更動 |
| 記憶體釋放 | 必須手動釋放 | 依照程式生命週期一起結束 |
| 配置問題 | 記憶體如果不釋放，可能會造成記憶體缺口，(強引用)不易回收，導致浪費記憶體 | 可能浪費多餘空間 |
* 如果是 C 語言必須手動釋放記憶體，否則會造成記憶體浪費
* Java 有垃圾回收機制(GC)，會自動回收不使用的記憶體區塊，但建議要把不使用的區塊**指向 null 促進(GC)回收**

| HowToUse | Java | C\C++ |
| -------- | ---------- | -------------------- |
| Type | Class、new | typedef、struct、ptr |

## 單向鏈結串列
* 像**單向列車**
* 接下來手作一個 LinkedList 為 HandlerLinkedList

| Func Name | 功能 |
| ------------ | ---------------- |
| isEmpty() | 檢查是否為空 |
| insert(Node) | 插入元素 |
| delete(int) | 刪除某元素 |
| print() | 印出所有串列元素 |

class Node {
    int data, SN;    // serialNumber => SN
    String name;
    Node next;
    
    Node(int SN) {
    	this.SN = SN;
    	this.name = "";
    	this.next = null;
    }
    
    Node(int SN, String name, int data) {
        this.data = data;
        this.name = name;
        this.SN = SN;
        "1: "
        this.next = null;
    }
}

class HandlerLinkedList {
    "2: "
    Node first = null, last = null;
    
    boolean isEmpty() {
        return first == null;
    }
    
    void hint(String h) {
        System.out.println("Hint: " + h);
    }
    
    "3: "
    void insert(Node node) {
        if(isEmpty()) {    // 先判空
            first = node;
            last = node;    
            // 起點終點都一樣
            hint("目前 List 為空，已加入第一個節點");
        } else {
        	
        	if(node.next == first) {    // 指向第一個節點
        		node.next = first;
        		first = node;
        		hint("insert First");
        	} else {
        		if(node.next == null) { // 無指向節點
        			last.next = node;
        			last = node;
        			hint("insert Last");
        		} else {
        			Node temp = first;
        			Node saveTemp = first;
        			
        			while(temp.next != node.next) {
        				saveTemp = temp;
        				temp = temp.next;
        			}
        			saveTemp.next = node;
        			node.next = temp;

        			hint("insert Middle");
        		}
        	}
        	
            //last.next = node;
            //last = node;	// 重新指定最後一個節點
        }
    }
    
    "4: "
    void delete(Node node) {
        if(isEmpty()) {    // 判空
            hint("目前 List 為空，無法刪除節點");
            return;
        }
        
        Node temp;
        if(node.SN == first.SN) {
            first = first.next;
            hint("刪除首節點");
        } else if(node.SN == last.SN) {
            temp = first;
            while(temp.SN != last.SN) {
            	if(temp.next.SN == last.SN) {
            		break;
            	}
                temp = temp.next;
            }
            last = temp;
            last.next = null;    // 並指讓last 最後指向 null
            hint("刪除尾節點");
        } else {
            temp = first;
            while(temp.SN != node.SN) {
            	if(temp.next.SN == node.SN) {
            		break;
            	}
                temp = temp.next;
            }
            temp.next = temp.next.next;
            hint("刪除中間節點");
        }
        hint("首節點 SN: " + first.SN + "\t 尾節點 SN: " + last.SN);
    }
    
    void print() {
        Node temp = first;
        while(temp != null) {
            System.out.println("temp.SN: " + temp.SN + "\t" + 
                               "temp.name: " + temp.name + "\t" + 
                               "temp.data: " + temp.data + "\t");
            temp = temp.next;
        }
    }
}

* 1: 當串見出一個節點時，預設此結點無下一個節點
* 2: **單向串列的首極為重要**，因為它是一個串列的起點，單向串列隨意一個節點一定知道下一個節點要指向何方，但卻不知道前一個節點要指向何方，所以串列首極為重要，**非必要時不會去改變串列首，否則可能會造成記憶體無法回收造成記憶體缺口**; 串列尾一定指向 null;
* 3: **加入節點後要重新指定最後一個節點(即新插入的節點)**
* 4: 刪除節點是比對 SN (Serial Number)，並且**刪除有三種處理方式，首刪除、尾刪除、中間刪除**
> 首: 讓 first 改變為 first.next
> 尾: 搜尋到 last 前一個，重新指定 last，**並讓 last.next 指向 null**
> 中: 搜尋到 node 前一個，並重新指定 temp.next = temp.next.next

import java.util.Random;

public class startCoding {
	public static void main(String[] args) {
		Random random = new Random();
		int[][] data = new int[12][2];
		String[] names = {"Alien", "Ban", "Car", "Drive", 
						  "Eve", "Friend", "Game", "Hand",
						  "Ido", "Jack", "Kyle", "Long"};
		HandlerLinkedList list = new HandlerLinkedList();
		
		for(int i = 0; i < 12; i++) {
			data[i][0] = i + 1;
			int score = random.nextInt(50) + 50;
			data[i][1] = score;
			
			list.insert(new Node(data[i][0], names[i], data[i][1]));
		}
		
		list.print();
		
		list.delete(new Node(10,"",0));
		
		System.out.println("---刪除 node 後---");
		
		list.print();
	}
}

**--實做--**
> 
>

### 兩個單向串接

// HandlerLinkedList 內部新增
HandlerLinkedList concat(HandlerLinkedList n1, HandlerLinkedList n2) {
    	HandlerLinkedList ptr = n1;
    	while(ptr.last.next != null) {
    		ptr.last = ptr.last.next;
    	}
    	ptr.last.next = n2.first;
        ptr.last = n2.last;
    	return ptr;
    }

**--實做--**
> 

### 單向鏈結反轉

// HandlerLinkedList 內部新增
void reverse() {
    	Node temp = first, cache = null;
        Node yo;
    	
    	// 反轉的起點是 cache
    	while(temp != null) {
    		
    		yo = cache;         // 暫存上一個節點
    		cache = temp;		// first 1 -> 2 -> 3 -> 4 -> 5...
    		temp = temp.next;	// 正向更新
    		
    		cache.next = yo;  // 1.next -> null
    							// 2.next -> 1
    							// 3.next -> 2
    							// 4.next -> 3		... 依此類推
    	}
    	
    	while(cache != null) {
    		System.out.println("Reverse cache : " + cache.SN);
    		cache = cache.next;
    	}
    }

**--實做--**
> 

## 環狀鏈結串列
* 像**摩天輪**
* 與單向鏈結很像，但是多了**串列尾端連接到首端**

public class CircleList {
	Node first = null, last = null;
	
	private void hint(String str) {
		System.out.println("hint: " + str);
	}
	
	boolean isEmpty() {
		return first == null;
	}
	
	void insert(Node node) {
		if(isEmpty()) {
			first = node;
			last = node;
			last.next = first;
			//first.next = last; 這樣會變雙向
			hint("Circle List is Empty, Insert First");
			return;
		} else {
			last.next = node;
			last = node;
			last.next = first;
			hint("Insert at last");
		}
	}
	
	void delete(Node node) {
		if(isEmpty()) {
			hint("Circle List is Empty, Cannot delete");
			return;
		}
		
		if(node.SN == first.SN) {
			first = first.next;
			last.next = first;
			hint("circle delete first");
		} else if(node.SN == last.SN) {
			Node temp = first;
			while(temp.next.SN != last.SN) {
				temp = temp.next;
			}
			last = temp;
			last.next = first;
			hint("circle delete last");
		} else {
			Node temp = first;
			
			while(temp.next.SN != node.SN) {
				if(temp.next.SN == first.SN) {
					break;	// 避免無窮迴圈
				}
				temp = temp.next;
			}
			temp.next = node.next;
			
			hint("circle delete middle");
		}
	}
	
	void print() {
		Node temp = first;
		
		while(temp.next != first) {
            
			info(temp);
            
			temp = temp.next;
		}
        
		"1: "
		info(temp.next);
	}
    
    private void info(Node temp) {
        System.out.println("temp.SN: " + temp.SN + "\t" + 
                "temp.name: " + temp.name + "\t" + 
                "temp.data: " + temp.data + "\t");
    }
    
    void size() {
        int  i;
        
        if(isEmpty()) {
            i = 0;
        } else {
            Node temp = first;
            Node saveTemp = first;
            while(temp.next != saveTemp) {
                i++;
                temp = temp.next;
            }
            "2: "
            i++;
        }
        return i;
    }
}

* 1: 最後一個由於重複到開始節點，所以在單獨打印一次
* 2: 計算大小可用兩個指標計算，跳出 while 後再加一次是加最後一個節點

:::warning
**環狀鏈結在插入、刪除時要注意，因為是循環連結可能會造成無限迴圈**
:::

## 雙向鏈結串列
* 像**來回雙向列車**(Double Linked List)
* 雙向鏈結的 Node 多了一個指標 (也就是兩個指標在 Node) 可以指回上一個節點，在移動時需要花較多時間移動指標

public class StartCoding {

	public static void main(String[] args) {
		DoubleSidedList list = new DoubleSidedList();

		for(int i = 0; i < 12; i++) {
			list.insert(new Node(i+1));
		}
		
		list.print();
		
		Node n = new Node(list.first.SN);
		n.next = list.first.next;
		while(n.SN != 5) {
			n = n.next;
		}
		list.delete(n);
		
		System.out.println("---刪除 node 後---");
		
		list.print();
	}
}

class Node {
	Node pre;
	Node next;
	int SN;		// Serial Number
	Node(int SN) {
		this.SN = SN;
		pre = null;
		next = null;
	}
}

class DoubleSidedList {
	
	Node first = null;
	Node last = null;
	
	void hint(String h) {
        System.out.println("Hint: " + h);
    }
	
	boolean isEmpty() {
		return first == null;
	}
	
	void insert(Node node) {
		if(isEmpty()) {
			first = node;
			first.next = last;	// ptr to itself
			last = node;
			last.pre = first;
			hint("data insert empty double list");
		} else {
			if(node.next == first) {	// insert header
				node.next = first;
				node.pre = first;
				first = node;
				hint("data insert header");
			} else {
				if(node.next == null) {	// insert last
					last.next = node;
					node.pre = last;
					last = node;
					hint("data insert last");
				} else {
					Node temp = first;
					Node saveTemp = first;
					
					while(temp != node) {
						saveTemp = temp;
						temp = temp.next;
					}
					// ptr to next
					saveTemp.next = node;
					node.next = temp;
					// ptr to pre
					temp.pre = node;
					node.pre = saveTemp;
					
					hint("data insert middle");
				}
			}
		}
	}
	
	void delete(Node node) {
		if(isEmpty()) {
			hint("cannot delete empty data in double list");
			return;
		}
		
		if(node.SN == first.SN) {
			first = first.next;
			first.pre = null;
			hint("delete header");
		} else if(node.SN == last.SN) {
			last = last.pre;
			last.next = null;
			hint("delete last");
		} else {
			Node temp = first;
			Node saveTemp = first;
			
			while(temp.SN != node.SN) {
				saveTemp = temp;
				temp = temp.next;
			}
			saveTemp.next = node.next;
			node.pre = saveTemp;
			
			hint("delete middle");
		}
	}
	
	void print() {
		Node temp = first;
		while(temp != null) {
            System.out.println("temp.SN: " + temp.SN + "\t");
            temp = temp.next;
		}
	}
	
}

**--實作--**
> 

## Appendix & FAQ

:::info
:::

###### tags: `資料結構`