Go의 단일 체인 테이블

개요

체인 테이블은 선형 정렬을 형성하는 노드의 집합이다.각 노드는 하나의 데이터 필드와 다른 노드를 가리키는 포인터를 저장하는 객체입니다.체인 테이블에는 두 개의 특수 노드가 있습니다.

Head는 목록의 첫 번째 요소를 가리키는 바늘입니다. 목록이 비어 있으면 Head의 값은 0입니다.

끝 부분은 선택 사항이며 마지막 요소를 가리킵니다.우리는 다음 절에서 이 지침의 장점을 볼 것이다.

type Node struct {
    Value   interface{}
    Next    *Node
}

type LinkedList struct {
    Head    *Node
    Tail    *Node
}

조작하다

다음은 체인 테이블에서 실행할 수 있는 몇 가지 조작 예이다.전체 실현은 Github에서 찾을 수 있다.

앞으로 밀다

이 작업은 체인 테이블 앞에 요소를 추가합니다.이를 위해 필요한 값을 가진 새 노드를 생성해야 합니다
다음 포인터를 목록의 현재 제목으로 설정합니다.

다음에 새로 만든 노드를 가리키기 위해 헤더 포인터를 업데이트해야 합니다.

func (l *LinkedList) PushFront(val interface{}) {
    node := &Node{Value: val, Next: l.Head}
    l.Head = node
    if l.Tail == nil {
        l.Tail = l.Head
    }
}

요소를 추가할 때 체인 테이블이 비어 있고 꼬리 바늘을 사용하고 있다면, 새로 만든 노드를 가리키기 위해 꼬리 바늘을 업데이트해야 합니다. (이 예에서 이 노드는 목록의 머리를 대표합니다.)

팝업 전면

링크 목록의 첫 번째 요소를 삭제하려면 먼저 목록이 비어 있는지 확인해야 합니다.
다음 노드를 가리키도록 목록의 머리를 업데이트해야 합니다.머리가 지금 0을 가리키면 목록이 비어 있고 끝부분을 업데이트해야 합니다.

func (l *LinkedList) PopFront() error {
    if l.Head == nil {
        return errors.New("can't remove from empty list")
    }
    l.Head = l.Head.Next
    if l.Head == nil {
        l.Tail = nil
    }
    return nil
}

되돌리다

목록의 끝에 원소를 추가하는 것은 매우 비싸다. 왜냐하면 전체 목록을 두루 훑어봐야 마지막 원소를 찾을 수 있기 때문이다.모든 노드는 다음 노드를 가리키는 지침이 있어 처음부터 끝까지 훑어볼 수 있지만 거꾸로 훑어볼 수는 없다.
따라서 목록의 끝에 도달하려면 모든 노드를 교체해야 합니다.
꼬리가 구조를 가리키기 때문에 이런 조작 방식이 더욱 싸다.

func (l *LinkedList) PushBack(val interface{}) {
    node := &Node{Value: val, Next: nil}
    if l.Tail == nil {
        l.Head = node
        l.Tail = node
    } else {
        l.Tail.Next = node
        l.Tail = node
    }
}

필요한 값을 사용하여 새 노드를 만들고 다음 바늘을nil로 설정합니다.목록이 비어 있으면 머리와 꼬리를 업데이트하여 생성된 노드를 가리킵니다.

그렇지 않으면 현재 꼬리의 다음 포인터를 새 노드로 업데이트한 다음 꼬리 포인터 자체를 업데이트합니다.

튕기다

Pop Front 작업과 유사합니다. 목록이 비어 있는지 확인해야 합니다. 그렇지 않으면 오류가 발생합니다.
다음에 목록에 원소가 하나밖에 없으면head와tail을 모두nil로 설정합니다. 열이 비어 있기 때문입니다.

func (l *LinkedList) PopBack() error {
    if l.Head == nil {
        return errors.New("can't remove from empty list")
    }
    if l.Head.Value == l.Tail.Value {
        l.Head = nil
        l.Tail = nil
        return nil
    }
    currentHead := l.Head
    for currentHead.Next.Next != nil {
        currentHead = currentHead.Next
    }
    l.Tail = currentHead
    currentHead.Next = nil
    return nil
}

여기는 더욱 복잡해졌다. 왜냐하면 너는 반드시 꼴찌의 두 번째 요소를 찾아야 하기 때문이다. 앞에서 언급한 바와 같이 단일 링크 목록에서 두루 돌아다닐 수 없기 때문이다.

