作者简介:

       姜海强:闷骚码农,互联网行业摸爬滚打数余载,先后担任中国体育直播TV主程、网信集团先锋支付架构师、奇虎360服务器端资深开发。热爱技术,喜欢分享,热衷领域:PHP/Golang语言、面向对象设计模式、Redis、Yaf、Yii2、微服务等。

视频课程

yaf+yar微服务-腾讯课堂
yaf+yar微服务-51CTO学院
CSDN学院

Github

个人主页
swoole-boot
roach
roach-orm

QQ群:

姜海强的QQ群

公众号:

360tryst公众号

单链表

链表是一种链式存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,单链表的结构如下图

链表

代码实现

  1. package line
  2. type LinkList struct {
  3. first *element
  4. last *element
  5. length int
  6. }
  7. type element struct {
  8. item interface{}
  9. next *element
  10. }
  11. func NewLinkList() *LinkList {
  12. return &LinkList{}
  13. }
  14. func (this *LinkList) Get(index int) (interface{}, bool) {
  15. if this.length == 0 || index >= this.length || index < 0 {
  16. return nil, false
  17. }
  18. ele := this.first
  19. for i := 0; i < index; i++ {
  20. ele = ele.next
  21. if ele == nil {
  22. return nil, false
  23. }
  24. }
  25. return ele.item, true
  26. }
  27. func (this *LinkList) Set(index int, item interface{}) bool {
  28. if index > this.length || index < 0 {
  29. return false
  30. }
  31. current := &element{
  32. item: item,
  33. }
  34. if index == 0 {
  35. current.next = this.first.next
  36. this.first = current
  37. if this.length == 0 {
  38. this.last = this.first
  39. this.length++
  40. }
  41. return true
  42. }
  43. ele := this.first
  44. for i:=0; i< index -1; i++ {
  45. ele = ele.next
  46. }
  47. indexEle := ele.next
  48. current.next = indexEle.next
  49. ele.next = current
  50. if index == this.length {
  51. this.length++
  52. this.last = current
  53. }
  54. return true
  55. }
  56. func (this *LinkList) Insert(index int, item interface{}) bool {
  57. if index > this.length || index < 0 {
  58. return false
  59. }
  60. defer func() {
  61. this.length++
  62. }()
  63. current := &element{
  64. item: item,
  65. }
  66. //头位置,需要更换头指针
  67. if index == 0 {
  68. current.next = this.first
  69. this.first = current
  70. if this.length == 0 {
  71. this.last = this.first
  72. }
  73. return true
  74. }
  75. //尾位置,需要更换尾指针
  76. if index == this.length {
  77. this.last.next = current
  78. this.last = current
  79. return true
  80. }
  81. ele := this.first
  82. for i := 0; i < index - 1; i++ {
  83. ele = ele.next
  84. }
  85. //获取索引位置元素
  86. indexEle := ele.next
  87. //将索引位置元素放到插入元素后面
  88. current.next = indexEle
  89. //上一元素的下一个元素为当前元素
  90. ele.next = current
  91. return true
  92. }
  93. func (this *LinkList) Prepend(item interface{}) {
  94. this.Insert(0, item)
  95. }
  96. func (this *LinkList) Append(item interface{}) {
  97. this.Insert(this.length, item)
  98. }
  99. func (this *LinkList) Length() int {
  100. return this.length
  101. }
  102. func (this *LinkList) Remove(index int) bool {
  103. if this.length == 0 || index > this.length - 1 || index < 0 {
  104. return false
  105. }
  106. defer func() {
  107. this.length--
  108. }()
  109. if index == 0 {
  110. this.first = this.first.next
  111. return true
  112. }
  113. ele := this.first
  114. for i :=0; i < index - 1; i++ {
  115. ele = ele.next
  116. }
  117. indexEle := ele.next
  118. ele.next = indexEle.next
  119. indexEle = nil
  120. if this.length == index {
  121. this.last = ele
  122. }
  123. return true
  124. }
  125. func (this *LinkList) Range(f func(index int, item interface{})) {
  126. ele := this.first
  127. for i := 0; i < this.length; i++ {
  128. f(i, ele.item)
  129. ele = ele.next
  130. }
  131. }

使用

  1. //初始化链表
  2. container := line.NewLinkList()
  3. //向索引位置1插入数据10,插入失败,因为头结点还没有数据
  4. result := container.Insert(1, 10)
  5. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  6. //向头结点插入数据0
  7. //此时数据为:0
  8. result = container.Insert(0, 0)
  9. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  10. //向索引为8插入数据80,插入失败
  11. //此时数据为:0
  12. result = container.Insert(8, 80)
  13. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  14. //此时数据为:10 0
  15. result = container.Insert(0, 10)
  16. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  17. container.Range(func(index int, item interface{}) {
  18. fmt.Printf("index:%d; item:%v\n", index, item)
  19. })
  20. //此时数据为:10 20 0
  21. result = container.Insert(1, 20)
  22. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  23. //此时数据为:10 20 0 30
  24. container.Append(30)
  25. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  26. //此时数据为:50 10 20 0 30
  27. container.Prepend(50)
  28. fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
  29. container.Range(func(index int, item interface{}) {
  30. fmt.Printf("index:%d; item:%v\n", index, item)
  31. })
  32. container.Append(60)
  33. container.Append(70)
  34. container.Append(80)
  35. container.Append(90)
  36. container.Append(100)
  37. container.Append(110)
  38. //单链表无长度限制
  39. fmt.Printf("container.Length:%d\n", container.Length())
  40. for i :=0; i < container.Length(); i++ {
  41. value, _ := container.Get(i)
  42. fmt.Printf("i:%d; item: %v\n", i, value)
  43. }
  44. //删除
  45. container.Remove(0)
  46. value, _ := container.Get(0)
  47. fmt.Printf("i:%d; item: %v\n", 0, value)
  48. container.Set(9, 999)
  49. value, _ = container.Get(9)
  50. fmt.Printf("i:%d; item: %v\n", 9, value)

以上例程运行结果

  1. Insert: false, container.Length:0
  2. Insert: true, container.Length:1
  3. Insert: false, container.Length:1
  4. Insert: true, container.Length:2
  5. index:0; item:10
  6. index:1; item:0
  7. Insert: true, container.Length:3
  8. Insert: true, container.Length:4
  9. Insert: true, container.Length:5
  10. index:0; item:50
  11. index:1; item:10
  12. index:2; item:20
  13. index:3; item:0
  14. index:4; item:30
  15. container.Length:11
  16. i:0; item: 50
  17. i:1; item: 10
  18. i:2; item: 20
  19. i:3; item: 0
  20. i:4; item: 30
  21. i:5; item: 60
  22. i:6; item: 70
  23. i:7; item: 80
  24. i:8; item: 90
  25. i:9; item: 100
  26. i:10; item: 110
  27. i:0; item: 10
  28. i:9; item: 999

时间复杂度

操作 最好时间复杂度 最差时间复杂度
查询 O(n) O(n)
删除 O(1) O(n)
插入 O(1) O(n)
修改 O(1) O(n)

QQ群:

姜海强的QQ群

公众号:

360tryst公众号