循环链表 python golang实现

循环链表就是将单链表的末尾指向其头部，形成一个环。循环链表的增删操作和单链表的增删操作
区别不大。只是增加时，需要考虑空链表增加第一个节点的特殊情况；删除时需考虑删除节点是头/尾节点，和链表中只有一个节点的特殊情况。

golang实现：

type Node struct {
    value int
    next  *Node
}

type Circle struct {
    tail  *Node
    lenth int
}

// 增加节点：
func (c *Circle) add(value int) {
    newNode := &Node{value, nil}
    if c.lenth == 0 { //空链表中添加节点
        c.tail = newNode
        c.tail.next = newNode
    } else {
        newNode.next = c.tail.next
        c.tail.next = newNode
        c.tail = newNode
    }
    c.lenth += 1
    c.printCircle()
}

// 删除节点：
func (c *Circle) remove(v int) {
    if c.lenth == 0 {
        fmt.Println("空环")
        return
    } else if c.lenth == 1 && c.tail.value == v { //链表中只有一个节点的特殊情况
        c.tail = nil
        c.lenth = 0
        c.printCircle()
        return
    }
    pre := c.tail
    cur := c.tail.next  // 头节点
    for i := 0; i < c.lenth; i++ {
        if cur.value == v {
            if cur == c.tail { //如果删除的节点是尾节点,需更新tail
                c.tail = pre
            }
            pre.next = cur.next
            c.lenth -= 1
            c.printCircle()
            return
        }
        pre = cur
        cur = cur.next
    }
    fmt.Println(v, "不在环中")
}

//打印节点：
func (c *Circle) printCircle() {
    if c.lenth == 0 {
        fmt.Println("空环")
        return
    }
    cur := c.tail.next  // 头节点
    for i := 0; i < c.lenth; i++ {
        fmt.Printf("%d ", cur.value)
        cur = cur.next
    }
    fmt.Println()
}

func testCircle() {
    var circle *Circle = new(Circle)
    //for i := 1; i <=41; i++ {
    //  circle.add(i)
    //}
    circle.add(1)
    circle.remove(10)
    circle.printCircle()
}

python实现：

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

    def __str__(self):
        return str(self.value)

class Circle:
    def __init__(self):
        self.tail = None
        self.lenth = 0

    # 增加节点
    def add(self, v):
        new_node = Node(v)
        if self.lenth == 0:  # 空链表中添加节点
            self.tail = new_node
            self.tail.next = new_node
        else:
            new_node.next = self.tail.next
            self.tail.next = new_node
            self.tail = new_node
        self.lenth += 1

    # 删除节点
    def remove(self, v):
        if self.lenth == 0:
            print("空环")
            return
        elif self.lenth == 1 and self.tail.value == v:  # 链表中只有一个节点的特殊情况
            self.tail = None
            self.lenth = 0
            return
        pre = self.tail
        cur = self.tail.next # 头节点
        for i in range(self.lenth):
            if cur.value == v:
                if cur == self.tail:  # 如果删除的节点是尾节点，需更新tail
                    self.tail = pre
                pre.next = cur.next
                self.lenth -= 1
                return
            pre = cur
            cur = cur.next
        print(v, "不在环中")

    # 打印链表
    def print_circle(self):
        if self.lenth == 0:
            print('空环')
            return
        cur = self.tail.next # 头节点
        for i in range(self.lenth):
            print(cur, end=" ")
            cur = cur.next
        print()


def test():
    c = Circle()
    for i in range(10):
        c.add(i)
    c.print_circle()
    c.remove(0)
    c.print_circle()
    c.remove(10)
    c.print_circle()
    c.remove(9)
    c.print_circle()
    c.remove(4)
    c.print_circle()

有疑问加站长微信联系（非本文作者）