[Go] 표준 라이브러리 container/list 코드 분석

최근 golang을 보고 있는데 꽤나 재밌는 내용이 있어서 정리해두고자 한다. 

 

golang에는 표준 라이브러리로 list를 제공한다. 그런데 재밌게도 ring구조를 채택하고 있고, 이를 통해 더미 노드를 하나 만들어서 첫번째 노드의 prev노드로 사용하고, 마지막 노드의 next노드로써 사용한다.

이렇게 함으로써 경계값 검사가 쉬워진다는 장점이 있다고 한다. 

 

분석하면서 개인적으로 주석을 달아놓았는데 한번쯤 재밌게 읽을법한 코드라서 아래 첨부한다. 

 

 

출처:

golang에서 기본적으로 제공하는 container/list 

 

 

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package list implements a doubly linked list.
//
// To iterate over a list (where l is a *List):
//
//	for e := l.Front(); e != nil; e = e.Next() {
//		// do something with e.Value
//	}
package list

/*
	NOTE
	- element는 list의 기본 요소인듯
	 재밌는건 Element라는 요소가 List 타입 구조체의 요소임에도
	 어느 List에 속한지 알기 위해 *List를 타입으로 가진 필드가 있다는점...

	 그리고 재미난건...
	 구현을 쉽게 하기 위해 내부적으로 list를 ring으로 구현했다고 한다.
	 마지막 요소의 Next는 첫 요소인 root이고, 첫 요소인 root의 이전 요소가 마지막 요소인것 처럼 말이다.
	 -> 이게 구현을 쉽게하나 ?
*/

// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value any
}

/*
	NOTE
	Next()를 사용할때 실제로 내부에서는 모체인 List가 nil이 아닌지를 검사한다.
	재밌는건 여기서 실제 list구현이 ring구조를 따른다는걸 알 수 있다.
	왜냐면 조건에 p != &e.list.root가 있다. 즉 다음 요소인 Next가 root요소라는 점은
	지금 보는 곳이 마지막이라는 점이니까 Next()가 없어야한다. 그러니까 != 라는 조건을
	p != &e.list.root에 붙인거고...
	이 점은 흥미롭네요

*/

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

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

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}

/*
	NOTE
	- Init()을 잘 보면 root라는 Element가 있음에도 길이는 0으로 잡는다
	즉 root Element는 counting되지 않으므로 더미노드다.

*/

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

// New returns an initialized list.
func New() *List { return new(List).Init() }

// Len returns the number of elements of list l.
// The complexity is O(1).
func (l *List) Len() int { return l.len }

/*
	NOTE
	여기를 보면 좀 더 명확해지지.(root가 더미노드라는 점이..)
	Front는 List의 맨 앞의 Element를 가져와야한다. 그런데 여기보면
	l.root.next를 가져오지? 그러니까 root의 다음이 첫 요소라는 거야.

*/

// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}

/*
	NOTE
	여기도 보면 마찬가지고, 가장 마지막 요소를 반환하는데 root의 이전 요소를 반환하고 있다.

*/

// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

/*
	NOTE 얘는 뭘까요 ?
	-> 얘가 있어서 명시적으로 List를 사용할때 l.Init() 코드를 사용자가 선언하지 않고도
	이걸 사용할 수 있는거다. Init()을 하지 않으면 root더미노드가 아예 nil인 상태다.
	그래서 l.root.next가 nil이라는건 root노드가 초기 Init()되지 않았다는 것이므로 여기서 Init한다는 것이다.
*/

// lazyInit lazily initializes a zero List value.
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}

/*
	NOTE
	e의 이전을 at으로 지정해서 at을 e의 앞으로 보내지.
	그리고 at의 Next였던 요소를 e의 Next로 삼는다.
	그리고 at요소에도 수정을 가한다.
	e.prev.next: e의 prev는 at이 되었으니 at의 Next는 이제 e가 되어야한다.
	그리고 e의 next는 기존 at의 next가 되었으니 해당 다음요소의 prev 인 이전 요소가 at이 아니라 e가 되게끔 수정해야한다.
	그리고 e에 List구조체 포인터 타입에 현재 List를 주고. 길이 글리고
	해당 요소 반환한다.
*/

