golang算法练习：单链表/双链表/环形链表

以你之姓@ 2021-12-03 15:05 437阅读 0赞

### 需求 ###

链表，常见且非常灵活的数据模型，可定制性强，可根据需求调整满足不同的使用需求，如FIFO\\LIFO，快速查找等，这里分别列举基础的单向链表和双向链表增删改查操作  
**备注：需求和运行输出结果均已在代码中注释**

### 单向链表 ###

代码

package main
    
    import (
    	"errors"
    	"fmt"
    )
    
    type Node struct { 
    	id   int
    	name string
    	next *Node
    }
    
    type SingleLink struct { 
    	head *Node
    }
    
    func (singleLink *SingleLink) orderInsert(node *Node) { 
    	// 按Node.id从小到大的顺序，插入链表中
    	curNode := singleLink.head
    	if curNode.id == 0 { 
    		// 第一次插入元素的空链表
    		singleLink.head = node
    	} else { 
    		// 如果node.id比队首id小，则队首让位后移，要保证队首最小。因为取值比较的时候， 是取curNode.next节点与node进行比较，如果满足大小顺序，
    		// 则将node插入curNode和curNode.next之间
    		if curNode.id > node.id { 
    			node.next = curNode
    			singleLink.head = node
    		} else { 
    			// 如果node.id不比队首id小，则往后取一位，用后一位与node比较，匹配则插入当前位与后一位中间
    			for { 
    				if curNode.next == nil { 
    					// 循环到最后一位都没有插入成功，说明node.id比现有链表中的所有node的id都大，则node成为新的队尾
    					curNode.next = node
    					break
    				}
    				if curNode.next.id > node.id { 
    					node.next = curNode.next
    					curNode.next = node
    					break
    				}
    				curNode = curNode.next
    			}
    		}
    	}
    }
    
    func (singleLink *SingleLink) pop(id int) (node *Node, err error) { 
    	// 弹出链表中指定id的node
    	curNode := singleLink.head
    	if curNode.id == id { 
    		// 要取的是队首
    		singleLink.head = singleLink.head.next
    		return curNode, nil
    	}
    	flag := false // 是否查找到的标志
    	for { 
    		if curNode.next == nil { 
    			break
    		}
    		if curNode.next.id == id { 
    			flag = true
    			selectNode := curNode.next
    			curNode.next = curNode.next.next
    			return selectNode, nil
    		}
    		curNode = curNode.next
    	}
    	if !flag { 
    		// 如果循环结束还没有查找到，输出信息
    		return nil, errors.New("node not found")
    	}
    	return
    }
    
    func (singleLink *SingleLink) getLength() (number int) { 
    	curNode := singleLink.head
    	if singleLink.head.id == 0 || singleLink.head == nil { 
    		// 空链表
    		return
    	} else { 
    		for { 
    			number += 1
    			curNode = curNode.next
    			if curNode == nil { 
    				break
    			}
    		}
    	}
    	fmt.Println("current link length:", number)
    	return number
    }
    
    func (singleLink *SingleLink) list() { 
    	if singleLink.head == nil || singleLink.head.id == 0 { 
    		fmt.Println("link is empty")
    	} else { 
    		curNode := singleLink.head
    		for { 
    			if curNode == nil { 
    				break
    			}
    			fmt.Print(*curNode, "==>")
    			curNode = curNode.next
    		}
    	}
    	fmt.Println()
    
    }
    
    func main() { 
    	// 约定空链表的header初始id为0，后面加入的实例id必须大于0
    	var originalHead = Node{ 
    		id: 0,
    	}
    	var s = SingleLink{ 
    		head: &originalHead,
    	}
    	var node1 = Node{ 
    		id:   1,
    		name: "001",
    	}
    	var node2 = Node{ 
    		id:   2,
    		name: "002",
    	}
    	var node3 = Node{ 
    		id:   3,
    		name: "003",
    	}
    	var node4 = Node{ 
    		id:   4,
    		name: "004",
    	}
    	var node5 = Node{ 
    		id:   5,
    		name: "005",
    	}
    
    	s.orderInsert(&node4)
    	s.list()
    	s.orderInsert(&node2)
    	s.list()
    	s.orderInsert(&node3)
    	s.list()
    	s.orderInsert(&node5)
    	s.list()
    	s.orderInsert(&node1)
    	s.list()
    	s.getLength()
    	popNode, err := s.pop(3)
    	if err != nil { 
    		fmt.Println(err)
    	}
    	fmt.Println("pop node successfully:", *popNode)
    	s.list()
    
    	/* output: {4 004 <nil>}==> {2 002 0xc00000a0e0}==>{4 004 <nil>}==> {2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 <nil>}==> {2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==> {1 001 0xc00000a0a0}==>{2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==> current link length: 5 pop node successfully: {3 003 0xc00000a0e0} {1 001 0xc00000a0a0}==>{2 002 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==> */
    }

