数据结构之链表 -

说实话，链表在我工作中用的确实不多，上一次接触链表，还是在上一次。最近重温算法，决定总结下链表相关知识，算是个人笔记分享。顺便分享一段老师的话：不是因为知识没有用，而是因为你没有使用知识，所以是你没用。(扎心了)

引言

链表，是一种基本的数据结构，它的基本概念和原理是独立于编程语言，也就是说，无论哪种语言你都可以实现它。具有灵活性、可伸缩性和内存效率，链表可能在缓存系统、高性能队列中得到了广泛的使用。以下的几个特征从网上查询外加上了个人的解释：

动态内存分配：链表允许在运行时动态分配内存空间，相对于静态数组，链表相对灵活，相对于go语言的切片，它有着不浪费内存的分配。如切片扩容原理，不会恰到好处的扩到合适的位置，导致内存浪费。但链表不会，每次新增一个节点，都只分配了实际需要的内存。
可变长度：链表的长度可以随时增加或减少。比如当需要再列表中间插入或删除元素的时候，链表的性能比数组更好，所以如果涉及到更改列表，查询很少，则建议使用链表。
低内存开销：链表的节点可以分散的存储在内存中，使用节点中的指针进行查找。但数组需要连续的内存块。这意味着链表可以有效的利用可用的内存碎片，减少内存浪费。但是，恰恰是由于节点在内存中分散，可能导致缓存不友好，从而影响性能。
时间复杂度：特定的链表操作，比如在头部插入或者删除某个节点的时候，它的时间复杂度为O(1)，但数组是O(n),在某些特定的操作下，链表的执行速度较快。
算法和面试：链表在面试中经常被问到，理解链表的原理以及操作对于编程面试非常重要。（算是学习链表的目的和意义吧）

来吧，链表

链表:linked list,是有一组不必相连的内存结构(节点)，按特定的顺序链接在一起的数据类型。也就是各个节点之前可以在内存中可以不连续，靠内部的数据结构进行操作。它分为单向链表、双向链表、循环链表。我们一般使用Node作为链表的基本构建块。链表的核心操作就是：插入、删除、查找。

单向链表

单向链表，它的Node包含了数据元素和指向下一个节点(后继Node)的引用，通过指向来形成链式结构，链尾没有后继。

danxainglianbiao

代码的表达为：

type Node struct {
    value int
    next  *Node
}

func CreateNode() *Node {
    n3 := &Node{
        value: 3,
        next:  nil,
    }
    n2 := &Node{
        value: 2,
        next:  n3,
    }
    n1 := &Node{
        value: 1,
        next:  n2,
    }
    return n1
}

单向链表的插入

如上：新增一个值为4，要插入到Node为3的后面，那么：

danxainglianbiaadd

插入的代码：

func InsertAfterValue(head *Node, targetValue, newValue int) *Node {
    current := head
    for current != nil {
        if current.value == targetValue {
            newNode := &Node{
                value: newValue,
                next:  current.next,
            }
            current.next = newNode
            break
        }
        current = current.next
    }
    return head
}

单向链表的删除

删除的原理，其实就是找到该节点后，把该节点的上一个节点指向下一个节点即可。如上，需要删除2这个节点:

danxainglianbiadel

代码：

func DelNode(head *Node, delValue int) *Node {
    // 直接判断头节点为删除点，直接返回头结点的下一个节点
    /*if head.value == delValue {
        newHead := head.next
        head.next = nil // 断开头节点的连接以防止内存泄漏
        return newHead
    }*/

    // 创建一个虚拟头节点，简化删除头节点的情况
    dummy := &Node{next: head}
    prev := dummy
    current := head

    for current != nil {
        if current.value == delValue {
            // 找到目标节点，将前一个节点的 next 指向当前节点的下一个节点
            prev.next = current.next
            current = nil
            break // 找到并删除节点后，退出循环
        }
        prev = current
        current = current.next
    }
    return dummy.next // 返回头节点，可能已经发生了变化
}

双向链表

双向链表：较单向而言，他的Node结构中包含了指向上一个节点的引用(前驱Node)，链头没有前驱，链尾没有后继。

shuangxiangliebiao

代码表达为：

type DoublyNode struct {
    value int
    prev  *DoublyNode
    next  *DoublyNode
}

双向链表的插入

如已经有1,2,3个节点，需要在2后面插入4节点：

shuangxiangliebiaoadd

代码：

func InsertDoublyNode(head *DoublyNode, targetValue, newValue int) *DoublyNode {
    current := head
    for current != nil {
        if current.value == targetValue {
            newNode := &DoublyNode{
                value: newValue,
                prev:  current,
                next:  current.next,
            }
            current.next = newNode
            break
        }
        current = current.next
    }
    return head
}

双向链表的删除

同单向列表的删除，不解释了，太晚了，睡觉。明天开干算法相关。

链表算法相关

链表典型算法剖析

数据结构之链表

引言