線性的資料儲存方式一般有兩種

1. array (陣列)
2. list node (鏈結)

這兩種差別到底在那，幹嘛不都用array就好了，簡單易用！？

為了要解釋這個，我來先說一下array背後的儲存方式。

ex. var arr [4]int
在背後Go會分配一個連續的記憶體去存放這個array
當你定下這個長度4之後，空間的大小就固定了，之後沒辦法擴大。
如果你要存第5個數值，你只能先定義一個更大的array，再用copy的方式，把舊資料放到新的連續空間。

Golang為了幫使用者解決這個麻煩，所以出了Slice的資料結構，不需要先定義好空間大小，用append的方式去動態新增，下面簡單說一下它的原理。

來看程式:

a := make([]int, 1, 10) // len:1 cap:10
b := []int{1, 2}        // len:2 cap:2  
c := append(a, b...)

fmt.Printf("cap: %v, len: %v ptr: %v \n", cap(a), len(a), &a[0])
fmt.Printf("cap: %v, len: %v ptr: %v \n", cap(c), len(c), &c[0])

output:

// 兩個地址是一樣
cap: 10, len: 1 ptr: 0xc000118000 
cap: 10, len: 3 ptr: 0xc000118000

a的空間是10,使用長度為1
b的空間是2,使用長度為2
在append的時候，Golang會發現a的空間是足夠可以放在b
所以會在a[0]後面加上b[0],b[1]
我們可以發現c[0],a[0]指向的地址是一樣的，如果這時候把c[0]的值改掉，a[0]也會被改掉哦。

這是a空間可以放得下b的情境。
那如果放不下，Golang會分配新的連續空間，用copy的方式把a、b的值存進去。

程式:

a := []int{1, 2} // len:2 cap:2
b := []int{3, 4} // len:2 cap:2  
c := append(a, b...)

fmt.Printf("cap: %v, len: %v ptr: %v \n", cap(a), len(a), &a[0])
fmt.Printf("cap: %v, len: %v ptr: %v \n", cap(c), len(c), &c[0])

output:

// 兩個地址是不一樣的哦
cap: 2, len: 2 ptr: 0xc0000140d0 
cap: 4, len: 4 ptr: 0xc0000200c0

array & slice都是連續的空間，所以在一些情境下的操作時會滿麻煩的，來看一下這個例子。

sorted := []int{1,3,4,5,6}
如果要把數字2，按照順序insert到sorted的slice裡面，要怎麼做？

插入的位置是在1的後面，而後面的3,4,5,6都要往右移一個位置
但在6再往右的時候，會超越slice的空間，所以需要先append一個值進去

這樣做的時間複雜度為O(n)，因為在插入點後面的值，都要往右移，而且要注意空間夠不夠。

那有沒有資料結構可以不用管空間夠不夠，在新增刪除上又可以更方便？
明天講～