0003 go语言实现循环链表

1 循环链表定义:

引用百度百科 https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8/3228465?fr=aladdin

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

image.png

2 实现功能

1 判断链表是否为空
2 向链表添加元素的
3 遍历链表
4 从指定位置遍历链表
5 删除元素

3 详细代码

3.1 数据结构

type Object interface {}

type Node struct {
    Data Object
    next *Node
}

type CirCleList struct {
    headNode *Node
}

3.2 添加元素

func (this *CirCleList) Add(data Object){
    new_node := &Node{Data:data}
    if this.headNode == nil{
        this.headNode = new_node
    }else{
        cur := this.headNode;
        // 先把cur 运行到尾部
        for cur.next != nil && cur.next  != this.headNode{
            cur = cur.next
        }
        new_node.next = this.headNode
        cur.next = new_node
    }
}

3.3 判断是否为空

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

3.4展示链表

func (this *CirCleList) Show(){
    if this.Empty() {
        fmt.Println("链表为空链表")
    }
    cur := this.headNode;
    fmt.Printf("\t %v", cur.Data)
    for cur.next !=this.headNode{
        // 如果直接打印 cur, 那么最后一个元素永远不会展示出来
        // 所以, 修改成for 循环前打印头元素, for 循环体中打印当前元素的下一个元素
        fmt.Printf("\t %v", cur.next.Data)
        cur = cur.next
    }
}

3.5 从指定元素开始展示链表

func (this *CirCleList) ShowFromNode(data Object){
    if this.Empty() {
        fmt.Println("链表为空链表")
    }
    cur := this.headNode;

    //第一步, 找到指定元素
    for cur.next != nil && cur.next != this.headNode{
        if cur.Data == data{
            break
        }
        cur = cur.next
    }

    if cur.Data != data{
        //
        fmt.Println("链表中未查询到您输入的元素, 无法开始遍历")
        return
    }

    // 从cur 的位置开始遍历
    fmt.Printf("\t %v", cur.Data)
    for cur.next.Data != data{
        fmt.Printf("\t %v", cur.next.Data)
        cur = cur.next
    }
}

3.6删除元素

func (this *CirCleList) RemoveNode(data Object){
    // 第一步, 查找到Node
    cur := this.headNode
    tail := this.TailNode()
    if cur.Data == data {
        // 删除头结点

        this.headNode = cur.next
        tail.next = cur.next
    } else {
        pre := tail
        for cur.next != this.headNode{
            if cur.Data == data{
                break
            }
            cur = cur.next
            pre = pre.next
        }

        //if cur.next == this.headNode{
        //  // 当前元素是最后一个元素, 当前元素的上一个元素指向  this.headNode
        //  pre.next = this.headNode
        //} else {
        //  pre.next = cur.next
        //}
        // 优化为如下代码
        pre.next = cur.next
    }

}

3.7 查找尾部结点

func ( this *CirCleList) TailNode() *Node{
    cur := this.headNode;
    for cur.next != this.headNode{
        cur = cur.next
    }
    return cur
}

调试代码

    list.Add("1")
    list.Add("2")
    list.Add("a")
    list.Add("b")
    //list.Add('3')
    list.Show()
    //删除头部元素
    list.RemoveNode("1")
    fmt.Println()
    list.Show()

    // 删除尾部元素
    list.RemoveNode("b")
    fmt.Println()
    list.Show()