作者简介:

       姜海强:闷骚码农,互联网行业摸爬滚打数余载,先后担任中国体育直播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 DoubleLinkList struct {
  3. first *doubleLinkElement
  4. length int
  5. }
  6. type doubleLinkElement struct {
  7. item interface{}
  8. prev *doubleLinkElement
  9. next *doubleLinkElement
  10. }
  11. func NewDoubleLinkList() *DoubleLinkList {
  12. return &DoubleLinkList{}
  13. }
  14. func (this *DoubleLinkList) 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 *DoubleLinkList) Insert(index int, item interface{}) bool {
  28. if index > this.length || index < 0 {
  29. return false
  30. }
  31. defer func() {
  32. this.length++
  33. }()
  34. current := &doubleLinkElement{
  35. item: item,
  36. }
  37. //头位置,需要更换头指针
  38. if index == 0 {
  39. if this.first != nil {
  40. current.next = this.first
  41. this.first.prev = current
  42. }
  43. this.first = current
  44. return true
  45. }
  46. ele := this.first
  47. for i := 0; i < index-1; i++ {
  48. ele = ele.next
  49. }
  50. //将索引位置的上一元素变为当前元素的上一元素
  51. current.prev = ele
  52. //将索引位置元素变为当前元素的下一元素
  53. current.next = ele.next
  54. if ele.next != nil && ele.next.next != nil {
  55. //索引位置下一元素的上个元素变为当前元素
  56. ele.next.next.prev = current
  57. }
  58. //索引位置上一元素的下个元素变为当前元素
  59. ele.next = current
  60. return true
  61. }
  62. func (this *DoubleLinkList) Lpush(item interface{}) {
  63. this.Insert(0, item)
  64. }
  65. func (this *DoubleLinkList) Rpush(item interface{}) {
  66. this.Insert(this.length, item)
  67. }
  68. func (this *DoubleLinkList) Set(index int, item interface{}) bool {
  69. if index > this.length || index < 0 {
  70. return false
  71. }
  72. current := &doubleLinkElement{
  73. item: item,
  74. }
  75. if index == 0 {
  76. if this.length == 0 {
  77. this.length++
  78. } else {
  79. current.next = this.first.next
  80. if this.first.next != nil {
  81. this.first.next.prev = current
  82. }
  83. }
  84. this.first = current
  85. return true
  86. }
  87. ele := this.first
  88. for i := 0; i < index-1; i++ {
  89. ele = ele.next
  90. }
  91. current.prev = ele
  92. if ele.next == nil {
  93. this.length++
  94. ele.next = current
  95. return true
  96. }
  97. ele.next = current
  98. current.next = ele.next.next
  99. ele.next.prev = current
  100. return true
  101. }
  102. func (this *DoubleLinkList) Length() int {
  103. return this.length
  104. }
  105. func (this *DoubleLinkList) Remove(index int) *doubleLinkElement {
  106. if this.length == 0 || index > this.length-1 || index < 0 {
  107. return nil
  108. }
  109. defer func() {
  110. this.length--
  111. }()
  112. ele := this.first
  113. if index == 0 {
  114. this.first = this.first.next
  115. if this.first != nil {
  116. this.first.prev = nil
  117. }
  118. return ele
  119. }
  120. for i := 0; i < index; i++ {
  121. ele = ele.next
  122. }
  123. ele.prev.next = ele.next
  124. if ele.next != nil {
  125. ele.next.prev = ele.prev
  126. }
  127. return ele
  128. }
  129. func (this *DoubleLinkList) Lpop() *doubleLinkElement {
  130. return this.Remove(0)
  131. }
  132. func (this *DoubleLinkList) Rpop() *doubleLinkElement {
  133. return this.Remove(this.length - 1)
  134. }
  135. func (this *DoubleLinkList) Range(f func(index int, item interface{})) {
  136. ele := this.first
  137. for i := 0; i < this.length; i++ {
  138. f(i, ele.item)
  139. ele = ele.next
  140. }
  141. }

测试

  1. package line
  2. import (
  3. "testing"
  4. "time"
  5. )
  6. func TestDoubleLinkList_Insert(t *testing.T) {
  7. double := NewDoubleLinkList()
  8. result := double.Insert(1, time.Now().Unix())
  9. if result {
  10. t.Fatalf("want false, got %#v", result)
  11. }
  12. result = double.Insert(0, 1)
  13. if !result {
  14. t.Fatalf("want true, got %#v", result)
  15. }
  16. length := double.Length()
  17. if length != 1 {
  18. t.Fatalf("want 1, got %#v", length)
  19. }
  20. result = double.Insert(0, 2)
  21. if !result {
  22. t.Fatalf("want true, got %#v", result)
  23. }
  24. result = double.Insert(1, 3)
  25. if !result {
  26. t.Fatalf("want true, got %#v", result)
  27. }
  28. length = double.Length()
  29. if length != 3 {
  30. t.Fatalf("want 3, got %#v", length)
  31. }
  32. r0, _ := double.Get(0)
  33. if r0 != 2 {
  34. t.Fatalf("want 2, got %#v", r0)
  35. }
  36. r1, _ := double.Get(1)
  37. if r1 != 3 {
  38. t.Fatalf("want 3, got %#v", r1)
  39. }
  40. r2, _ := double.Get(2)
  41. if r2 != 1 {
  42. t.Fatalf("want 2, got %#v", r2)
  43. }
  44. }
  45. func TestDoubleLinkList_Pushpop(t *testing.T) {
  46. double := NewDoubleLinkList()
  47. double.Lpush(5)
  48. double.Lpush(4)
  49. double.Lpush(3)
  50. double.Lpush(2)
  51. double.Lpush(1)
  52. double.Rpush(6)
  53. double.Rpush(7)
  54. double.Rpush(8)
  55. double.Rpush(9)
  56. double.Rpush(10)
  57. for i := 1; i < 11; i++ {
  58. item := double.Lpop()
  59. if item.item.(int) != i {
  60. t.Fatalf("want %d; got %#v", i, item.item)
  61. }
  62. }
  63. if double.Length() != 0 {
  64. t.Fatalf("want 0, got %#v", double.Length())
  65. }
  66. double.Range(func(index int, item interface{}) {
  67. t.Fatalf("not run")
  68. })
  69. double.Rpush(6)
  70. double.Rpush(7)
  71. double.Rpush(8)
  72. double.Rpush(9)
  73. double.Rpush(10)
  74. if double.Length() != 5 {
  75. t.Fatalf("want 5, got %#v", double.Length())
  76. }
  77. for i := 10; i > 5; i-- {
  78. item := double.Rpop()
  79. if item.item.(int) != i {
  80. t.Fatalf("want %d; got %#v", i, item.item)
  81. }
  82. }
  83. if double.Length() != 0 {
  84. t.Fatalf("want 0, got %#v", double.Length())
  85. }
  86. }
  87. func TestDoubleLinkList_Set(t *testing.T) {
  88. double := NewDoubleLinkList()
  89. double.Set(0, 0)
  90. double.Set(1, 1)
  91. double.Set(2, 2)
  92. double.Set(3, 3)
  93. for i := 0; i < 4; i++ {
  94. item := double.Lpop()
  95. if item.item.(int) != i {
  96. t.Fatalf("want %d; got %#v", i, item.item)
  97. }
  98. }
  99. }

时间复杂度

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

QQ群:

姜海强的QQ群

公众号:

360tryst公众号