什麼是鏈結？

每一個節點上，都記著了下一個節點的地址
這樣做法的好處是可以用非連續的空間來儲存資料，避免掉連續空間會不足的問題

這種資料結構叫單向鏈結，每一個節點會知道下一個節點在那，但不知道上一個點，是單向的。

我們來實作一下，看完在語言層面上是怎麼實作的，相信你會比較明白。

先定義結構:

// 節點的資料結構
type ListNode struct {
	Data int       // 儲存資料
	Next *ListNode // 下一個節點的地址
}

// 單向鏈結
type SingleLink struct {
	head *ListNode // 記下最初的節點
	tail *ListNode // 記下最後一個節點
	len  int       // 總長度
}

新增節點

func (s *SingleLink) Add(data int) {
	s.len++

	// 判斷是否空鏈結
	if s.head == nil {
		// 最初的節點
		s.head = &ListNode{
			Data: data,
		}
		// 最後一個節
		s.tail = s.head

		return
	}

	// 新增在最後一個節點的下一個節點
	s.tail.Next = &ListNode{
		Data: data,
	}
	// 更新最後一個節
	s.tail = s.tail.Next
}

讀取全部的節點資料

func (s *SingleLink) ShowLink() {
	i := 1
	node := s.head
	for node != nil {
		fmt.Printf("i: %v, val: %v \n", i, node.Data)

		i++
		node = node.Next
	}
}

刪除節點

/*
    ex. 
    1->2->3->4
    prev: 2
    node: 3 (next: 4)
    prev.next = node.next

    1->2->4
    3就從鏈結消失了
*/
func (s *SingleLink) Remove(index int) {
	if s.len == 0 {
		return
	}
	// 把第一個節點去掉
	if index == 1 {
		s.head = s.head.Next
		return
	}

	i := 2
	prev := s.head      // 記下前一個節點
	node := s.head.Next // 目前節點

	for node != nil {
		if i != index {
            // 再往下找
			i++
			prev = node
			node = node.Next
			continue
		}

		// 把中間的節點去掉
		prev.Next = node.Next
		s.len--

		// 如果刪除的是最後一個節點，就要更新tail的pointer
		if node == s.tail {
			s.tail = prev
		}

		break
	}
}

簡單說一下時間複雜
新增是O(1)，每次都只要新增節點在最後就行了。
讀取是O(n)，每次都要在鏈結從頭開始找。
刪除是O(n)，刪除的本身操作是O(1)，但你為了要找到對應的位置，所以要從頭往下找。

到這裡我們做一個簡單的總結，這兩個資料結構有什麼優缺，什麼情況要用那一個

Array:

鏈結:

Golang有供提Slice的用法，一樣來說不需要管到空間夠不夠的問題，大部分情境用Slice就夠了。
但如果現在需要對一個位置很頻繁的插入新的資料，用鏈結會比較適合，雖然讀取的成本是O(n)，但找到對應的位置後，插入的成本都只有O(1)。

明天來用鏈結來解一下leetcode~