golang算法练习：单链表/双链表/环形链表

以你之姓@ 2021-12-03 15:05 517阅读 0赞

需求

链表，常见且非常灵活的数据模型，可定制性强，可根据需求调整满足不同的使用需求，如FIFO\LIFO，快速查找等，这里分别列举基础的单向链表和双向链表增删改查操作
备注：需求和运行输出结果均已在代码中注释

单向链表

代码

  1. package main
  3. import (
  4.     "errors"
  5.     "fmt"
  6. )
  8. type Node struct { 
  9.     id   int
  10.     name string
  11.     next *Node
  12. }
  14. type SingleLink struct { 
  15.     head *Node
  16. }
  18. func (singleLink *SingleLink) orderInsert(node *Node) { 
  19.     // 按Node.id从小到大的顺序，插入链表中
  20.     curNode := singleLink.head
  21.     if curNode.id == 0 { 
  22.         // 第一次插入元素的空链表
  23.         singleLink.head = node
  24.     } else { 
  25.         // 如果node.id比队首id小，则队首让位后移，要保证队首最小。因为取值比较的时候， 是取curNode.next节点与node进行比较，如果满足大小顺序，
  26.         // 则将node插入curNode和curNode.next之间
  27.         if curNode.id > node.id { 
  28.             node.next = curNode
  29.             singleLink.head = node
  30.         } else { 
  31.             // 如果node.id不比队首id小，则往后取一位，用后一位与node比较，匹配则插入当前位与后一位中间
  32.             for { 
  33.                 if curNode.next == nil { 
  34.                     // 循环到最后一位都没有插入成功，说明node.id比现有链表中的所有node的id都大，则node成为新的队尾
  35.                     curNode.next = node
  36.                     break
  37.                 }
  38.                 if curNode.next.id > node.id { 
  39.                     node.next = curNode.next
  40.                     curNode.next = node
  41.                     break
  42.                 }
  43.                 curNode = curNode.next
  44.             }
  45.         }
  46.     }
  47. }
  49. func (singleLink *SingleLink) pop(id int) (node *Node, err error) { 
  50.     // 弹出链表中指定id的node
  51.     curNode := singleLink.head
  52.     if curNode.id == id { 
  53.         // 要取的是队首
  54.         singleLink.head = singleLink.head.next
  55.         return curNode, nil
  56.     }
  57.     flag := false // 是否查找到的标志
  58.     for { 
  59.         if curNode.next == nil { 
  60.             break
  61.         }
  62.         if curNode.next.id == id { 
  63.             flag = true
  64.             selectNode := curNode.next
  65.             curNode.next = curNode.next.next
  66.             return selectNode, nil
  67.         }
  68.         curNode = curNode.next
  69.     }
  70.     if !flag { 
  71.         // 如果循环结束还没有查找到，输出信息
  72.         return nil, errors.New("node not found")
  73.     }
  74.     return
  75. }
  77. func (singleLink *SingleLink) getLength() (number int) { 
  78.     curNode := singleLink.head
  79.     if singleLink.head.id == 0 || singleLink.head == nil { 
  80.         // 空链表
  81.         return
  82.     } else { 
  83.         for { 
  84.             number += 1
  85.             curNode = curNode.next
  86.             if curNode == nil { 
  87.                 break
  88.             }
  89.         }
  90.     }
  91.     fmt.Println("current link length:", number)
  92.     return number
  93. }
  95. func (singleLink *SingleLink) list() { 
  96.     if singleLink.head == nil || singleLink.head.id == 0 { 
  97.         fmt.Println("link is empty")
  98.     } else { 
  99.         curNode := singleLink.head
  100.         for { 
  101.             if curNode == nil { 
  102.                 break
  103.             }
  104.             fmt.Print(*curNode, "==>")
  105.             curNode = curNode.next
  106.         }
  107.     }
  108.     fmt.Println()
  110. }
  112. func main() { 
  113.     // 约定空链表的header初始id为0，后面加入的实例id必须大于0
  114.     var originalHead = Node{ 
  115.         id: 0,
  116.     }
  117.     var s = SingleLink{ 
  118.         head: &originalHead,
  119.     }
  120.     var node1 = Node{ 
  121.         id:   1,
  122.         name: "001",
  123.     }
  124.     var node2 = Node{ 
  125.         id:   2,
  126.         name: "002",
  127.     }
  128.     var node3 = Node{ 
  129.         id:   3,
  130.         name: "003",
  131.     }
  132.     var node4 = Node{ 
  133.         id:   4,
  134.         name: "004",
  135.     }
  136.     var node5 = Node{ 
  137.         id:   5,
  138.         name: "005",
  139.     }
  141.     s.orderInsert(&node4)
  142.     s.list()
  143.     s.orderInsert(&node2)
  144.     s.list()
  145.     s.orderInsert(&node3)
  146.     s.list()
  147.     s.orderInsert(&node5)
  148.     s.list()
  149.     s.orderInsert(&node1)
  150.     s.list()
  151.     s.getLength()
  152.     popNode, err := s.pop(3)
  153.     if err != nil { 
  154.         fmt.Println(err)
  155.     }
  156.     fmt.Println("pop node successfully:", *popNode)
  157.     s.list()
  159.     /* output: {4 004 <nil>}==> {2 002 0xc00000a0e0}==>{4 004 <nil>}==> {2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 <nil>}==> {2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==> {1 001 0xc00000a0a0}==>{2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==> current link length: 5 pop node successfully: {3 003 0xc00000a0e0} {1 001 0xc00000a0a0}==>{2 002 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==> */
  160. }

