iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
Software Development

算法30天系列 第 6

Day.6 線性資料

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

  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),因為在插入點後面的值,都要往右移,而且要注意空間夠不夠。

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


上一篇
Day.5 Slide Window
下一篇
Day.7 鏈結
系列文
算法30天30

尚未有邦友留言

立即登入留言