# 双向链表的GO语言实现

1、节点

``````type DNode struct {
data Object
prev *DNode
next *DNode
}
``````

2、双向链表

``````type DList struct {
size uint64
tail *DNode
}
``````

1、初始化链表Init

``````func (dList *DList) Init() {
_dList := *(dList)
_dList.size = 0     // 没车厢
_dList.tail = nil   // 没车尾
}
``````

2、新增数据Append

``````func (dList *DList) Append(data Object) {
newNode := new(DNode)
(*newNode).data =  data

if (*dList).GetSize() == 0 { // 买个车头
(*dList).tail = newNode
(*newNode).prev = nil
(*newNode).next = nil
} else { //  挂在车队尾部
(*newNode).prev = (*dList).tail
(*newNode).next = nil
(*((*dList).tail)).next = newNode
(*dList).tail = newNode
}

(*dList).size++;
}
``````

3、在节点后面插入数据InsertNext

``````func (dList *DList) InsertNext(elmt *DNode, data Object) bool {
if elmt == nil { // apend
return false
}

if dList.isTail(elmt) { // 恰好在车队尾巴
dList.Append(data)
} else {
newNode := new(DNode)
(*newNode).data =  data
(*newNode).prev = elmt
(*newNode).next = (*elmt).next

(*elmt).next = newNode
(*((*newNode).next)).prev = newNode
(*dList).size++;
}

return true
}
``````

5、在节点前面插入数据InsertPrev

``````func (dList *DList) InsertPrev(elmt *DNode, data Object) bool {
if elmt == nil {
return false
}

newNode := new(DNode)
(*newNode).data = data
(*newNode).prev = nil

dList.size++
return true
} else {
prev := (*elmt).prev
return dList.InsertNext(prev, data)
}
}
``````

6、删除一个节点Remove

``````func (dList *DList) Remove(elmt *DNode) Object {
if elmt == nil {
return false
}

prev := (*elmt).prev
next := (*elmt).next

} else {
(*prev).next = next
}

if dList.isTail(elmt) {
dList.tail = prev
} else {
(*next).prev = prev
}

dList.size--

return (*elmt).GetData()
}
``````

7、查找指定数据所在的节点Search

``````func (dList *DList) Search(data Object, yourMatch ...MatchFun) *DNode {
if dList.GetSize() == 0 {
return nil
}

match := defaultMatch
if len(yourMatch) > 0 {
match = yourMatch[0]
}

for ; node != nil; node = node.GetNext() {
if match(node.GetData(), data) == 0 {
break
}
}

return node
}
``````

match是匹配函数，定义如下：

``````type MatchFun func (data1 Object, data2 Object) int
``````

8、获取链表长度GetSize

``````func (dList *DList) GetSize() uint64 {
return (*dList).size
}
``````

``````func (dList *DList) GetHead() *DNode {
}
``````

10、获取尾部节点GetTail

``````func (dList *DList) GetTail() *DNode {
return (*dList).tail
}
``````

``````func (dList *DList) isHead(elmt *DNode) bool {
}
``````

12、节点是否是列表尾部isTail

``````func (dList *DList) isTail(elmt *DNode) bool {
return dList.GetTail() == elmt
}
``````

13、获取节点内数据GetData

``````func (dNode *DNode) GetData() Object {
return (*dNode).data
}
``````

14、获取下一个节点GetNext

``````func (dNode *DNode) GetNext() *DNode {
return (*dNode).next
}
``````

15、获取前一个节点GetPrev

``````func (dNode *DNode) GetPrev() *DNode {
return (*dNode).prev
}
``````

2 回复  |  直到 2017-11-10 03:10:47

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

1、节点

``````type DNode struct {
data Object
prev *DNode
next *DNode
}
``````

2、双向链表

``````type DList struct {
size uint64
tail *DNode
}
``````

1、初始化链表Init

``````func (dList *DList) Init() {
_dList := *(dList)
_dList.size = 0     // 没车厢
_dList.tail = nil   // 没车尾
}
``````

2、新增数据Append

``````func (dList *DList) Append(data Object) {
newNode := new(DNode)
(*newNode).data =  data

if (*dList).GetSize() == 0 { // 买个车头
(*dList).tail = newNode
(*newNode).prev = nil
(*newNode).next = nil
} else { //  挂在车队尾部
(*newNode).prev = (*dList).tail
(*newNode).next = nil
(*((*dList).tail)).next = newNode
(*dList).tail = newNode
}

(*dList).size++;
}
``````

3、在节点后面插入数据InsertNext

``````func (dList *DList) InsertNext(elmt *DNode, data Object) bool {
if elmt == nil { // apend
return false
}

if dList.isTail(elmt) { // 恰好在车队尾巴
dList.Append(data)
} else {
newNode := new(DNode)
(*newNode).data =  data
(*newNode).prev = elmt
(*newNode).next = (*elmt).next

(*elmt).next = newNode
(*((*newNode).next)).prev = newNode
(*dList).size++;
}

return true
}
``````

5、在节点前面插入数据InsertPrev

``````func (dList *DList) InsertPrev(elmt *DNode, data Object) bool {
if elmt == nil {
return false
}

newNode := new(DNode)
(*newNode).data = data
(*newNode).prev = nil

dList.size++
return true
} else {
prev := (*elmt).prev
return dList.InsertNext(prev, data)
}
}
``````

6、删除一个节点Remove

``````func (dList *DList) Remove(elmt *DNode) Object {
if elmt == nil {
return false
}

prev := (*elmt).prev
next := (*elmt).next

} else {
(*prev).next = next
}

if dList.isTail(elmt) {
dList.tail = prev
} else {
(*next).prev = prev
}

dList.size--

return (*elmt).GetData()
}
``````

7、查找指定数据所在的节点Search

``````func (dList *DList) Search(data Object, yourMatch ...MatchFun) *DNode {
if dList.GetSize() == 0 {
return nil
}

match := defaultMatch
if len(yourMatch) > 0 {
match = yourMatch[0]
}

for ; node != nil; node = node.GetNext() {
if match(node.GetData(), data) == 0 {
break
}
}

return node
}
``````

match是匹配函数，定义如下：

``````type MatchFun func (data1 Object, data2 Object) int
``````

8、获取链表长度GetSize

``````func (dList *DList) GetSize() uint64 {
return (*dList).size
}
``````

``````func (dList *DList) GetHead() *DNode {
}
``````

10、获取尾部节点GetTail

``````func (dList *DList) GetTail() *DNode {
return (*dList).tail
}
``````

``````func (dList *DList) isHead(elmt *DNode) bool {
}
``````

12、节点是否是列表尾部isTail

``````func (dList *DList) isTail(elmt *DNode) bool {
return dList.GetTail() == elmt
}
``````

13、获取节点内数据GetData

``````func (dNode *DNode) GetData() Object {
return (*dNode).data
}
``````

14、获取下一个节点GetNext

``````func (dNode *DNode) GetNext() *DNode {
return (*dNode).next
}
``````

15、获取前一个节点GetPrev

``````func (dNode *DNode) GetPrev() *DNode {
return (*dNode).prev
}
``````