问题
单向链表的操作必须从首部开始，那么可不可以灵活一些，比如从尾部开始呢？当然可以，改造成双向链表即可满足

双向链表

代码：
为了以示区别，增删改查全部改为从尾部开始循环

  1. package main
  3. import (
  4.     "errors"
  5.     "fmt"
  6. )
  8. type Node struct { 
  9.     id   int
  10.     name string
  11.     next *Node
  12.     prev *Node
  13. }
  15. type CircleLink struct { 
  16.     head *Node
  17.     tail *Node
  18. }
  20. func (circleLink *CircleLink) orderInsert(node *Node) { 
  21.     // 按Node.id从小到大的顺序，插入链表中
  22.     curNode := circleLink.head
  23.     if curNode.id == 0 { 
  24.         // 第一次插入元素的空链表
  25.         circleLink.head = node
  26.         circleLink.tail = node
  27.     } else { 
  28.         // 如果node.id比队首id小，则队首让位后移，要保证队首最小。因为取值比较的时候， 是取curNode.next节点与node进行比较，如果满足大小顺序，
  29.         // 则将node插入curNode和curNode.next之间
  30.         if curNode.id > node.id { 
  31.             node.next = curNode
  32.             curNode.prev = node
  33.             circleLink.head = node
  34.         } else { 
  35.             // 如果node.id不比队首id小，则往后取一位，用后一位与node比较，匹配则插入当前位与后一位中间
  36.             for { 
  37.                 if curNode.next == nil { 
  38.                     // 循环到最后一位都没有插入成功，说明node.id比现有链表中的所有node的id都大，则node成为新的队尾
  39.                     curNode.next = node
  40.                     node.prev = curNode
  41.                     circleLink.tail = node
  42.                     break
  43.                 }
  44.                 if curNode.next.id > node.id { 
  45.                     node.next = curNode.next
  46.                     node.prev = curNode
  47.                     curNode.next.prev = node
  48.                     curNode.next = node
  49.                     break
  50.                 }
  51.                 curNode = curNode.next
  52.             }
  53.         }
  54.     }
  55. }
  57. func (circleLink *CircleLink) pop(id int) (node *Node, err error) { 
  58.     // 弹出链表中指定id的node.这次从链表尾部往首部循环
  59.     curNode := circleLink.tail
  60.     if curNode.id == id { 
  61.         // 要取的是队尾
  62.         circleLink.tail = circleLink.tail.prev
  63.         return curNode, nil
  64.     }
  65.     flag := false // 是否查找到的标志
  66.     for { 
  67.         if curNode.prev == nil { 
  68.             // 已经从队尾达到队首,全部都没命中
  69.             break
  70.         }
  71.         if curNode.id == id { 
  72.             flag = true
  73.             selectNode := curNode
  74.             if curNode == circleLink.head { 
  75.                 // 如果命中的节点正好是队首
  76.                 if circleLink.head.next != nil { 
  77.                     // 如果队首后面还有节点，则第二个节点置为新的首节点，且第二个节点的prev指向置为nil，这样原head没有被引用，内存会释放出来
  78.                     circleLink.head.next.prev = nil
  79.                     circleLink.head = circleLink.head.next
  80.                 } else { 
  81.                     // 如果队首之后没有节点了，那么直接首位都置空
  82.                     circleLink.head = nil
  83.                     circleLink.tail = nil
  84.                 }
  85.             } else { 
  86.                 // 命中的节点在队中间,则取出命中的节点，并维护好其前后指向关系
  87.                 curNode.prev.next = curNode.next
  88.                 curNode.next.prev = curNode.prev
  89.             }
  90.             return selectNode, nil
  91.         }
  92.         curNode = curNode.prev
  93.     }
  94.     if !flag { 
  95.         // 如果循环结束还没有查找到，输出信息
  96.         return nil, errors.New("node not found")
  97.     }
  98.     return
  99. }
  101. func (circleLink *CircleLink) getLength() (number int) { 
  102.     curNode := circleLink.tail
  103.     if circleLink.tail.id == 0 || circleLink.tail == nil { 
  104.         // 空链表
  105.         return
  106.     } else { 
  107.         for { 
  108.             number += 1
  109.             curNode = curNode.prev
  110.             if curNode == nil { 
  111.                 break
  112.             }
  113.         }
  114.     }
  115.     fmt.Println("current link length:", number)
  116.     return number
  117. }
  119. func (circleLink *CircleLink) list() { 
  120.     if circleLink.tail == nil || circleLink.tail.id == 0 { 
  121.         fmt.Println("link is empty")
  122.     } else { 
  123.         curNode := circleLink.tail
  124.         var nodes []*Node
  125.         for { 
  126.             if curNode == nil { 
  127.                 break
  128.             }
  129.             //fmt.Print("<==", *curNode)
  130.             // 从尾部到首部的循环，为了展示链接效果，将节点先加入一个slice中，稍后从slice的后面开始循环展示数据.此时slice是从尾部到首部排序的
  131.             nodes = append(nodes, curNode)
  132.             curNode = curNode.prev
  133.         }
  134.         for i := 0; i < len(nodes); i++ { 
  135.             index := len(nodes) - i - 1 // 颠倒一下顺序，现在slice中的顺序和链表顺序恰好是相反的，为了打印的效果，让前面的节点先输出
  136.             fmt.Print("<==>", nodes[index])
  137.         }
  138.     }
  140.     fmt.Println()
  142. }
  144. func main() { 
  145.     // 约定空链表的header初始id为0，后面加入的实例id必须大于0
  146.     var originalHead = Node{ 
  147.         id: 0,
  148.     }
  149.     var s = CircleLink{ 
  150.         head: &originalHead,
  151.     }
  152.     var node1 = Node{ 
  153.         id:   1,
  154.         name: "001",
  155.     }
  156.     var node2 = Node{ 
  157.         id:   2,
  158.         name: "002",
  159.     }
  160.     var node3 = Node{ 
  161.         id:   3,
  162.         name: "003",
  163.     }
  164.     var node4 = Node{ 
  165.         id:   4,
  166.         name: "004",
  167.     }
  168.     var node5 = Node{ 
  169.         id:   5,
  170.         name: "005",
  171.     }
  173.     s.orderInsert(&node4)
  174.     s.list()
  175.     s.orderInsert(&node2)
  176.     s.list()
  177.     s.orderInsert(&node3)
  178.     s.list()
  179.     s.orderInsert(&node5)
  180.     s.list()
  181.     s.orderInsert(&node1)
  182.     s.list()
  183.     s.getLength()
  184.     popNode, err := s.pop(3)
  185.     if err != nil { 
  186.         fmt.Println(err)
  187.     }
  188.     fmt.Println("pop node successfully:", *popNode)
  189.     s.list()
  191.     /* output: <==&{4 004 <nil> <nil>} <==&{2 002 0xc0000761e0 <nil>}<==&{4 004 <nil> 0xc000076180} <==&{2 002 0xc0000761b0 <nil>}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 <nil> 0xc0000761b0} <==&{2 002 0xc0000761b0 <nil>}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 0xc000076210 0xc0000761b0}<==&{5 005 <nil> 0xc0000761e0} <==&{1 001 0xc000076180 <nil>}<==&{2 002 0xc0000761b0 0xc000076150}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 0xc000076210 0xc0000761b0}<==&{5 005 <nil> 0xc0000761e0} current link length: 5 pop node successfully: {3 003 0xc0000761e0 0xc000076180} <==&{1 001 0xc000076180 <nil>}<==&{2 002 0xc0000761e0 0xc000076150}<==&{4 004 0xc000076210 0xc000076180}<==&{5 005 <nil> 0xc0000761e0} */
  192. }