**问题**  
单向链表的操作必须从首部开始，那么可不可以灵活一些，比如从尾部开始呢？当然可以，改造成双向链表即可满足

### 双向链表 ###

代码：  
为了以示区别，增删改查全部改为从尾部开始循环

package main
    
    import (
    	"errors"
    	"fmt"
    )
    
    type Node struct { 
    	id   int
    	name string
    	next *Node
    	prev *Node
    }
    
    type CircleLink struct { 
    	head *Node
    	tail *Node
    }
    
    func (circleLink *CircleLink) orderInsert(node *Node) { 
    	// 按Node.id从小到大的顺序，插入链表中
    	curNode := circleLink.head
    	if curNode.id == 0 { 
    		// 第一次插入元素的空链表
    		circleLink.head = node
    		circleLink.tail = node
    	} else { 
    		// 如果node.id比队首id小，则队首让位后移，要保证队首最小。因为取值比较的时候， 是取curNode.next节点与node进行比较，如果满足大小顺序，
    		// 则将node插入curNode和curNode.next之间
    		if curNode.id > node.id { 
    			node.next = curNode
    			curNode.prev = node
    			circleLink.head = node
    		} else { 
    			// 如果node.id不比队首id小，则往后取一位，用后一位与node比较，匹配则插入当前位与后一位中间
    			for { 
    				if curNode.next == nil { 
    					// 循环到最后一位都没有插入成功，说明node.id比现有链表中的所有node的id都大，则node成为新的队尾
    					curNode.next = node
    					node.prev = curNode
    					circleLink.tail = node
    					break
    				}
    				if curNode.next.id > node.id { 
    					node.next = curNode.next
    					node.prev = curNode
    					curNode.next.prev = node
    					curNode.next = node
    					break
    				}
    				curNode = curNode.next
    			}
    		}
    	}
    }
    
    func (circleLink *CircleLink) pop(id int) (node *Node, err error) { 
    	// 弹出链表中指定id的node.这次从链表尾部往首部循环
    	curNode := circleLink.tail
    	if curNode.id == id { 
    		// 要取的是队尾
    		circleLink.tail = circleLink.tail.prev
    		return curNode, nil
    	}
    	flag := false // 是否查找到的标志
    	for { 
    		if curNode.prev == nil { 
    			// 已经从队尾达到队首,全部都没命中
    			break
    		}
    		if curNode.id == id { 
    			flag = true
    			selectNode := curNode
    			if curNode == circleLink.head { 
    				// 如果命中的节点正好是队首
    				if circleLink.head.next != nil { 
    					// 如果队首后面还有节点，则第二个节点置为新的首节点，且第二个节点的prev指向置为nil，这样原head没有被引用，内存会释放出来
    					circleLink.head.next.prev = nil
    					circleLink.head = circleLink.head.next
    				} else { 
    					// 如果队首之后没有节点了，那么直接首位都置空
    					circleLink.head = nil
    					circleLink.tail = nil
    				}
    			} else { 
    				// 命中的节点在队中间,则取出命中的节点，并维护好其前后指向关系
    				curNode.prev.next = curNode.next
    				curNode.next.prev = curNode.prev
    			}
    			return selectNode, nil
    		}
    		curNode = curNode.prev
    	}
    	if !flag { 
    		// 如果循环结束还没有查找到，输出信息
    		return nil, errors.New("node not found")
    	}
    	return
    }
    
    func (circleLink *CircleLink) getLength() (number int) { 
    	curNode := circleLink.tail
    	if circleLink.tail.id == 0 || circleLink.tail == nil { 
    		// 空链表
    		return
    	} else { 
    		for { 
    			number += 1
    			curNode = curNode.prev
    			if curNode == nil { 
    				break
    			}
    		}
    	}
    	fmt.Println("current link length:", number)
    	return number
    }
    
    func (circleLink *CircleLink) list() { 
    	if circleLink.tail == nil || circleLink.tail.id == 0 { 
    		fmt.Println("link is empty")
    	} else { 
    		curNode := circleLink.tail
    		var nodes []*Node
    		for { 
    			if curNode == nil { 
    				break
    			}
    			//fmt.Print("<==", *curNode)
    			// 从尾部到首部的循环，为了展示链接效果，将节点先加入一个slice中，稍后从slice的后面开始循环展示数据.此时slice是从尾部到首部排序的
    			nodes = append(nodes, curNode)
    			curNode = curNode.prev
    		}
    		for i := 0; i < len(nodes); i++ { 
    			index := len(nodes) - i - 1 // 颠倒一下顺序，现在slice中的顺序和链表顺序恰好是相反的，为了打印的效果，让前面的节点先输出
    			fmt.Print("<==>", nodes[index])
    		}
    	}
    
    	fmt.Println()
    
    }
    
    func main() { 
    	// 约定空链表的header初始id为0，后面加入的实例id必须大于0
    	var originalHead = Node{ 
    		id: 0,
    	}
    	var s = CircleLink{ 
    		head: &originalHead,
    	}
    	var node1 = Node{ 
    		id:   1,
    		name: "001",
    	}
    	var node2 = Node{ 
    		id:   2,
    		name: "002",
    	}
    	var node3 = Node{ 
    		id:   3,
    		name: "003",
    	}
    	var node4 = Node{ 
    		id:   4,
    		name: "004",
    	}
    	var node5 = Node{ 
    		id:   5,
    		name: "005",
    	}
    
    	s.orderInsert(&node4)
    	s.list()
    	s.orderInsert(&node2)
    	s.list()
    	s.orderInsert(&node3)
    	s.list()
    	s.orderInsert(&node5)
    	s.list()
    	s.orderInsert(&node1)
    	s.list()
    	s.getLength()
    	popNode, err := s.pop(3)
    	if err != nil { 
    		fmt.Println(err)
    	}
    	fmt.Println("pop node successfully:", *popNode)
    	s.list()
    
    	/* output: <==&{4 004 <nil> <nil>} <==&{2 002 0xc0000761e0 <nil>}<==&{4 004 <nil> 0xc000076180} <==&{2 002 0xc0000761b0 <nil>}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 <nil> 0xc0000761b0} <==&{2 002 0xc0000761b0 <nil>}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 0xc000076210 0xc0000761b0}<==&{5 005 <nil> 0xc0000761e0} <==&{1 001 0xc000076180 <nil>}<==&{2 002 0xc0000761b0 0xc000076150}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 0xc000076210 0xc0000761b0}<==&{5 005 <nil> 0xc0000761e0} current link length: 5 pop node successfully: {3 003 0xc0000761e0 0xc000076180} <==&{1 001 0xc000076180 <nil>}<==&{2 002 0xc0000761e0 0xc000076150}<==&{4 004 0xc000076210 0xc000076180}<==&{5 005 <nil> 0xc0000761e0} */
    }

