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()

来源：https://www.jianshu.com/p/73095503dfdd