// insert inserts e after at, increments l.len, and returns e.
func (l *List) insert(e, at *Element) *Element {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
func (l *List) insertValue(v any, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

// remove removes e from its list, decrements l.len
func (l *List) remove(e *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--
}

// move moves e to next to at.
func (l *List) move(e, at *Element) {
	if e == at {
		return
	}
	e.prev.next = e.next
	e.next.prev = e.prev

	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
}

/*
	NOTE 
	Remove 메서드를 보다보니 재밌는걸 발견했다. 
	e.list == l이 아니면 그냥 e.Value만 리턴하고 끝난다는걸로 보아하니 
	제대로 Remove되었다고 착각하고 그냥 넘어갈 여지도 있어보인다. 
*/

// Remove removes e from l if e is an element of list l.
// It returns the element value e.Value.
// The element must not be nil.
func (l *List) Remove(e *Element) any {
	if e.list == l {
		// if e.list == l, l must have been initialized when e was inserted
		// in l or l == nil (e is a zero Element) and l.remove will crash
		l.remove(e)
	}
	return e.Value
}

// PushFront inserts a new element e with value v at the front of list l and returns e.
func (l *List) PushFront(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (l *List) PushBack(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertBefore(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark.prev)
}

// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertAfter(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark)
}

// MoveToFront moves element e to the front of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e { 
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, &l.root)
}

// MoveToBack moves element e to the back of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToBack(e *Element) {
	if e.list != l || l.root.prev == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, l.root.prev)
}

// MoveBefore moves element e to its new position before mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark.prev)
}

// MoveAfter moves element e to its new position after mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveAfter(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark)
}

// PushBackList inserts a copy of another list at the back of list l.
// The lists l and other may be the same. They must not be nil.
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)
	}
}

// PushFrontList inserts a copy of another list at the front of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}

 

 

위 코드를 보면 알겠지만 재밌는 내용이 하나 있다. 

 

Remove메서드에서 개발자로 하여금 착각할 만한 여지가 존재한다. 

 

Remove에 실패하든 성공하든 두 경우 모두 내가 지우려고 한 요소를 리턴해준다.

실제로 아래 코드로 테스트해보면 삭제에 실패해야하는 케이스임에도 불구하고 삭제 동작 시 출력문에는 삭제하려는 요소에 대한 출력이 성공적으로 이뤄진다. 

 

개인적으로 이 부분을 보면서 착각해서 잘못된 코드를 짤 여지가 있는 부분이라고 생각되었다. 삭제가 성공했는지 알려면 추가 코드가 필요하다. 그리고 이 점을 모른다면 Remove를 하고나서 해당 리턴값이 있으므로 본인은 이 동작이 성공했다고 보고 이후 코드에서 오동작을 하는 것이다. 

 

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l1 := list.New()
	l1.PushBack(1)
	l1.PushBack(2)
	l1.PushBack(3)
	l1.PushBack(4)

	l2 := list.New()
	l2.PushBack(1)
	l2.PushBack(2)
	l2.PushBack(3)
	l2.PushBack(4)

	fmt.Println()
	for e := l1.Front(); e != nil; e = e.Next() {
		var removeResult = l2.Remove(e)
		fmt.Println("removeReuslt: ", removeResult)
	}

	printList(l1)
	printList(l2)
}

func printList(l *list.List) {
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()
}

 

 

golang 쪽 코드를 보면 간결하면서도 표현하고자 하는 바가 명확하다는 점이 개인적으로 마음에 든다.

군더더기없이 내가 하고자 하는 일만 코드에 명확하게 나타나는 점이 좋다. 

꽤 재밌게 보고 있다.  

 

언젠가 현업에 사용해보고 싶다.