Go（Golang）中的反向二重链接列表

概述

二重链接列表可以通过以下两种方法进行反转。

• 通过交换节点的上一个和下一个指针。

• 通过使用堆栈

在本教程中，我们将介绍第一种方法，即通过交换上一个和下一个指针。

比方说，我们有以下的双链表

颠倒之后，双链表就会变成下面这样。

程序

在这种方法中，我们需要注意以下几点。

• 交换双链表的头和尾

• 交换所有节点的上一个和下一个指针

package main
import "fmt"
type node struct {
    data string
    prev *node
    next *node
}
type doublyLinkedList struct {
    len  int
    tail *node
    head *node
}
func initDoublyList() *doublyLinkedList {
    return &doublyLinkedList{}
}
func (d *doublyLinkedList) AddFrontNodeDLL(data string) {
    newNode := &node{
        data: data,
    }
    if d.head == nil {
        d.head = newNode
        d.tail = newNode
    } else {
        newNode.next = d.head
        d.head.prev = newNode
        d.head = newNode
    }
    d.len++
}
func (d *doublyLinkedList) AddEndNodeDLL(data string) {
    newNode := &node{
        data: data,
    }
    if d.head == nil {
        d.head = newNode
        d.tail = newNode
    } else {
        currentNode := d.head
        for currentNode.next != nil {
            currentNode = currentNode.next
        }
        newNode.prev = currentNode
        currentNode.next = newNode
        d.tail = newNode
    }
    d.len++
}
func (d *doublyLinkedList) TraverseForward() error {
    if d.head == nil {
        return fmt.Errorf("TraverseError: List is empty")
    }
    temp := d.head
    for temp != nil {
        fmt.Printf("value = %v, prev = %v, next = %v\n", temp.data, temp.prev, temp.next)
        temp = temp.next
    }
    fmt.Println()
    return nil
}
func (d *doublyLinkedList) Size() int {
    return d.len
}
func (d *doublyLinkedList) ReverseDLL() {
    currentNode := d.head
    var nextInList *node
    d.head, d.tail = d.tail, d.head
    for currentNode != nil {
        nextInList = currentNode.next
        currentNode.next, currentNode.prev = currentNode.prev, currentNode.next
        currentNode = nextInList
    }
}
func main() {
    doublyList := initDoublyList()
    fmt.Printf("Add Front Node: C\n")
    doublyList.AddFrontNodeDLL("C")
    fmt.Printf("Add Front Node: B\n")
    doublyList.AddFrontNodeDLL("B")
    fmt.Printf("Add Front Node: A\n")
    doublyList.AddFrontNodeDLL("A")
    fmt.Printf("Add End Node: D\n")
    doublyList.AddEndNodeDLL("D")
    fmt.Printf("Add End Node: E\n")
    doublyList.AddEndNodeDLL("E")
    fmt.Printf("Size of doubly linked ist: %d\n", doublyList.Size())
    err := doublyList.TraverseForward()
    if err != nil {
        fmt.Println(err.Error())
    }
    fmt.Println("Reversing Doubly Linked List")
    doublyList.ReverseDLL()
    fmt.Printf("Size of doubly linked ist: %d\n", doublyList.Size())
    err = doublyList.TraverseForward()
    if err != nil {
        fmt.Println(err.Error())
    }
}
复制代码

输出

Add Front Node: C
Add Front Node: B
Add Front Node: A
Add End Node: D
Add End Node: E
Size of doubly linked ist: 5
value = A, prev = , next = &{B 0xc000070060 0xc000070020}
value = B, prev = &{A  0xc000070040}, next = &{C 0xc000070040 0xc000070080}
value = C, prev = &{B 0xc000070060 0xc000070020}, next = &{D 0xc000070020 0xc0000700a0}
value = D, prev = &{C 0xc000070040 0xc000070080}, next = &{E 0xc000070080 }
value = E, prev = &{D 0xc000070020 0xc0000700a0}, next = 

Reversing Doubly Linked List
Size of doubly linked ist: 5
value = E, prev = , next = &{D 0xc0000700a0 0xc000070020}
value = D, prev = &{E  0xc000070080}, next = &{C 0xc000070080 0xc000070040}
value = C, prev = &{D 0xc0000700a0 0xc000070020}, next = &{B 0xc000070020 0xc000070060}
value = B, prev = &{C 0xc000070080 0xc000070040}, next = &{A 0xc000070040 }
value = A, prev = &{B 0xc000070020 0xc000070060}, next = 
复制代码

另外，请查看我们的Golang高级教程系列——。 Golang高级教程

The postReverse Doubly Linked List in Go (Golang)appeared first onWelcome To Golang By Example.