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

我会带着你远行 2022-09-09 09:27 240阅读 0赞

代码片段如下：

/*
     *                    .::::.
     *                  .::::::::.
     *                 :::::::::::
     *             ..:::::::::::'
     *           '::::::::::::'
     *             .::::::::::
     *        '::::::::::::::..
     *             ..::::::::::::.		Utils:双链表
     *           ``::::::::::::::::		Author:崔金朋
     *            ::::``:::::::::'        .:::.
     *           ::::'   ':::::'       .::::::::.
     *         .::::'      ::::     .:::::::'::::.
     *        .:::'       :::::  .:::::::::' ':::::.
     *       .::'        :::::.:::::::::'      ':::::.
     *      .::'         ::::::::::::::'         ``::::.
     *  ...:::           ::::::::::::'              ``::.
     * ```` ':.          ':::::::::'                  ::::..
     *  		           '.:::::'          			':'````..
     */
    
    package main
    
    import (
    	"fmt"
    	"sync"
    )
    
    type DoubleNode struct {
    	Value interface{}
    	Prev  *DoubleNode
    	Next  *DoubleNode
    }
    
    type DoubleLinkedList struct {
    	mutex *sync.RWMutex
    	Size  int
    	Head  *DoubleNode
    	Tail  *DoubleNode
    }
    
    // 创建空的双链表
    func CreateDoubleLinkedList() *DoubleLinkedList {
    	return &DoubleLinkedList{new(sync.RWMutex), 0, nil, nil}
    }
    
    // 根据指定的位置索引，查询出节点内容
    func (list *DoubleLinkedList) SearchDoubleListNode(i int) *DoubleNode {
    	if list.Size == 0 || i > list.Size {
    		return nil
    	}
    
    	if i == 0 {
    		return list.Head
    	}
    
    	node := list.Head
    	for count := 1; count < i; count++ {
    		node = node.Next
    	}
    
    	return node
    }
    
    // 链表后面追加节点
    func (list *DoubleLinkedList) AppendDoubleListNode(node *DoubleNode) bool {
    	if node == nil {
    		return false
    	}
    
    	list.mutex.Lock()
    	defer list.mutex.Unlock()
    
    	if list.Size == 0 {
    		list.Head = node
    		list.Tail = node
    		node.Next = nil
    		node.Prev = nil
    	} else {
    		node.Prev = list.Tail
    		node.Next = nil
    		list.Tail.Next = node
    		list.Tail = node
    	}
    
    	list.Size++
    	return true
    }
    
    // 指定位置插入节点
    func (list *DoubleLinkedList) InsertDoubleListNode(i int, node *DoubleNode) bool {
    	if node == nil || i > list.Size || i == 0 {
    		return false
    	}
    
    	if i == list.Size {
    		return list.AppendDoubleListNode(node)
    	}
    
    	list.mutex.Lock()
    	defer list.mutex.Unlock()
    
    	if i == 1 {
    		node.Next = list.Head
    		list.Head = node
    		list.Head.Prev = nil
    		list.Size++
    		return true
    	}
    
    	nextNode := list.SearchDoubleListNode(i)
    	node.Prev = nextNode.Prev
    	node.Next = nextNode
    	nextNode.Prev.Next = node
    	nextNode.Prev = node
    	list.Size++
    	return true
    }
    
    // 删除指定的位置的节点
    func (list *DoubleLinkedList) DeleteDoubleListNode(i int) bool {
    	if i > list.Size-1 || i == 0 {
    		return false
    	}
    
    	list.mutex.Lock()
    	defer list.mutex.Unlock()
    
    	if i == 1 {
    		if list.Size == 1 {
    			list.Head = nil
    			list.Tail = nil
    		} else {
    			list.Head.Next.Prev = nil
    			list.Head = list.Head.Next
    		}
    
    		list.Size--
    		return true
    	}
    
    	if i == list.Size-1 {
    		list.Tail.Prev.Next = nil
    		list.Tail = list.Tail.Prev
    		list.Size--
    		return true
    	}
    
    	node := list.SearchDoubleListNode(i)
    	node.Prev.Next = node.Next
    	node.Next.Prev = node.Prev
    	list.Size--
    	return true
    }
    
    // 打印链表
    func (list *DoubleLinkedList) PrintlnDoubleListNode() {
    	if list == nil || list.Size == 0 {
    		fmt.Println("this double list is null or empty")
    		return
    	}
    
    	list.mutex.Lock()
    	defer list.mutex.Unlock()
    
    	fmt.Println("this double list size is: ", list.Size)
    	ptr := list.Head
    	for ptr != nil {
    		fmt.Println("data is: ", ptr.Value)
    		ptr = ptr.Next
    	}
    }
    
    // 倒序打印链表
    func (list *DoubleLinkedList) ReversePrintlnDoubleListNode() {
    	if list == nil || list.Size == 0 {
    		fmt.Println("this double list is null or empty")
    		return
    	}
    
    	list.mutex.Lock()
    	defer list.mutex.Unlock()
    
    	fmt.Println("this double list size is: ", list.Size)
    	ptr := list.Tail
    	for ptr != nil {
    		fmt.Println("data is: ", ptr.Value)
    		ptr = ptr.Prev
    	}
    }