1. 芝麻开门首页
  2. 知识分享

线性表链式存储实现介绍：链表分类及首结构操作问题

admin • • 知识分享• 阅读 76

[[id[id_[id_[id_1297[id_493927199]7591]655[id_[id_[id_495957126]58058169]5426[id_421845368]6]5673]13209284][id_49719[id_152[id_19048[id_695580725]64]85481]988]30[id_1324685047]4311]d_7[id_324416065]9471603]

[id_824955103]

链表由若干个结构单元构成，这些单元在内存中并非必须连续排列；每个单元内含有一个数据项以及一个指向后续单元的链接指针。

依据指针的指向及数量，链表一般可划分为单链表、双向链表以及循环链表三种类型。

实际使用中，双向链表更为常用。

若对首个结构体实施直接操作，编程过程中可能会遭遇若干棘手难题，诸如：

此类任务可能相当复杂，或者需要在程序中特别处理，这对编程构成了挑战。实际上，只需在首部结构之前添加一个头文件，问题便能迎刃而解。

在多数情况下，我们习惯将 Header 设定在位置 0，尽管我个人对此并不赞同。

单链表

[id_1044590037]

1type Node struct [id_2060582320]
2    Data interface{}
3    Next *Node
4}

显而易见，链表的访问机制与顺序表存在显著差异，这就导致了代码在结构上发生了较大变动。

初始化

1func New() *Node {
2    return &Node{}
3}

取值

 1func (n *Node) Get(i int) (interface{}, error) {
 2    if i < 0 {
 3        return nil, errors.New("index out of range")
 4    }
 5    for j := 0; j < i; j++ {
 6        n = n.Next
 7        if n == nil {
 8            return nil, errors.New("index out of range")
 9        }
10    }
11    return n.Data, nil
12}

插入

 1func (n *Node) Insert(i int, data interface{}) error {
 2    if i < 0 {
 3        return errors.New("index out of range")
 4    }
 5    for j := 0; j < i; j++ {
 6        n = n.Next
 7        if n == nil {
 8            return errors.New("index out of range")
 9        }
10    }
11    n.Next = &Node{Data: data, Next: n.Next}
12    return nil
13}

删除

 1func (n *Node) Delete(i int) error {
 2    if i < 0 {
 3        return errors.New("index out of range")
 4    }
 5    for j := 0; j < i; j++ {
 6        n = n.Next
 7        if n == nil {
 8            return errors.New("index out of range")
 9        }
10    }
11    n.Next = n.Next.Next
12    return nil
13}

创建链表

创建链表根据节点插入位置的不同，可以分为头插法和尾插法。

头插法：

1func CreateHead(data []interface{}) *Node {
2    var head *Node = nil
3    for _, v := range data {
4        head := &Node{Data: v, Next: head}
5    }
6    return head
7}

尾插法：

 1func CreateTail(data []interface{}) *Node {
 2    var head *Node = nil
 3    var tail *Node = nil
 4    for _, v := range data {
 5        if head == nil {
 6            head = &Node{Data: v, Next: nil}
 7            tail = head
 8        } else {
 9            tail.Next = &Node{Data: v, Next: nil}
10            tail = tail.Next
11        }
12    }
13    return head
14}

双向链表

双向链表的节点结构可以表示为：

1type Node struct {
2    Data interface{}
3    Prev *Node
4    Next *Node
5}

即每个节点多维护一个指向前一个节点的指针。

每次插入或删除节点时，需要同时修改前后节点的指针。

循环链表

循环链表是一种特殊的链表结构，其特点是链表的第一个节点与最后一个节点相互连接，即链表的起始节点的前一个节点指向链表的结束节点，而链表的结束节点的下一个节点又指向链表的起始节点。

与单链表相比，最大的区别在于遍历的边界条件不同。

在循环链表中，从链表的起始节点开始进行遍历，直至达到链表的末尾节点。此时，该末尾节点的直接后继节点恰好是链表的起始节点。基于此，遍历操作需要满足的边界条件是：

1for n.Next != head {
2    // ...
3}

一些练习LeetCode 707 设计链表

LeetCode 707 设计链表

一道链表设计题，基本涵盖了链表的常用操作。

这道题目不可轻视，一旦认真完成这一链表编程任务，你便会发现，在链表操作中，存在诸多不易把握的边界情况。

  1type MyLinkedList struct {
  2    Val int
  3    Next *MyLinkedList
[id_139438102]}
  5
  6
  7func Constructor() MyLinkedList {
  8    // return a dummy node
  9    return MyLinkedList{
 10        Val: -1,
 11        Next: nil,
 12    }
 13}
 14
 15
 16func (this *MyLinkedList) Get(index int) int {
 17    cur := this.Next
 18    for i := 0; cur != nil; i++ {
 19        if i == index {
 20            return cur.Val
 21        } else {
 22            cur = cur.Next
 23        }
 24    }
 25    return -1
 26}
 27
 28
 29func (this *MyLinkedList) AddAtHead(val int)  {
 30    new := &MyLinkedList{
 31        Val: val,
 32        Next: this.Next,
 33    }
 34    this.Next = new
 35    return
 36}
 37
 38
 39func (this *MyLinkedList) AddAtTail(val int)  {
 40    cur := this
 41    for cur.Next != nil {
 42        cur = cur.Next
 43    }

线性表链式存储实现_单链表节点结构初始化_链表基础知识总结

 44    new := &MyLinkedList{
 45        Val: val,
 46        Next: nil,
 47    }
 48    cur.Next = new
 49}
 50
 51
 52func (this *MyLinkedList) AddAtIndex(index int, val int)  {
 53    if index < 0 {
 54        this.AddAtHead(val)
 55        return
 56    }
 57    if index == 0 {
 58        this.AddAtHead(val)
 59        return
 60    }
 61    cur := this
 62    for i := 0; i < index; i++ {
 63        if cur.Next != nil {
 64            cur = cur.Next
 65        } else {
 66            if i == index {
 67                this.AddAtTail(val)
 68                return
 69            } else {
 70                return
 71            }
 72        }
 73    }
 74    new := &MyLinkedList{
 75        Val: val,
 76        Next: cur.Next,
 77    }
 78    cur.Next = new
 79}
 80
 81
 82func (this *MyLinkedList) DeleteAtIndex(index int)  {
 83    cur := this
 84    for i := 0; i < index; i++ {
 85        if cur.Next == nil {
 86            return
 87        }
 88        cur = cur.Next
 89    }
 90    if cur.Next != nil {
 91        cur.Next = cur.Next.Next
 92    }
 93    return
 94}
 95
 96
 97/**
 98您的MyLinkedList对象将被创建并按照以下方式调用：
 99 * obj := Constructor();
100 * param_1 := obj.Get(index);
101 * obj.AddAtHead(val);
102 * obj.AddAtTail(val);
103 * obj.AddAtIndex(index,val);
104 * obj.DeleteAtIndex(index);
105 */

