03.数据结构——链表

数据结构—链表

相关数据结构实现用go语言实现

相关代码做题合集：https://github.com/longpi1/algorithm-pattern

链表（Linked List）是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的指针（在双向链表中还包括指向前一个节点的指针）。下面我将详细介绍链表的特点、优缺点，并提供 Go 语言实现的示例。

---

一、链表的特点

1. 动态性：
   • 链表的大小可以动态增长或缩小，节点可以在运行时动态分配内存，不需要预先定义固定大小。
2. 非连续存储：
   • 链表的节点在内存中不是连续存储的，每个节点通过指针连接到下一个节点。
3. 插入和删除效率高：
   • 在已知某个节点位置的情况下，插入或删除操作的时间复杂度为 O(1)，只需要调整指针即可。
4. 访问效率低：
   • 链表不支持随机访问，要访问第 n 个节点，必须从头节点开始遍历，时间复杂度为 O(n)。
5. 类型多样：
   • 单向链表：每个节点只包含指向下一个节点的指针。
   • 双向链表：每个节点包含指向前一个和后一个节点的指针。
   • 循环链表：链表的尾节点指向头节点，形成一个环。

---

二、链表的优缺点

优点

1. 动态扩展：链表的大小可以根据需要动态增加或减少，适合存储大小不固定的数据。
2. 高效的插入和删除：在已知节点位置的情况下，插入和删除操作非常高效（O(1)）。
3. 内存利用率高：不需要连续的内存空间，适合内存碎片较多的情况。

缺点

1. 访问效率低：不支持随机访问，查找某个节点需要从头遍历，时间复杂度为 O(n)。
2. 额外的内存开销：每个节点都需要额外的空间存储指针。
3. 不适合并行操作：由于链表的非连续性，难以利用现代 CPU 的缓存机制，性能可能不如数组。

---

三、链表的应用场景

1. 动态数据存储：当数据量不确定或需要频繁插入/删除时，链表是一个不错的选择。
2. 实现栈和队列：链表可以轻松实现栈（后进先出）和队列（先进先出）的数据结构。
3. 图的邻接表表示：在图论中，邻接表通常用链表实现。
4. 内存管理：操作系统的内存分配中，空闲内存块通常用链表管理。

四、算法示例

203. 移除链表元素

// 直接使用原来的链表来进行删除操作
func removeElements(head *ListNode, val int) *ListNode {
	// 1.需要首先对头结点进行处理，判断头节点是否相等
	// 这个循环会移除所有值为 val 的前导节点。执行完毕后，head 要么是 nil (如果所有节点都被移除了)，要么指向第一个值不等于 val 的节点。
	for head != nil && head.Val == val {
		head = head.Next
	}
	// 2不能直接操作头节点，头结点遍历会导致值不断变化，最后返回的就是最后一个值，这里需要用cur作为临时指针节点指向头节点；
	cur := head
	for cur != nil && cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return head
}

// 虚拟头节点做法，
func removeElements(head *ListNode, val int) *ListNode {
	dummyHead := &ListNode{}
	dummyHead.Next = head
	cur := dummyHead
	for cur != nil && cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return dummyHead.Next
}

206. 反转链表

// 1.头插法：
/*
dummy 用作新链表的「表头前置节点」
循环里：
断开 head 和 nxt 的连接
把 nxt 插到新链表最前面
最后返回 dummy.Next 即反转后的头节点。
*/
func reverseList(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    // 每次把 head.Next 拿出来，插到 dummy.Next 之前
    for head != nil && head.Next != nil {
       nxt := head.Next
       head.Next = nxt.Next      // 跳过 nxt
       nxt.Next = dummy.Next     // 把 nxt 插到最前面
       dummy.Next = nxt
    }
    return dummy.Next
}

// 2.迭代+双指针
func reverseList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode
    for cur != nil {
       //for cur.Next != nil {
       next := cur.Next
       cur.Next = pre
       pre = cur
       cur = next
    }

    return pre
    // 不应该返回head,最后返回新的头引用pre
    //return head
}

// 3.递归（判断是否有最小子问题）递归最主要找边界条件与非边界条件，最后得到就i是最小子问题的结果
func reverseList(head *ListNode) *ListNode {
    // 1. 递归终止条件也就是边界条件
    if head == nil || head.Next == nil {
       return head
    }
    var p = reverseList(head.Next)
    //反转
    head.Next.Next = head
    head.Next = nil
    return p
}