什麽是链结?
每一个节点上,都记着了下一个节点的地址
这样做法的好处是可以用非连续的空间来储存资料,避免掉连续空间会不足的问题
这种资料结构叫单向链结,每一个节点会知道下一个节点在那,但不知道上一个点,是单向的。
我们来实作一下,看完在语言层面上是怎麽实作的,相信你会比较明白。
先定义结构:
// 节点的资料结构
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 自动属性介绍
今日文章目录 > - 导览列 > - 练习演示 > - 遇到的问题 > -...
前言 这次预计用这30天,来执行一轮乱七八糟的HomeLab,内容将会涵盖许多不同领域的范畴但不会探...
在 React 中,允许直接用 HTML 来建立表单, 但使用 JavaScript functio...
「将127.0.0.1改成内网IP」,这是上一篇的某个步骤,没浅浅扒一下网路基础,对学习有点影响~~...
在一个网页後端程序中,主要都是负责资料的处理,关於资料的储存则是会交由专门处理资料库的系统来处理 而...