학습 노트 - 03 선형 표 의 순환 링크 (golang 실현)

24587 단어 데이터 구조
순환 링크
머리말
일반적인 단일 체인 표 는 뚜렷 한 단점 이 있 는데 처음부터 출발점 을 출발 하지 않 으 면 모든 노드 에 접근 할 수 없다.
정의. , , , 。
싱글 체인 시트 와 의 차이
사실 순환 체인 테이블 과 단일 체인 테이블 의 주요 차 이 는 순환 의 판단 조건 에 있다. 원래는 p - > next 가 비어 있 는 지 판단 하 는 것 이 었 는데 지금 은 p - > next 가 두 결점 과 같은 지 판단 하 는 것 이다.
코드 구현
package CricleLinkling

import "fmt"

//      
type CricleLinkNode struct {
	value interface{}
	pNext *CricleLinkNode
}

//     
func NewCricleLinkNode(data interface{}) *CricleLinkNode {
	return &CricleLinkNode{
		value: data,
		pNext: nil,
	}
}

//     
func (node *CricleLinkNode) Value() interface{} {
	return node.value
}

//        
func (node *CricleLinkNode) PNext() *CricleLinkNode {
	return node.pNext
}

//         
type CricleLink interface {

	//          
	GetFirstNode() *CricleLinkNode

	//     (   )
	InsertNodeFront(node *CricleLinkNode)

	//     (   )
	InsertNodeBack(node *CricleLinkNode)

	//       
	InsertNodeValueFront(dest interface{}, node *CricleLinkNode) bool

	//       
	InsertNodeValueBack(dest interface{}, node *CricleLinkNode) bool

	//           
	GetNodeAtIndex(index int) *CricleLinkNode

	//     
	DeleteNode(dest *CricleLinkNode) bool

	//           
	DeleteAtIndex(index int) bool

	//      
	String() string
}

//     
type CricleLinkList struct {

	//    
	head *CricleLinkNode

	//   
	length int
}

//        
func NewCricleLinkList() *CricleLinkList {

	//       
	head := NewCricleLinkNode(nil)

	return &CricleLinkList{
		head:   head,
		length: 0,
	}
}

//          
func (list *CricleLinkList) GetFirstNode() *CricleLinkNode {
	return list.head.pNext
}

//           
func (list *CricleLinkList) GetNodeAtIndex(index int) *CricleLinkNode {

	//     
	if index > list.length-1 || index < 0 {
		return nil
	}

	//      
	bak := list.head

	//     
	for index > -1 {
		bak = bak.pNext
		index--
	}

	return bak
}

//     
func (list *CricleLinkList) InsertNodeFront(node *CricleLinkNode) {

	//      
	bak := list.head

	//    
	if bak.pNext == nil {

		//              
		bak.pNext = node

		//            
		node.pNext = bak
		list.length++
		return
	}

	//       ,            
	node.pNext = bak.pNext

	//         
	bak.pNext = node

	list.length++
	return
}

//     
func (list *CricleLinkList) InsertNodeBack(node *CricleLinkNode) {

	//      
	bak := list.head
	bak2 := list.head

	//    
	if bak.pNext == nil {

		//              
		bak.pNext = node

		//            
		node.pNext = bak

		list.length++
		return
	}

	//        
	for bak.pNext != list.head {
		bak = bak.pNext
	}

	//             
	bak.pNext = node

	//            
	node.pNext = bak2

	list.length++
	return
}

//       
func (list *CricleLinkList) InsertNodeValueFront(dest interface{}, node *CricleLinkNode) bool {

	//      
	bak := list.head

	//      ,        
	for bak.pNext != bak && bak.pNext.value != dest {
		bak = bak.pNext
	}

	//   
	if bak.pNext.value == dest {

		//                ,         
		node.pNext = bak.pNext

		//                ,     
		bak.pNext = node

		list.length++
		return true
	}

	return false

}

//       
func (list *CricleLinkList) InsertNodeValueBack(dest interface{}, node *CricleLinkNode) bool {

	//      
	bak := list.head

	//      ,        
	for bak.pNext != bak && bak.pNext.value != dest {
		bak = bak.pNext
	}

	//   
	if bak.pNext.value == dest {

		//                 
		node.pNext = bak.pNext.pNext

		//             
		bak.pNext.pNext = node

		list.length++
		return true
	}

	return false

}

//     
func (list *CricleLinkList) DeleteNode(dest *CricleLinkNode) bool {

	//      
	bak := list.head

	//     
	if dest == nil {
		return false
	}

	//      ,        
	for bak.pNext != bak && bak.pNext != dest {
		bak = bak.pNext
	}

	//   
	if bak.pNext == dest {

		//                          
		bak.pNext = bak.pNext.pNext

		list.length--
		return true
	}

	return false
}

//           
func (list *CricleLinkList) DeleteAtIndex(index int) bool {

	//     
	if index > list.length-1 || index < 0 {
		return false
	}

	//      
	bak := list.head

	//     ,       
	for index > 0 {
		bak = bak.pNext
		index--
	}

	//                          
	bak.pNext = bak.pNext.pNext
	list.length--

	return true
}

//      
func (list *CricleLinkList) String() string {

	var listString string

	//    
	p := list.head

	//     
	for p.pNext != list.head {
		listString += fmt.Sprintf("%v-->", p.pNext.value)
		p = p.pNext
	}

	listString += fmt.Sprintf("nil")

	return listString
}


좋은 웹페이지 즐겨찾기