算法：golang实现无头单向非循环链表

淡淡的烟草味﹌ 2022-09-08 11:47 114阅读 0赞

![在这里插入图片描述][4d14c2319b02439dbf24a0a4e4656718.png]

package main
    
    import "fmt"
    
    type SingleListInterface interface {
        
    	Empty() bool
    	Size()  int
    	Clear()
    	Exist_data(data interface{
        }) bool
    	Push_back(data interface{
        })
    	Push_front(data interface{
        })
    	Search_index(pos int)(data interface{
        }, err error)
    	Insert(pos int, data interface{
        }) (err error)
    	Pop_back() (data interface{
        }, err error)
    	Pop_front() (data interface{
        }, err error)
    	Remove_index(pos int)(data interface{
        }, err error)
    	Reversel()
    	String()
    }
    
    
    
    
    
    type Node struct {
        
    	data interface{
        }
    	next *Node
    }
    
    func NewNode(data interface{
        }) *Node  {
        
    	return &Node{
        
    		data: data,
    		next: nil,
    	}
    }
    
    
    type SingleList struct {
        
    	head *Node
    	tail *Node
    	cnt int
    }
    
    func NewSingleList() *SingleList   {
        
    	return &SingleList{
        
    		head: nil,
    		tail: nil,
    		cnt: 0,
    	}
    }
    
    
    func (s *SingleList)Empty() bool{
        
    	return s.cnt == 0
    }
    func (s *SingleList)Size()  int{
        
    	return s.cnt
    }
    func (s *SingleList)Clear(){
        
    	s.head = nil
    	s.tail = nil
    	s.cnt = 0
    }
    func (s *SingleList)Push_back(data interface{
        }){
        
    	// 0. 判断值有效
    	if data == nil {
        
    		return
    	}
    
    	// 1. 生成节点
    	node := NewNode(data)
    
    	// 2. 插入尾部
    	if s.tail == nil {
        
    		s.tail = node
    		s.head = node
    	}else{
        
    		s.tail.next = node
    		s.tail = node
    	}
    
    	s.cnt++
    }
    func (s *SingleList)Push_front(data interface{
        }){
        
    	// 0. 判断值有效
    	if data == nil {
        
    		return
    	}
    
    	// 1. 生成节点
    	node := NewNode(data)
    
    	// 2. 插入头部
    	if s.head == nil {
        
    		s.head = node
    		s.tail = node
    	}else{
        
    		node.next = s.head
    		s.head = node
    	}
    
    	s.cnt++
    }
    
    func (s *SingleList)search_index(pos int) (node *Node, err error){
        
    	// 1. 判断值是否有效
    	if pos < 0 || pos > s.cnt - 1 {
        
    		return nil, fmt.Errorf("超出索引范围");
    	}
    	// 2. 查找
    	i := 0
    	curr := s.head
    	for {
        
    		if i == pos {
        
    			break
    		}
    		i++
    		curr = curr.next
    	}
    
    	return curr, nil
    }
    
    func (s *SingleList)Insert(pos int, data interface{
        }) (err error){
        
    	// 1. 判断值是否有效
    	if data == nil {
        
    		return fmt.Errorf("data is nil")
    	}
    
    	// 2. 处理特例
    	if pos == 0 {
        
    		s.Push_front(data)
    		return
    	}
    
    	if pos == s.cnt {
        
    		s.Push_back(data)
    		return
    	}
    
    	// 3. 找到当前位置的前一个节点
    	prenode, err := s.search_index(pos - 1);
    	if err != nil {
        
    		return err
    	}
    
    	// 生成节点
    	node := NewNode(data)
    	node.next = prenode.next
    	prenode.next = node
    	s.cnt++
    
    	return nil
    }
    func (s *SingleList)Pop_back() (data interface{
        }, err error){
        
    	// 1. 找到待删除节点的前一个节点
    	preNode, err := s.search_index(s.cnt - 2)
    	if err != nil {
        
    		return nil,  fmt.Errorf("linked is empty")
    	}
    
    	//2. 删除节点
    	data = s.tail.data
    
    	s.tail = preNode
    	preNode.next = nil
    	s.cnt--
    
    	return data, nil
    }
    
    
    func (s *SingleList)Pop_front() (data interface{
        }, err error){
        
    	if s.Empty() {
        
    		return nil,  fmt.Errorf("linked is empty")
    	}
    
    	data  = s.head.data
    
    	s.head = s.head.next   // 头指针向下移动
    	s.cnt--
    
    	return data, nil
    }
    
    
    func (s *SingleList)Remove_index(pos int)(interface{
        }, error){
        
    	if pos == 0 {
        
    		return s.Pop_front()
    	}
    
    	if pos == s.cnt - 1 {
        
    		return s.Pop_back()
    	}
    
    	pre, err := s.search_index(pos - 1)
    	if err != nil {
        
    		return nil, err
    	}
    
    	data := pre.next.data
    	pre.next = pre.next.next
    	s.cnt--
    
    	return data, nil
    }
    
    
    func (s *SingleList)Reversel(){
        
    	if s.Empty() || s.Size() == 1 {
        
    		return
    	}
    
    	pre :=  s.head
    	curr := pre.next
    	fur :=  curr.next
    
    	s.tail = pre
    
    
    	pre.next = nil
    	for curr != nil{
        
    		curr.next = pre   // 指向前驱
    
    		pre = curr     // pre是不要了的
    		curr = fur
    		if fur != nil {
           //fur不是最后一个节点
    			fur = fur.next
    		}
    	}
    
    	s.head = pre
    }
    func (s *SingleList)String(){
        
    	curr := s.head
    
    
    	for curr != nil{
        
    		fmt.Print(curr.data, " ")
    		curr = curr.next
    	}
    	fmt.Println()
    
    	return
    }
    
    
    func (s *SingleList)Exist_data(data interface{
        }) bool{
        
    	if data == nil || s.Empty() {
        
    		return false
    	}
    
    	curr := s.head
    
    	for curr != nil{
        
    		if curr.data == data {
        
    			return true
    		}
    		curr = curr.next
    	}
    
    	return false
    }
    
    
    
    func main(){
        
    	singlelist := NewSingleList();
    
    	for  i := 0; i < 20; i++{
        
    		singlelist.Push_back(i)
    	}
    	for  i := 0; i < 20; i++{
        
    		singlelist.Push_front(i)
    	}
    
    	fmt.Println(singlelist.Size())
    
    
    	singlelist.Reversel()
    
    	_, _ = singlelist.Pop_back()
    	_, _ = singlelist.Pop_front()
    
    	singlelist.String()
    
    	fmt.Println(singlelist.Size())
    
    	singlelist.Remove_index(3)
    	singlelist.String()
    
    	fmt.Println(singlelist.Size())
    
    	fmt.Println(singlelist.Exist_data(12))
    
    	singlelist.Clear()
    
    	fmt.Println(singlelist.Size())
    
    	singlelist.String()
    	fmt.Println(singlelist.Exist_data(12))
    
    }

[4d14c2319b02439dbf24a0a4e4656718.png]: /images/20220829/51d17534a29a4ba2a1e07f5548a6aa20.png