# 單元三 鏈結串列(LinkedList)
:::success
可以比較有彈性的擴充，實現靈活的記憶體動態管理。
:::

## 指標

int *p; // 指標 並非int變數 而是指向int的一個門牌
// 上面這樣還沒有分配到記憶體空間 因此還無法使用。
int x; // 宣告int變數
p = &x; // 將p指向x的記憶體空間。
p = new int; // 幫助p指向一個int的空間，
*p = 2;
delete p; // 將p指向的資料刪除
p = NULL; // 必須要這麼做，防止指標誤用記憶體空間。

:::danger

記住在使用指標時，必須小心memory leak的問題。
如果在 delete p 下面打 cout << p << '\n'; 會出事
:::

## 動態陣列

可以利用動態的方式去產生陣列，增加了彈性
:::warning
動態陣列如果已經滿了 必須要再宣告新的更大的陣列，並且搬動原陣列的資料。
:::

    int arraySize = 50;
    double *arr = new double[arraySize];
    
    // 以下是如果上面滿了該做的事情 只是示範而已
    double *newarr = new double[arraySize * 3];
    for(int i = 0 ; i < arraySize ; i++){
        newarr[i] = arr[i];
    }
    // 記得要delete掉舊的array
    delete [] arr;
    arr = newarr;
    

## 來開始實作LinkedList吧

// C++ 11
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<sstream>

template <typename T>
struct Node {
	T num; // 資料
	Node * next; // 下一個點 
};

// 利用泛型實作LinkedList
// 殘缺的LinkedList, 不過可以應付這題
template <typename T>
class LinkedList {
	public:
		// 建構子
		// 初始化資料
		LinkedList() {
			head = NULL; // 頭先設定為NULL 
			tail = NULL; // 尾也先設定為NULL 
			size = 0;
		}

		// 把資料放進去
		void push(T data) {
			// 如果裡面空空的
			if(size==0) {
				head = new Node<T>; // 讓head變成新的Node
				head -> num = data; // 把資料放進去
				head -> next = NULL; // 指定head的next是null
				size++; // 讓size++
				tail = head;// 讓tail變成head
				return; // return 回去 避免進入下一行
			}

			// 要是不是空的話
			tail -> next = new Node<T>; // 先讓tail的下一個變成新的Node
			tail = tail -> next; // 把tail 移到下一層
			tail -> num = data;// 把資料放進去
			tail -> next = NULL; // tail的下一個指定為NULL
			size++;// size增加
			return;// return 回去 可加可不加
		}

		// 單純的複製LinkedList
		// 這邊是產生一個新的LinkedList 而不是把原本的return回去
		// 因為如果是把原本的return回去，會導致資料會被互相引響
		LinkedList copy() {
			LinkedList toReturn; // 準備回傳回去的資料
			Node<T> * temp = head; // 指標 用來走訪整個LinkedList
			while(temp!=NULL) {
				toReturn.push(temp->num); // 透過方法一直去push資料
				temp = temp -> next;
			}
			return toReturn; // return

		}

		// 透過 index 去取得資料
		T getDataFromIndex(int k) {
			Node<T> * temp = getFromIndex(k);
			return temp -> num;
		}

		// 透過index 移除資料 並且將資料回傳 
		T removeFromIndex(int k) {
			// 如果k的大小==0 就代表刪掉頭 
			if(k==0){
				if(head==NULL) return NULL;
				T n = head -> num;
				head = head -> next;
				size--;
				return n;
			}
			// 如果k小於0或者不小於size 就代表越界 因此直接return NULL 
			if(k>=size || k < 0) return NULL;
			
			// 暫時的節點 用來儲存即將被刪除的節點的上一個節點 
			Node<T> * temp = getFromIndex(k-1);
			if(temp==NULL) return NULL; // 如果取不到 就代表越界 直接return NULL 
			T n = temp -> next -> num; // N是即將被回傳的值 也就代表被刪除的節點的值 
			temp -> next = temp -> next -> next; // 讓next指向更下一層的節點 
			size--; // size記得要-1 
			return n; // return value
		}

		// 取得大小 
		int getSize() {
			return size;
		}
        
        // 排序 
        void sortList(){
            head = mergeSort(head);
        }



	// 不公開的 
	private:
		Node<T> * head;
		Node<T> * tail;
		int size;

		// 這邊之所以放在private 是為了防止有人透過此方法破壞LinkedList 
		// 此方法單純就是將第i個Node回傳 
		Node<T> * getFromIndex(int i) {
			if(i==0) return head;
			if(i>=size) return NULL;
			Node<T> * temp = head;
			for(int j = 0 ; j < i ; j++) {
				temp = temp -> next;
			}
			return temp;
		}
        
        // 將節點排序 
        Node<T> * mergeSort(Node<T> * h){
            // 如果h的大小只有1或者是根本沒東西 直接回傳h 
            if(h==NULL||h -> next == NULL) return h;
            // 找出中心點
            Node<T> * slow = h;
            Node<T> * fast = h -> next;
            while(fast!=NULL&&fast-> next!=NULL){
                fast = fast -> next;
                slow = slow -> next;
            }
            Node<T> * mid = slow -> next;
            // 找到中心點後 分割開前半部以及後半部 
            slow -> next = NULL;
            // 再度分割前半部 並且等待回傳的結果 
            Node<T> * left = mergeSort(h);
            // 再度分割後半部 並且等待回傳的結果 
            Node<T> * right = mergeSort(mid);
            // 開頭 
            Node<T> * ans = new Node<T>;
            // 結尾 
            Node<T> * last = ans;
            
            // 跑回圈 逐漸合併各個節點 並且回傳回去 
            while(left!=NULL||right!=NULL){
                T n1 = (left != NULL? left -> num : INT_MAX );
                T n2 = (right != NULL? right -> num: INT_MAX );
                if(n1<n2){
                	last -> next = left;
                	left = left -> next;
				}
				else{
					last -> next = right;
					right = right -> next; 
				}
				last = last -> next;
            }
            return ans -> next;
        }    
};

:::success
以上只是LinkedList的一種寫法
:::

## 比較Array跟LinkedList

|差異 |Array |LinkedList |
| -------- | -------- | -------- |
|彈性| 較不彈性| 較彈性
|占用的記憶體空間 | 較少 | 較大|
|取得檔案| 較快|較慢
|插入和刪除|較不容易|較容易

## LinkedList的變形
|種類 |特點
| -------- | -------- |
|Circular LinkedList| 將dummy設在最後一個節點，並且將next設定成head。在需要取得很多次tail的時候可以應用 。
|Dummy Head Node |一直都存在著 即使List是空的，可以避免掉一些Special Case|
|Doubly LinkedList|多了一個指向前一個節點的LinkedList，比較容易找到和刪除跟修改節點。比起原本的LinkedList有更好的應用。代價就是占用較大的記憶體空間。|