따라서 두 번째 요소를 찾을 때까지 목록을 처음부터 반복해야 합니다.찾으면 마지막 요소를 가리키기 위해 끝부분을 업데이트합니다. (마지막 요소를 제거합니다.)
마지막으로 현재 마지막 요소의 다음 바늘을nil로 설정합니다.

나중에 추가

이 작업은 다른 주어진 노드 다음에 새 노드를 삽입합니다.
따라서 필요한 값을 사용하여 새 노드를 만들고 다음 포인터를 지정된 노드에 현재 지향하는 노드로 설정할 수 있습니다.
새 노드를 가리키기 위해 지정된 노드를 업데이트합니다.주어진 노드가 꼬리 요소일 경우, 새 노드를 가리키기 위해 꼬리를 업데이트합니다.

func (l *LinkedList) AddAfter(node *Node, val interface{}) {
    newNode := &Node{Value: val, Next: node.Next}
    node.Next = newNode
    if l.Tail.Value == node.Value {
        l.Tail = newNode
    }
}

이전에 추가

이 조작은 가장 복잡하다. 왜냐하면, 당신은 반드시 머리에서 목록을 순환해야만 주어진 노드 이전의 요소에 도달할 수 있기 때문이다.
먼저 목록이 비어 있거나 지정된 노드가 목록의 첫 번째 요소인 경우 Push Front 작업을 반복하여 노드를 목록의 시작으로 삽입할 수 있습니다.

그렇지 않으면 지정된 노드의 이전 요소를 찾을 때까지 목록을 반복해야 합니다.순환 중, 이 두 노드 사이에 새 노드를 삽입해야 하기 때문에 이전 노드와 현재 노드를 추적합니다.
정확한 삽입 위치가 있을 때, 현재 노드가 0인지 확인하고, 두 노드 사이에 새 노드를 삽입해야 합니다.
그렇지 않으면 이미 실행된 Push Back 작업을 통해 노드를 목록 뒤에 추가합니다.

func (l *LinkedList) AddBefore(node *Node, val interface{}) {
    if l.Head == nil || l.Head == node {
        l.PushFront(val)
    } else {
        var prev *Node
        cur := l.Head
        for cur != nil && cur != node {
            prev = cur
            cur = cur.Next
        }
        if cur != nil {
            prev.Next = &Node{Value: val, Next: cur}
        } else {
            l.PushBack(val)
        }
    }
}

운영 비용

헤더 포인터 때문에 목록 앞의 조작 원가가 비교적 낮다.목록 뒤에 요소를 삽입하는 것도 싸다. (꼬리 바늘이 없으면 이 작업은 O (n) 를 쓴다.
마지막 요소를 삭제하면 전체 목록에서 순환해야 하기 때문에 O(n) 형식으로 실행됩니다. 이것은 Add Before 작업에도 적용됩니다.
활용단어참조
꼬리가 없다
띠꼬리
전면 밀어냄 (val)
O(1)
PopFront
O(1)
리셋 (val)
O(n)
O(1)
팝업 ()
O(n)
AddAfter(노드, val)
O(1)
AddBefore(노드, val)
O(n)
마지막으로 목록의 전방향 포인터로 인해 기존 노드가 O(1)에서 다시 실행된 후에 요소를 추가합니다.

언제

기존 어레이에 비해 체인 테이블의 이점은 다음과 같습니다.

노드를 동적으로 추가하고 삭제할 수 있는 고정 크기가 없습니다.

기존 요소를 이동할 공간을 만들 필요가 없기 때문에 삽입과 삭제의 비용이 높지 않다.

Go에서 우리는 수조가 아니라 슬라이스 (동적 수조) 를 사용하고 수조는 크기를 조정하는 것을 책임지기 때문에 이 문제는 체인 테이블이 필요하지 않다.
그러나 삽입/삭제 비용은 어떻습니까?Bjarne Stroustrup의 한 글은 진열에 비해 이러한 조작은 속도 우위가 전혀 없다는 것을 보여 준다.
따라서 메모리 사용량 증가 (스토리지 바늘) 와 무작위 접근 속도 차이 등 단점만 남았다.

결론

나에게 있어서 바둑에서 단사슬표를 사용하는 것은 실제적인 우세가 없고 단지 슬라이스만 사용하면 된다.