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~


<<:  ASP.NET MVC 从入门到放弃(Day10) -C# get set 自动属性介绍

>>:  Day1 前言

DAY07 - [CSS+RWD] 导览列

今日文章目录 > - 导览列 > - 练习演示 > - 遇到的问题 > -...

Day01,旅途的起点

前言 这次预计用这30天,来执行一轮乱七八糟的HomeLab,内容将会涵盖许多不同领域的范畴但不会探...

【Day10】表单 Form:受控元件 Controlled Component

在 React 中,允许直接用 HTML 来建立表单, 但使用 JavaScript functio...

DAY7 浅扒网路 - 估计被扒皮的是我不是网路

「将127.0.0.1改成内网IP」,这是上一篇的某个步骤,没浅浅扒一下网路基础,对学习有点影响~~...

建立第一个RESTful api server(连结资料库篇)-1 (Day17)

在一个网页後端程序中,主要都是负责资料的处理,关於资料的储存则是会交由专门处理资料库的系统来处理 而...