链表
image.png
缺点：查找复杂
有点：定点删除／插入元素
单链表
type ListNode struct {
Val int
Next *ListNode
}
image.png
双向链表
type ListNode struct {
Val int
Prev *ListNode
Next *ListNode
}
image.png
循环链表
image.png
双向循环链表
image.png
数组与链表的区别
数据存储：数组必须要有连续的内存空间，链表不需要
数据存取特点：插入删除，随机访问时间复杂度正好相反
image.png
示例：LRU缓存淘汰策略
常见的缓存淘汰策略：
先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
LRU
距离当前最久没有被访问过的数据应该被淘汰
package linked_list2
import (
"errors"
"fmt"
"testing"
)
//链表结构
type ListNode struct {
data int
next *ListNode
}
//初始化链表头，下面的所有操作都是基于带头链表
func NewListNode() *ListNode {
return &ListNode{next: nil}
}
//获取链表的长度
func (l *ListNode) Length() int {
len := 0
for l.next != nil {
len++
l = l.next
}
return len
}
//插入节点
func (l *ListNode) InsertNode(d int) error {
fmt.Println("InsertNode", d)
newNode := new(ListNode)
newNode.data = d
newNode.next = l.next
l.next = newNode
return nil
}
//删除节点
//注意：如果直接操作 l = l.next l的指向会发生变化
//注意：如果直接 temp = l.next ; temp = temp.next 不会对 l 链表有影响
func (l *ListNode) DelNode(d int) {
if l == nil {
errors.New("Empty List!")
return
}
for l.next != nil {
if l.next.data == d {
l.next = l.next.next
continue
}
l = l.next
}
}
//遍历链表
func (l *ListNode) ListNode() {
fmt.Print("range :")
for l.next != nil {
fmt.Printf(" %d", l.next.data)
l = l.next
}
fmt.Println("")
}
//获取链表第一个元素
func (l *ListNode) GetFirstNode() *ListNode {
return l.next
}
//递归单链反转
func ReverseList(pHead, node *ListNode) *ListNode {
if node.next == nil {
pHead.next = node
return node
}
n := ReverseList(pHead, node.next)
if n != nil {
n.next = node
node.next = nil
}
return node
}
//遍历单链反转方法
func (pHead *ListNode) ReverseListV2() {
pReversedHead := pHead
var pNode = pHead.next
var pPrev *ListNode
for pNode != nil {
pNext := pNode.next
if pNext == nil {
pReversedHead.next = pNode
}
pNode.next = pPrev
pPrev = pNode
pNode = pNext
}
return
}
func TestLinkedList2(t *testing.T) {
//新建单链表
//
l := NewListNode()
l.ListNode()
l.InsertNode(1)
l.ListNode()
l.InsertNode(2)
l.ListNode()
l.InsertNode(3)
l.ListNode()
fmt.Println("first:", l.GetFirstNode().data)
fmt.Printf("before del l:%p\n", l)
l.DelNode(2)
fmt.Printf("after del l:%p\n", l)
l.ListNode()
}
如何轻松写出正确的链表代码？
技巧一：理解指针或引用的含义
p->next=q
技巧二：警惕指针丢失和内存泄漏
p->next = x; // 将 p 的 next 指针指向 x 结点；
x->next = p->next; // 将 x 的结点的 next 指针指向 b 结点；
image.png
插入结点时，一定要注意操作的顺序
删除链表结点时，也一定要记得手动释放内存空间
技巧三：利用哨兵简化实现难度
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理
插入操作
if (head == null) {
head = new_node;
}else{
new_node->next = p->next;
p->next = new_node;
}
删除操作
iif (head == null) {
head = new_node;
}else{
p->next = p->next->next;
}
哨兵也是解决“边界问题”的，不直接参与业务逻辑
带头链表:有哨兵结点的链表
不带头链表:有哨兵结点的链表
技巧四：重点留意边界条件处理
经常用来检查链表代码是否正确的边界条件：
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
技巧五：举例画图，辅助思考
image.png
技巧六：多写多练，没有捷径
练习：
//Leetcode 206 https://leetcode.com/problems/reverse-linked-list/
type ListNode struct {
Val int
Next *ListNode
}
//翻转链表
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
var prev *ListNode
next := head.Next
for next != nil {
head.Next = prev
prev = head
head = next
next = next.Next
}
head.Next = prev
return head
}
引用：
https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98
