iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
Software Development

算法30天系列 第 7

Day.7 鏈結

什麼是鏈結?
https://ithelp.ithome.com.tw/upload/images/20210915/20129767H5zc9FELzk.png

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

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

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

先定義結構:

// 節點的資料結構
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:

在讀取上會比較快,可以快速用index找出對應位置的資料 在插入跟刪除操作上比較麻煩
比起鏈結更省記錄體,因為不用存上下的關係。 有空間的限制

鏈結:

插入跟刪除的操作的速度較快 讀取速度比Array慢
沒有空間的限制 需要多花記憶體去記地址

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

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


上一篇
Day.6 線性資料
下一篇
Day.8 Reverse Linked List
系列文
算法30天30

尚未有邦友留言

立即登入留言