**问题**  
从尾部开始查询的操作复杂度依旧与首部开始一样，为O(n)，有没有办法降低复杂度？当然可以，按照自定义链节点串联规则，完全可以使用二分等其他查找的方法降低复杂度，这个后面再补充

### 环形链表 ###

直接以约瑟夫问题，又称丢手帕游戏举例，此场景非常适用于使用环形链表模型，游戏规则见代码顶部注释  
代码：

package main
    
    import (
    	"fmt"
    	"math/rand"
    )
    
    /* 约瑟夫问题，又叫丢手帕游戏，若干人围成一圈，从头开始，每次递进若干位随机数，然后出列一人，接着再从出列者的下一位开始继续循环， 直到圈内只剩最后一人,游戏结束 */
    
    type Child struct { 
    	Id   int
    	next *Child
    }
    
    type Ring struct { 
    	Head *Child
    	Tail *Child
    }
    
    func (ring *Ring) list() { 
    	curChild := ring.Head
    	for { 
    		fmt.Printf("child %d ==>\t", curChild.Id)
    		if curChild.next == ring.Head { 
    			break
    		}
    		curChild = curChild.next
    	}
    	fmt.Println()
    }
    
    func (ring *Ring) play() { 
    	// 开始转圈,第一次是从头开始
    	startIndex := 1
    	n := 0
    	startChild := ring.Head
    	for { 
    		if startChild.next == startChild { 
    			fmt.Printf("游戏结束，圈圈中的最后一位child是%d号\n", startChild.Id)
    			break
    		}
    		n += 1
    		randInt := rand.Intn(10)
    		curChild := startChild
    		for i := 0; i < randInt-1; i++ { 
    			// 在出列child的前一位停下，因为是链表关系，所以需要维护好出列child的前一位的指向关系
    			curChild = curChild.next
    		}
    		chooseChild := curChild.next
    		if chooseChild == ring.Head { 
    			ring.Head = chooseChild.next
    		}
    		curChild.next = chooseChild.next // chooseChild的指针取消，chooseChild会被回收，出列
    		fmt.Printf("第%d轮,从第%d号开始,前进%d位,出列的是%d号child,game continue!\n", n, startIndex, randInt, chooseChild.Id)
    		startIndex = (randInt + startIndex + 1) % 20
    		startChild = chooseChild.next // 下一轮，从chooseChild.next节点开始
    	}
    
    }
    
    func ringInit(number int) (ring Ring) { 
    	// 构建一个指定成员数量的环形链表
    	for i := 1; i <= number; i++ { 
    		var child = Child{ 
    			Id: i,
    		}
    		fmt.Println(child)
    		if i == 1 { 
    			// 插入第一个节点
    			ring.Head = &child
    			ring.Tail = &child
    			ring.Tail.next = ring.Head // 尾节点下一个指针指向首节点
    		} else { 
    			// 后面的节点，陆续成为新的尾结点
    			child.next = ring.Head
    			ring.Tail.next = &child
    			ring.Tail = &child
    		}
    	}
    	return
    }
    
    func main() { 
    	ring := ringInit(20)
    	fmt.Println(*ring.Head, *ring.Tail)
    	ring.list()
    	ring.play()
    }
    /* output: 第1轮,从第1号开始,前进1位,出列的是2号child,game continue! 第2轮,从第3号开始,前进7位,出列的是10号child,game continue! 第3轮,从第11号开始,前进7位,出列的是18号child,game continue! 第4轮,从第19号开始,前进9位,出列的是9号child,game continue! 第5轮,从第9号开始,前进1位,出列的是12号child,game continue! 第6轮,从第11号开始,前进8位,出列的是3号child,game continue! 第7轮,从第0号开始,前进5位,出列的是11号child,game continue! 第8轮,从第6号开始,前进0位,出列的是14号child,game continue! 第9轮,从第7号开始,前进6位,出列的是4号child,game continue! 第10轮,从第14号开始,前进0位,出列的是6号child,game continue! 第11轮,从第15号开始,前进4位,出列的是16号child,game continue! 第12轮,从第0号开始,前进1位,出列的是19号child,game continue! 第13轮,从第2号开始,前进2位,出列的是5号child,game continue! 第14轮,从第5号开始,前进9位,出列的是13号child,game continue! 第15轮,从第15号开始,前进8位,出列的是20号child,game continue! 第16轮,从第4号开始,前进4位,出列的是17号child,game continue! 第17轮,从第9号开始,前进1位,出列的是7号child,game continue! 第18轮,从第11号开始,前进5位,出列的是1号child,game continue! 第19轮,从第17号开始,前进7位,出列的是15号child,game continue! 游戏结束，圈圈中的最后一位child是8号 */