关于数据结构:数据结构双向链表

51次阅读

共计 1714 个字符,预计需要花费 5 分钟才能阅读完成。

双向链表的一种 Go 语言实现

package main

import "fmt"

// 定义节点信息
type dNode struct {
    id int
    name string
    pre *dNode
    next *dNode
}

// 尾部插入节点
func dInsertTail(head, newNode *dNode) {
    // 定义一个长期游走变量
    temp := head
    for {
        if temp.next == nil{break // 游走到链表尾部后跳出循环进行插入数据}
        temp = temp.next
    }

    // 尾部增加绝对简略
    temp.next = newNode
    newNode.pre = temp
}

// 头部插入节点
func dInsertHead(head, newNode *dNode) {
    temp := head
    // 先连贯新节点的两条链到链表
    newNode.next = temp.next
    newNode.pre = temp
    // 再拆旧连贯到新连贯上
    temp.next = newNode
    temp.next.pre = newNode
}

// 程序插入节点
func dInsertSort(head, newNode *dNode){
    temp := head
    for {
        if temp.next == nil{
            newNode.next = temp.next
            newNode.pre = temp
            temp.next = newNode
            //temp.next.pre = newNode
            break
        } else if temp.next.id >= newNode.id {
            newNode.next = temp.next
            newNode.pre = temp
            temp.next = newNode
            temp.next.pre = newNode
            break
        }
        temp = temp.next
    }
}

// 头部删除节点
func dDeleteHead(head *dNode){
    if head.next == nil{return}else {head.next = head.next.next}
}

// 尾部删除节点
func dDeleteTail(head *dNode){
    temp := head

    for {
        if temp.next == nil {return} else if temp.next.next == nil{
            // 删除节点
            temp.next = nil
            break
        }
        temp = temp.next
    }
}

// 删除指定节点
func dDeleteNode(head, node * dNode){
    temp := head
    for {
        if temp.next == nil {return}else if temp.next.id == node.id {
            temp.next = temp.next.next
            temp.next.pre = temp
            break
        }
        temp = temp.next
    }
}

// 显示链表元素
func dList(head *dNode){
    temp := head
    if temp.next == nil {fmt.Println("链表为空")
        return
    }
    for {
        // 留神这里,我所有的思路都是在链表的以后节点操作下一个节点
        fmt.Printf("%d  %s -->", temp.next.id, temp.next.name)
        temp = temp.next
        if temp.next == nil{break}
    }
}

func main(){head := &dNode{}

    node1 := &dNode{
        id:   0,
        name: "number1",
        pre:  nil,
        next: nil,
    }
    node2 := &dNode{
        id:   1,
        name: "number2",
        pre:  nil,
        next: nil,
    }
    node3 := &dNode{
        id:   2,
        name: "number3",
        pre:  nil,
        next: nil,
    }
    node4 := &dNode{
        id:   3,
        name: "number4",
        pre:  nil,
        next: nil,
    }
    dInsertHead(head, node1)
    dInsertTail(head, node3)
    dInsertSort(head, node2)
    dInsertSort(head, node4)
    dDeleteHead(head)
    dDeleteTail(head)
    dDeleteNode(head, node2)
    dList(head)
}

正文完
 0