双链表示意图
节点
1package doublylinkedlist
2
3type DoubleLinkNode struct {
4 value interface{}
5 prev *DoubleLinkNode //上一个节点
6 next *DoubleLinkNode //下一个节点
7}
8
9func (node *DoubleLinkNode) Value() interface{} {
10 return node.value
11}
12
13func NewDoubleLinkNode(value interface{}) *DoubleLinkNode {
14 return &DoubleLinkNode{value, nil, nil}
15}
16
17func (node *DoubleLinkNode) Prev() *DoubleLinkNode {
18 return node.prev
19}
20
21func (node *DoubleLinkNode) Next() *DoubleLinkNode {
22 return node.next
23}
双链表实现
1package doublylinkedlist
2
3import (
4 "fmt"
5 "strings"
6)
7
8type DoubleLinkList struct {
9 head *DoubleLinkNode
10 length int
11}
12
13//新建一个双链表
14func NewDoubleLinkList() *DoubleLinkList {
15 node := NewDoubleLinkNode(nil)
16 return &DoubleLinkList{node, 0}
17}
18
19//获得链表长度
20func (dlist *DoubleLinkList) GetLength() int {
21 return dlist.length
22}
23
24//返回第一个节点 （数据值不为nil的节点）
25func (dlist *DoubleLinkList) GetFirstNode() *DoubleLinkNode {
26 return dlist.head.next
27}
28
29// 头部插入 节点
30
31func (dlist *DoubleLinkList) InsertHead(node *DoubleLinkNode) {
32 phead := dlist.head //头节点
33 // 没有第一个节点
34 if phead.next == nil {
35 node.next = nil
36 phead.next = node
37 node.prev = phead
38 } else {
39 //已经有第一个节点
40 phead.next.prev = node //标记上一个节点
41 node.next = phead.next //下一个节点
42 phead.next = node //标记头部节点的下一个节点
43 node.prev = phead //node上一个节点 指向头节点
44 }
45 dlist.length++
46}
47
48//尾部插入节点
49func (dlist *DoubleLinkList) InsertBack(node *DoubleLinkNode) {
50 phead := dlist.head
51 for phead.next != nil {
52 phead = phead.next
53 }
54 //phead 为最后一个节点
55 phead.next = node
56 // node.next=nil 可以省略 node 默认next 就是nil
57 node.prev = phead
58 dlist.length++
59}
60
61// 打印链表
62func (dlist *DoubleLinkList) String() string {
63 var listString1 string
64 var listString2 string
65 phead := dlist.head
66 for phead.next != nil {
67 listString1 += fmt.Sprintf("%v-->", phead.next.value)
68 phead = phead.next
69 }
70 listString1 += fmt.Sprintf("nil")
71 listString1 += "\n"
72 // 此时 phead 已经是最后一个节点了
73 for phead != dlist.head {
74 //反向循环
75 listString2 += fmt.Sprintf("<--%v", phead.value)
76 phead = phead.prev
77 }
78 listString1 += fmt.Sprintf("nil")
79 return "\n" + listString1 + listString2 + "\n" //打印链表字符串
80}
81
82//指定节点后面插入
83func (dlist *DoubleLinkList) InsertNodeBack(dest *DoubleLinkNode, node *DoubleLinkNode) bool {
84 phead := dlist.head
85 for phead.next != nil && phead.next != dest { //循环查找
86 phead = phead.next
87 }
88 // value cur prev next
89 // 1 400100 40000 40200
90 // 2 40200 400100 40300
91 // 3 40300 40200 nil
92 // node 400150
93 //目标节点是 2 后面插入
94 if phead.next == dest {
95 //看已经是不是最后了 是最后了 只有3步 ，否则是4步
96 if phead.next.next != nil {
97 phead.next.next.prev = node //400150
98 }
99 node.next = phead.next.next //400300
100 phead.next.next = node // 400150
101 node.prev = phead.next // 400200
102 dlist.length++
103 return true
104 } else {
105 return false
106 }
107}
108
109//指定节点前面 插入
110func (dlist *DoubleLinkList) InsertNodeHead(dest *DoubleLinkNode, node *DoubleLinkNode) bool {
111
112 phead := dlist.head
113 for phead.next != nil && phead.next != dest {
114 phead = phead.next
115 }
116 if phead.next == dest {
117 if phead.next != nil { //这个应该去掉
118 phead.next.prev = node
119 }
120 node.next = phead.next
121 node.prev = phead
122 phead.next = node
123 dlist.length++
124 return true
125 } else {
126 return false
127 }
128}
129
130//根据值 后插入
131func (dlist *DoubleLinkList) InsertValueBack(dest interface{}, node *DoubleLinkNode) bool {
132 phead := dlist.head
133 for phead.next != nil && phead.next.value != dest {
134 phead = phead.next
135 }
136 if phead.next.value == dest {
137 if phead.next.next != nil {
138 phead.next.next.prev = node
139 }
140 node.next = phead.next.next
141 phead.next.next = node
142 node.prev = phead.next
143 dlist.length++
144 return true
145 } else {
146 return false
147 }
148}
149
150//根据值 前插入
151func(dlist* DoubleLinkList) InsertValueHead(dest interface{},node *DoubleLinkNode )bool{
152 phead:=dlist.head
153 for phead.next!=nil && phead.next.value!=dest{ //循环查找
154 phead=phead.next
155 }
156 if phead.next.value==dest{
157 if phead.next!=nil{
158 phead.next.prev=node
159 }
160 node.next=phead.next
161 node.prev=phead
162 phead.next=node
163 dlist.length++
164 return true
165 }else{
166 return false
167 }
168}
169
170// 根据索引获得节点 0 代表 第一个节点，头节点的值是nil
171func (dlist *DoubleLinkList) GetNodeAtindex(index int) *DoubleLinkNode {
172 if index > dlist.length-1 || index < 0 {
173 return nil
174 }
175 phead := dlist.head
176 for index > -1 {
177 phead = phead.next
178 index-- //计算位置
179 }
180 return phead
181
182 // var i int
183 // node := dlist.head
184 // for node.next != nil {
185 // node = node.next
186 // if index == i {
187 // //break
188 // return node
189 // }
190 // i++
191 // }
192 // return node
193}
194
195//删除指定节点
196func (dlist *DoubleLinkList) DeleteNode(node *DoubleLinkNode) bool {
197 if node == nil {
198 return false
199 } else {
200 phead := dlist.head
201 for phead.next != nil && phead.next != node {
202 phead = phead.next //循环查找
203 }
204 if phead.next == node {
205 if phead.next.next != nil {
206 phead.next.next.prev = phead //设置pre
207 }
208 phead.next = phead.next.next //设置next
209 dlist.length--
210 return true
211 } else {
212 return false
213 }
214 }
215}
216
217//删除指定位置节点
218func (dlist *DoubleLinkList) DeleteNodeAtindex(index int) bool {
219 if index > dlist.length-1 || index < 0 {
220 return false
221 }
222 phead := dlist.head
223 for index > 0 {
224 phead = phead.next
225 index-- //计算位置
226 }
227
228 if phead.next.next != nil {
229 phead.next.next.prev = phead //设置pre
230 }
231 phead.next = phead.next.next //设置next
232 dlist.length--
233 return true
234}
235
236func (dlist *DoubleLinkList) FindString(inputstr string) {
237 phead := dlist.head.next
238 for phead.next != nil {
239 //正向循环
240 if strings.Contains(phead.value.(string), inputstr) {
241 fmt.Println(phead.value.(string))
242 }
243 phead = phead.next
244 }
245}
测试
1package doublylinkedlist
2
3import (
4 "testing"
5)
6
7
8func TestDoubleLink(t *testing.T) {
9 dobleLink :=NewDoubleLinkList()
10
11 node1 :=NewDoubleLinkNode(1)
12 node2 :=NewDoubleLinkNode(2)
13 node3 :=NewDoubleLinkNode(3)
14 node4 :=NewDoubleLinkNode(4)
15 node5 :=NewDoubleLinkNode(5)
16 node6 :=NewDoubleLinkNode(6)
17 node7 :=NewDoubleLinkNode(7)
18 node8 :=NewDoubleLinkNode(8)
19 node9 :=NewDoubleLinkNode(9)
20 node10 :=NewDoubleLinkNode(10)
21 dobleLink.InsertHead(node1)
22 dobleLink.InsertHead(node2)
23 dobleLink.InsertHead(node3)
24 dobleLink.InsertHead(node4)
25 t.Log(dobleLink.String())
26 dobleLink.InsertBack(node5)
27 dobleLink.InsertBack(node6)
28 t.Log(dobleLink.String())
29 dobleLink.DeleteNode(node5)
30 t.Log(dobleLink.String())
31 dobleLink.DeleteNode(node6)
32 t.Log(dobleLink.String())
33 t.Log("获得第一个节点值",dobleLink.GetFirstNode().Value())
34 dobleLink.InsertNodeBack(node4,node7)
35 t.Log(dobleLink.String())
36 dobleLink.InsertNodeHead(node4,node8)
37 t.Log(dobleLink.String())
38 dobleLink.InsertValueBack(8,node9)
39 t.Log(dobleLink.String())
40 dobleLink.InsertValueHead(8,node10)
41 t.Log(dobleLink.String())
42 dobleLink.DeleteNodeAtindex(0)
43 t.Log(dobleLink.String())
44}