Golang 표준 라 이브 러 리 학습 - container / list

container 패키지 에는 세 가지 데이터 구조 가 있 습 니 다. hep (더미), list (링크), ring (링)
Package list
import "container/list"
list 패 키 지 는 양 방향 링크 를 실 현 했 습 니 다. 링크 를 옮 겨 다 녀 야 합 니 다.

for e := l.Front(); e != nil; e = e.Next() {
	// do something with e.Value
}

type Element
Element 는 링크 노드 를 대표 합 니 다.

type Element struct {
	next, prev *Element    // next, prev              
	list *List             // list        
	Value interface{}      // Value          
}

Next 와 Prev 방법

// Next           nil
func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

// Prev           nil
func (e *Element) Prev() *Element {
	if p := e.prev; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

type List
List 는 양 방향 링크 를 대표 합 니 다.List 0 값 은 비어 있 고 사용 가능 한 링크 입 니 다.

type List struct {
	root Element // root       
	len  int     // len  List  ，  root
}

List 는 세 가지 기본 방법 이 있어 요.

//          
func New() *List {
	return new(List).Init()
}

//     
func (l *List) Init() *List {
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}

//       
func (l *List) Len() int {
	return l.len 
}

list 에 포 함 된 방법 은 다음 과 같 습 니 다.
링크 기능 의 기본 실현

//     
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}
//  list     
func (l *List) Front() *Element {}
//  list     
func (l *List) Back() *Element {}
//     v              ，        
func (l *List) PushFront(v interface{}) *Element {}                   
//    other   ，              list      
func (l *List) PushFrontList(other *List) {}
//     v              ，                             
func (l *List) PushBack(v interface{}) *Element {}
//    other   ，             list       
func (l *List) PushBackList(other *List) {}
//     v       mark  ，         。  mark  l   ，l     
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {}
//     v       mark  ，         。  mark  l   ，l     
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {}
//   e           ，  e  l   ，l     
func (l *List) MoveToFront(e *Element) {}
//   e            ，  e  l   ，l     
func (l *List) MoveToBack(e *Element) {}
//   e   mark   。  e mark  l   ，  e==mark，l     
func (l *List) MoveBefore(e, mark *Element) {}
//   e   mark   。  e mark  l   ，  e==mark，l     
func (l *List) MoveAfter(e, mark *Element) {}
//        e，   e.Value
func (l *List) Remove(e *Element) interface{} {}

container / list 표준 라 이브 러 리 에서 코드 가 교묘 하 게 이 루어 집 니 다. 초기 화 지연, 패 키 징 디자인 등 기 교 를 포함 하여 소 백 (like me) 에 좋 은 참고 가치 가 있 습 니 다.
여기 서 몇 개의 단편 을 떼 어 냈 다.
Remove 는 내부 remove 에 대한 패 키 징 을 실현 하 였 습 니 다.

func (l *List) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
	return e
}

func (l *List) Remove(e *Element) interface{} {
	if e.list == l {
		l.remove(e)
	}
	return e.Value
}

MoveBefore 와 PushBackList 는 모두 기본 동작 에 대한 호출 입 니 다.

func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.insert(l.remove(e), mark.prev)
}

func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}

list 패키지 사용 예시
그 중 몇 가지 대표 적 인 방법 을 사용 하 다

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	l.PushFront(1)                // 1
	l.PushBack(2)                 // 1->2
	fmt.Println(l.Front().Value)  // 1
	fmt.Println(l.Back().Value)   // 2
	other := list.New()
	other.PushFront(3)
	other.PushBack(4)
	l.PushFrontList(other)        // 3->4->1->2
	fmt.Println(l.Front().Value)
	fmt.Println(l.Back().Value)
	fmt.Println(l.Len())
	l.Remove(l.Front().Next())    // 3->1->2
	fmt.Println(l.Len())
	for v := l.Front(); v != nil; v = v.Next() {
		fmt.Printf("%d ", v.Value)
	}
	fmt.Printf("
")
}