Go-实现双向循环链表附加基础操作

一时失言乱红尘 2022-09-09 09:26 258阅读 0赞

代码片段如下：

/*
     *                    .::::.
     *                  .::::::::.
     *                 :::::::::::
     *             ..:::::::::::'
     *           '::::::::::::'
     *             .::::::::::
     *        '::::::::::::::..
     *             ..::::::::::::.		Utils:双向循环链表
     *           ``::::::::::::::::		Author:崔金朋
     *            ::::``:::::::::'        .:::.
     *           ::::'   ':::::'       .::::::::.
     *         .::::'      ::::     .:::::::'::::.
     *        .:::'       :::::  .:::::::::' ':::::.
     *       .::'        :::::.:::::::::'      ':::::.
     *      .::'         ::::::::::::::'         ``::::.
     *  ...:::           ::::::::::::'              ``::.
     * ```` ':.          ':::::::::'                  ::::..
     *  		           '.:::::'          			':'````..
     */
    
    package main
    
    import (
    	"fmt"
    	"sync"
    )
    
    type DoubleCircleLinkedList struct {
    	mutex *sync.RWMutex
    	Id    int
    	Value interface{}
    	Prev  *DoubleCircleLinkedList
    	Next  *DoubleCircleLinkedList
    }
    
    // 创建链表
    func CreateDoubleCircleLinkedListNode() *DoubleCircleLinkedList {
    	return &DoubleCircleLinkedList{}
    }
    
    // 追加节点
    func (c *DoubleCircleLinkedList) AppendDoubleCircleLinkedListNode(val interface{}) {
    	if val == nil {
    		return
    	}
    
    	if c.mutex != nil {
    		c.mutex.Lock()
    		defer c.mutex.Unlock()
    	}
    
    	if c.Id == 0 {
    		c.mutex = new(sync.RWMutex)
    		c.Id = 1
    		c.Value = val
    		c.Prev = c
    		c.Next = c
    
    		return
    	}
    
    	currNode := c.Next
    	for {
    		if currNode.Next == c {
    			currNode.Next = &DoubleCircleLinkedList{
    				mutex: new(sync.RWMutex),
    				Id:    currNode.Id + 1,
    				Value: val,
    				Prev:  currNode,
    				Next:  currNode.Next,
    			}
    
    			break
    		}
    
    		currNode = currNode.Next
    	}
    }
    
    // 指定位置插入节点
    func (c *DoubleCircleLinkedList) InsertDoubleCircleLinkedListNode(i int, val interface{}) *DoubleCircleLinkedList {
    	listLength := c.GetDoubleCircleLinkedListLength()
    	if i < 0 || val == nil || listLength+1 < i {
    		return c
    	}
    
    	var key int
    	currNode := c
    	for {
    		key++
    		if key == i-1 {
    			currNode.Next = &DoubleCircleLinkedList{
    				mutex: new(sync.RWMutex),
    				Id:    currNode.Id + 1,
    				Value: val,
    				Prev:  currNode,
    				Next:  currNode.Next,
    			}
    			break
    		}
    
    		if currNode.Next == c {
    			if i == 1 {
    				currNode.Next = &DoubleCircleLinkedList{
    					mutex: new(sync.RWMutex),
    					Id:    listLength + 1,
    					Value: val,
    					Prev:  currNode,
    					Next:  c,
    				}
    
    				currNode = currNode.Next
    			}
    
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	if i == 1 {
    		return currNode
    	}
    
    	return c
    }
    
    // 查询节点位置
    func (c *DoubleCircleLinkedList) SearchDoubleCircleLinkedListNode(i int) *DoubleCircleLinkedList {
    	if i < 1 {
    		return nil
    	}
    
    	if i == 1 {
    		return c
    	}
    
    	var key int
    	currNode := c
    	for {
    		key++
    		if key == i-1 {
    			return currNode.Next
    		}
    
    		if currNode.Next == c {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	return nil
    }
    
    // 指定位置删除节点
    func (c *DoubleCircleLinkedList) DeleteDoubleCircleLinkedListNode(i int) *DoubleCircleLinkedList {
    	listLength := c.GetDoubleCircleLinkedListLength()
    	if i <= 0 || i > listLength {
    		return c
    	}
    
    	if listLength == 1 {
    		return c
    	}
    
    	var key int
    	currNode := c
    	for {
    		key++
    		if key == i-1 {
    			currNode.Prev = currNode.Next
    			currNode.Next = currNode.Next.Next
    			break
    		}
    
    		if currNode.Next == c {
    			if i == 1 {
    				currNode.Prev = currNode
    				currNode.Next = currNode.Next.Next
    				currNode = currNode.Next
    			}
    
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	if i == 1 {
    		return currNode
    	}
    
    	return c
    }
    
    // 打印所有节点
    func (c *DoubleCircleLinkedList) PrintlnDoubleCircleLinkedListNode() {
    	currNode := c
    	for {
    		fmt.Println("circle list value is: ", currNode.Value)
    		if currNode.Next.Id == c.Id {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    }
    
    // 获取环形链表长度
    func (c *DoubleCircleLinkedList) GetDoubleCircleLinkedListLength() int {
    	var key int
    	currNode := c
    	for {
    		key++
    		if currNode.Next == c {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	return key
    }