问题
从尾部开始查询的操作复杂度依旧与首部开始一样，为O(n)，有没有办法降低复杂度？当然可以，按照自定义链节点串联规则，完全可以使用二分等其他查找的方法降低复杂度，这个后面再补充

环形链表

直接以约瑟夫问题，又称丢手帕游戏举例，此场景非常适用于使用环形链表模型，游戏规则见代码顶部注释
代码：

  1. package main
  3. import (
  4.     "fmt"
  5.     "math/rand"
  6. )
  8. /* 约瑟夫问题，又叫丢手帕游戏，若干人围成一圈，从头开始，每次递进若干位随机数，然后出列一人，接着再从出列者的下一位开始继续循环， 直到圈内只剩最后一人,游戏结束 */
  10. type Child struct { 
  11.     Id   int
  12.     next *Child
  13. }
  15. type Ring struct { 
  16.     Head *Child
  17.     Tail *Child
  18. }
  20. func (ring *Ring) list() { 
  21.     curChild := ring.Head
  22.     for { 
  23.         fmt.Printf("child %d ==>\t", curChild.Id)
  24.         if curChild.next == ring.Head { 
  25.             break
  26.         }
  27.         curChild = curChild.next
  28.     }
  29.     fmt.Println()
  30. }
  32. func (ring *Ring) play() { 
  33.     // 开始转圈,第一次是从头开始
  34.     startIndex := 1
  35.     n := 0
  36.     startChild := ring.Head
  37.     for { 
  38.         if startChild.next == startChild { 
  39.             fmt.Printf("游戏结束，圈圈中的最后一位child是%d号\n", startChild.Id)
  40.             break
  41.         }
  42.         n += 1
  43.         randInt := rand.Intn(10)
  44.         curChild := startChild
  45.         for i := 0; i < randInt-1; i++ { 
  46.             // 在出列child的前一位停下，因为是链表关系，所以需要维护好出列child的前一位的指向关系
  47.             curChild = curChild.next
  48.         }
  49.         chooseChild := curChild.next
  50.         if chooseChild == ring.Head { 
  51.             ring.Head = chooseChild.next
  52.         }
  53.         curChild.next = chooseChild.next // chooseChild的指针取消，chooseChild会被回收，出列
  54.         fmt.Printf("第%d轮,从第%d号开始,前进%d位,出列的是%d号child,game continue!\n", n, startIndex, randInt, chooseChild.Id)
  55.         startIndex = (randInt + startIndex + 1) % 20
  56.         startChild = chooseChild.next // 下一轮，从chooseChild.next节点开始
  57.     }
  59. }
  61. func ringInit(number int) (ring Ring) { 
  62.     // 构建一个指定成员数量的环形链表
  63.     for i := 1; i <= number; i++ { 
  64.         var child = Child{ 
  65.             Id: i,
  66.         }
  67.         fmt.Println(child)
  68.         if i == 1 { 
  69.             // 插入第一个节点
  70.             ring.Head = &child
  71.             ring.Tail = &child
  72.             ring.Tail.next = ring.Head // 尾节点下一个指针指向首节点
  73.         } else { 
  74.             // 后面的节点，陆续成为新的尾结点
  75.             child.next = ring.Head
  76.             ring.Tail.next = &child
  77.             ring.Tail = &child
  78.         }
  79.     }
  80.     return
  81. }
  83. func main() { 
  84.     ring := ringInit(20)
  85.     fmt.Println(*ring.Head, *ring.Tail)
  86.     ring.list()
  87.     ring.play()
  88. }
  89. /* output: 第1轮,从第1号开始,前进1位,出列的是2号child,game continue! 第2轮,从第3号开始,前进7位,出列的是10号child,game continue! 第3轮,从第11号开始,前进7位,出列的是18号child,game continue! 第4轮,从第19号开始,前进9位,出列的是9号child,game continue! 第5轮,从第9号开始,前进1位,出列的是12号child,game continue! 第6轮,从第11号开始,前进8位,出列的是3号child,game continue! 第7轮,从第0号开始,前进5位,出列的是11号child,game continue! 第8轮,从第6号开始,前进0位,出列的是14号child,game continue! 第9轮,从第7号开始,前进6位,出列的是4号child,game continue! 第10轮,从第14号开始,前进0位,出列的是6号child,game continue! 第11轮,从第15号开始,前进4位,出列的是16号child,game continue! 第12轮,从第0号开始,前进1位,出列的是19号child,game continue! 第13轮,从第2号开始,前进2位,出列的是5号child,game continue! 第14轮,从第5号开始,前进9位,出列的是13号child,game continue! 第15轮,从第15号开始,前进8位,出列的是20号child,game continue! 第16轮,从第4号开始,前进4位,出列的是17号child,game continue! 第17轮,从第9号开始,前进1位,出列的是7号child,game continue! 第18轮,从第11号开始,前进5位,出列的是1号child,game continue! 第19轮,从第17号开始,前进7位,出列的是15号child,game continue! 游戏结束，圈圈中的最后一位child是8号 */

发表评论

表情：
评论列表 （有 0 条评论，517人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构-链表-环形链表

    数据结构-链表-环形链表 环形链表就是将单链表的尾部指向头部，从而形成一个单方向的环形结构，环形链表中每个元素都可以是head，也都可以是尾部，这样就不用担心链表头指针遗

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 40 阅读

    相关 链表----141. 环形链表

    【题目】给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来

    朱雀朱雀/ 0 赞/ 267 阅读

    相关 环形单链表

    【一】环形单链表 > 单项环形链表解决约瑟夫环 > 1.定义节点 > 2.创建环形链表 > 3.遍历环形链表 > 4.环形链表添加节点 【二】环形单链表的图

    怼烎@怼烎@/ 0 赞/ 582 阅读