此类单链表结构相对简单，将其转变为双向链表的任务亦非艰巨，特此留作读者们的思考练习。

LeetCode 21 合并两个有序链表

LeetCode 21 合并两个有序链表

这是一道基础题目，也是教材上的一道例题。

 1func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
 2	dummy := &ListNode{}
 3	cur := dummy
 4    l1 := list1
 5    l2 := list2
 6	for l1 != nil && l2 != nil {
 7		若list1的规模较小，则将list1的节点进行接入；若list1规模较大，则采取相反的操作。
 8		if l1.Val < l2.Val {
 9			cur.Next = l1
10			l1 = l1.Next
11		} else {
12			cur.Next = l2
13			l2 = l2.Next
14		}
15		// cur 后移
16		cur = cur.Next
17	}
18	若list1与list2中尚存未处理的节点，则将这些节点依次附加至尾部。
19	if l1 != nil {
20		cur.Next = l1
21	}
22	if l2 != nil {
23		cur.Next = l2
24	}
25
26	return dummy.Next
27}

LeetCode 203 移除链表元素

LeetCode 203 移除链表元素

同样是基础题目，遍历一遍遇到就删就可以了。

 1func removeElements(head *ListNode, val int) *ListNode {
 2    dummy := &ListNode{
 3        Val: -1,
 4        Next: head,
 5    }
 6    cur := dummy
 7    for cur.Next != nil {
 8        if cur.Next.Val == val {
 9            cur.Next = cur.Next.Next
10        } else {
11            cur = cur.Next
12        }
13    }
14    return dummy.Next
15}

LeetCode 19 删除链表的倒数第 N 个结点

LeetCode 19 删除链表的倒数第 N 个结点

若事先掌握了链表的长度，解决此题将变得极其容易，其难度几乎等同于小学的数学问题。然而，在大多数情况下，我们仅能获取链表的头指针，却无法得知链表的长度。

这个问题同样涉及双指针技术。我们首先让第一个指针从链表的首部出发，向前移动 n 个位置；与此同时，第二个指针保持静止。从第 n+1 步起，第二个指针也开始从链表的首部向前移动。由于两个指针始终保持 n 个位置的差距，因此当第一个指针抵达链表的末端时，第二个指针恰好位于倒数第 n 个节点上。

 1func removeNthFromEnd(head *ListNode, n int) *ListNode {
 2    dummy := &ListNode{
 3        Val: -1,
 4        Next: head,
 5    }
 6    fast := dummy
 7    slow := dummy
 8    for i := 0; i < n; i++ {
 9        fast = fast.Next
10    }
11
12    for fast.Next != nil {
13        slow = slow.Next
14        fast = fast.Next
15    }
16    slow.Next = slow.Next.Next
17    return dummy.Next
18}

LeetCode 83 删除排序链表中的重复元素

LeetCode 83 删除排序链表中的重复元素

题目并不复杂。解决此题的最基本方法是对链表进行遍历，一旦发现当前节点的数值与紧随其后的节点数值相同，便将其后一个节点移除。

鉴于本题目要求至少保留一个关键点，且不会发生首节点被删除的情形，因此无需引入虚拟的首节点。

 1func deleteDuplicates(head *ListNode) *ListNode {
 2    cur := head
 3    for cur != nil && cur.Next != nil {
 4        if cur.Val == cur.Next.Val {
 5            cur.Next = cur.Next.Next
 6        } else {
 7            cur = cur.Next
 8        }
 9    }
10    return head
11}

本文来自作者[admin]投稿，不代表芝麻开门立场，如若转载，请注明出处：https://aizmkm.com/zshi/202507-2380.html

赞 (76)
admin的头像admin签约作者
76 3

文章推荐

发表回复

作者才能评论

评论列表（3条）

  • admin的头像
    admin 2025年07月26日

    我是芝麻开门的签约作者“admin”

  • admin
    admin 2025年07月26日

    本文概览：上一节我们介绍了线性表的顺序存储实现，这一节阐述线性表的链式存储实现。...

  • admin
    用户072612 2025年07月26日

    文章不错《线性表链式存储实现介绍：链表分类及首结构操作问题》内容很有帮助

联系我们

邮件：芝麻开门@gmail.com

工作时间：周一至周五，9:30-17:30，节假日休息

关注微信