002 go语言实现双向链表

1 双向链表

代码仓库
https://gitee.com/babyb/data_srtuct

根据百度百科定义:

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

2 实现功能

双向链表与单项链表差不多, 区别就在于每个节点多了个 pre, 在删除元素的时候需要注意, 所以简单的实现以下功能
1 添加元素
2 从头向尾开始展示链表
3 从尾向头展示链表
4 删除元素
5 获取链表长度
6 判断链表是否为空

3 数据结构

空接口是指没有定义任何接口方法的接口。
没有定义任何接口方法，
意味着Go中的任意对象都可以实现空接口(因为没方法需要实现)，
任意对象都可以保存到空接口实例变量中。

type Object interface {}

type Node struct {
    Data Object
    pre  *Node
    next *Node
}

type DoubleList struct {
    headNode *Node
}

4 每个具体的方法

4.1 判断链表是否为空

func (this *DoubleList) Empty() bool{
    if this.headNode == nil {
        return  true
    }else {
        return false
    }
}

4.2尾部添加元素

func (this *DoubleList) Add(data Object){
    node := &Node{ Data: data}
    cur := this.headNode
    if cur == nil{
        this.headNode = node
    }else{
        for cur.next != nil{
            cur = cur.next
        }
        node.pre = cur
        cur.next = node
    }
}

4.3链表长度

func (this *DoubleList) Length() int{
    count := 0;
    cur  := this.headNode;
    if cur != nil{
        for cur != nil{
            cur = cur.next
            count ++
        }
    }
    return count
}

4.4 从前向后展示链表

func (this *DoubleList) ShowList(){
    cur := this.headNode;
    for cur != nil{
        fmt.Printf("\t %v", cur.Data)
        cur = cur.next
    }
    fmt.Println()
}

4.5从后向前展示

func (this *DoubleList) ShowListFromTail(){
    tail := this.headNode;
    for tail.next != nil{
        tail = tail.next
    }

    for tail !=nil{
        fmt.Printf("\t %v", tail.Data)
        tail = tail.pre
    }
}

4.6 移除元素

func (this *DoubleList) RemoveNode(data Object){
    cur := this.headNode
    if cur.Data == data{
        // 移除头元素
        new_head := cur.next;
        new_head.pre = nil;
        this.headNode = new_head
    }else{
        for cur !=nil{
            if cur.Data == data{
                // 移除元素
                pre := cur.pre;
                next := cur.next;

                //当前节点被跳过, 会被当做垃圾回收掉
                next.pre = pre;
                pre.next = next
            }
            cur = cur.next
        }
    }
}

5 测试代码

package main

import (
    "data_struct/0002_double_linked_list"
    "fmt"
)

func main(){
    list := doubleLinkedList.DoubleList{}
    fmt.Println("链表是否为空" , list.Empty())
    list.Add("1")
    fmt.Println("链表是否为空" , list.Empty())

    fmt.Println("链表长度", list.Length())
    list.Add("a")
    fmt.Println("链表长度", list.Length())

    list.Add("b")
    list.Add("+c")

    list.ShowList()
    //fmt.Println("从后向前展示元素")
    //list.ShowListFromTail()

    list.RemoveNode("b")
    list.ShowList()

    list.RemoveNode("1")
    list.ShowList()


}