数据结构：Go语言实现双向链表

代码

package main

import "fmt"

type Element interface{}

var NoData Element = 0

type Node struct {
    Data Element
    Next *Node
    Pre  *Node
}

type List struct {
    Head   *Node
    Length int
}

// 创建双向链表
func Create() *List {
    head := new(Node)
    return &List{Head: head, Length: 0}
}

// 获取链表长度
func (l *List) Len() int {
    return l.Length
}

// 判断是否为空链表
func (l *List) IsEmpty() bool {
    if l.Head.Next == nil && l.Head.Pre == nil {
        return true
    }
    return false
}

// 向链表末尾追加数据
func (l *List) Append(e Element) {
    node := &Node{Data: e, Next: nil, Pre: nil}

    p := l.Head
    if l.IsEmpty() {
        p.Next = node
        node.Pre = p

        l.Length++
        return
    }

    for p.Next != nil {
        p = p.Next
    }

    p.Next = node
    node.Pre = p
    l.Length++

    return
}

// 在头部追加数据
func (l *List) PreAppend(e Element) {
    p := l.Head
    node := &Node{Data: e, Next: nil, Pre: nil}

    if l.IsEmpty() {
        p.Next = node
        node.Pre = p

        l.Length++

        return
    }

    // 插入节点的 NEXT 指向头节点的 Next
    node.Next = p.Next
    // 头节点的 Next 的 Pre 指向 新插入的节点
    p.Next.Pre = node

    // 头节点的 Next 指向 新插入的节点
    p.Next = node
    // 新插入节点的 Pre 指向头节点
    node.Pre = p

    l.Length++

    return
}

// 在指定位置插入数据
func (l *List) Insert(index int, e Element) {
    if l.IsEmpty() || index < 0 {
        l.PreAppend(e)

        return
    }

    if index > l.Len() {
        l.Append(e)

        return
    }

    p := l.Head
    node := &Node{Data: e, Next: nil, Pre: nil}

    for i := 0; i < index-1; i++ {
        p = p.Next
    }

    // 新插入节点的 Next 节点指向 p[index-1]的Next 节点
    node.Next = p.Next
    // p[index - 1]的 Next.Pre 节点 指向 node 节点
    p.Next.Pre = node

    // p[index -1] 的Next 节点 指向 新插入的节点
    p.Next = node
    // ❤新插入的节点的Pre 指向 p[index-1]
    node.Pre = p

    l.Length++

    return
}

// 删除指定位置的数据, 并返回该数据
func (l *List) Delete(index int) Element {
    if l.IsEmpty() {
        fmt.Println("list is empty. delete error")
        return NoData
    }

    if index < 0 || index > l.Len() {
        fmt.Println("index out of range. delete error")
    }

    p := l.Head
    for i := 0; i < index; i++ {
        p = p.Next
    }

    e := p.Data

    // 先将 p [index -1] 的 Next 指向 p [index] 的 Next
    p.Pre.Next = p.Next

    // 再将 p [index + 1] 的 Pre 指向 p [index -1]
    p.Next.Pre = p.Pre

    l.Length--

    return e

}

// 查找指定位置的数据 。
func (l *List) Query(index int) Element {
    if l.IsEmpty() {
        fmt.Println("list is empty. ")

        return NoData
    }

    if index < 0 || index > l.Len() {
        return NoData
    }

    p := l.Head

    for i := 0; i < index; i++ {
        p = p.Next
    }

    return p.Data
}

// 打印链表
func (l *List) Print() {
    if l.IsEmpty() {
        fmt.Println("list is empty")
    }

    p := l.Head.Next
    i := 1
    for p != nil {
        fmt.Printf("iNode %d, Data %#v\n", i, p.Data)
        i++
        p = p.Next
    }
}

func main() {
    l := Create()

    l.Append(111)
    l.Append(222)
    l.Append(333)
    l.Append(555)

    l.Insert(4, 444)
    fmt.Println("delete ===", l.Delete(3))

    fmt.Println("query ===", l.Query(2))

    l.Print()
    fmt.Println("len ==", l.Len())

}