Go에서 단일 연결 목록 구현-Golang-php.cn

안녕하세요 DEV.to 커뮤니티입니다!

이것은 내 데이터 구조 및 알고리즘 시리즈의 일부입니다. 이 글에서는 단일 연결 리스트를 구현하고, 다음 시리즈 글에서는 Go를 사용하여 다른 종류의 연결 리스트도 구현해 보겠습니다.

Singly Linked List Implementation in Go — 이미지 출처: GeeksforGeeks

단일 연결 목록을 구현하려면 구조, 노드 및 단일 연결 목록 자체가 필요합니다. 하지만 여기서 코딩을 시작하기 전에 코드를 정리하는 방법은 다음과 같습니다.


project
├── singly_linked_list
│   ├── node.go
│   └── list.go
└── main.go

로그인 후 복사

마디

노드는 가장 간단한 형태로 데이터와 다음 노드에 대한 포인터만 보유합니다. 따라서 다음은 노드로 사용할 구조체입니다(node.go 파일에 있음):


type SinglyNode struct {
    data interface{}
    next *SinglyNode
}

로그인 후 복사

우리는 구조체의 데이터에 대한 데이터 유형으로 인터페이스{}를 사용하므로 노드 내부에 원하는 데이터를 저장할 수 있습니다.

그런 다음 방금 생성한 노드 구조체를 활용하기 위한 몇 가지 메서드를 정의해야 합니다.


func NewSinglyNode(data interface{}) *SinglyNode {
    return &SinglyNode{data: data}
}

로그인 후 복사

객체 지향 언어에 익숙하다면 생성자가 무엇인지 대부분 익숙할 것입니다. Go는 객체 지향 언어가 아니기 때문에 클래스가 없지만 Go 세계의 일부 규칙에 따라 일반적으로 New라는 단어가 붙은 함수를 만듭니다. 그러나 OOP 언어에서 new는 객체 생성을 의미하는 특수 키워드라는 점을 명심하세요. 여기서 New는 이름 접두사일 뿐이며 그 이상은 아닙니다.

NewSinglyNode 함수는 인터페이스{} 유형의 data라는 인수 하나만 받고 SinglyNode의 포인터를 반환합니다.

다음으로 노드에 대한 몇 가지 getter 및 setter를 정의합니다.


func (n *SinglyNode) SetData(data interface{}) {
    n.data = data
}

func (n *SinglyNode) SetNext(next *SinglyNode) {
    n.next = next
}

func (n *SinglyNode) GetData() interface{} {
    return n.data
}

func (n *SinglyNode) GetNext() (*SinglyNode, error) {
    if n.next == nil {
        return nil, errors.New("no next node")
    }
    return n.next, nil
}

로그인 후 복사

SetData, Setnext 및 GetData는 설명이 거의 필요하지 않습니다. GetNext는 다음 SinglyNode에 대한 포인터와 다음 노드가 없는 경우 오류라는 두 가지 값을 반환합니다.

다음은 내 구조체의 문자열 표현이 어떤지 항상 알 수 있도록 항상 추가하고 싶은 추가 함수입니다.


func (n *SinglyNode) ToString() string {
    return n.data.(string)
}

로그인 후 복사

이제 노드 작업이 완료되었으므로 목록 자체를 구현해야 합니다. 단일 연결 목록은 첫 번째 노드를 헤드로 보유하고 내 선호에 따라 last라는 두 개의 추가 데이터가 마지막 노드와 목록에 추가된 노드 수를 보유하는 국가 속성을 보유합니다.

다음은 list.go 파일의 첫 번째 줄입니다.


type SinglyLinkedList struct {
    head  *SinglyNode
    last  *SinglyNode
    count int
}

로그인 후 복사

SinglyLinkedList를 쉽게 생성하는 생성자와 유사한 함수는 다음과 같습니다.


func NewSinglyLinkedList() *SinglyLinkedList {
    return &SinglyLinkedList{}
}

로그인 후 복사

연결리스트에서 가장 중요한 기능은 노드를 추가하는 기능입니다. 다음은 이러한 기능을 구현한 것입니다.


func (l *SinglyLinkedList) AttachNode(node *SinglyNode) {
    if l.head == nil {
        l.head = node
    } else {
        l.last.SetNext(node)
    }
    l.last = node
    l.count++
}

로그인 후 복사

기능은 다음과 같습니다.

링크드 리스트의 헤드가 비어 있는지 확인하고, 비어 있으면 수신된 노드를 리스트의 헤드로 설정하세요.
헤드가 비어 있지 않으면 수신된 노드를 마지막 노드의 다음 속성으로 설정합니다.
이전에 발생한 일에 관계없이 현재 노드는 마지막 노드여야 하므로 다음에 노드가 추가될 때 목록의 마지막 노드에 대해 다음 노드로 설정될 수 있습니다.
갯수를 1씩 늘립니다.

다음은 데이터를 수신하여 노드를 생성하고 이를 AttachNode 함수에 전달하는 함수입니다.


func (l *SinglyLinkedList) Add(data interface{}) {
    l.AttachNode(NewSinglyNode(data))
}

로그인 후 복사

이 기능이 중복되어 보일 수도 있지만 매번 수동으로 노드를 만들지 않고도 목록에 노드를 쉽게 추가할 수 있습니다.

count 속성도 가져오는 함수:


func (l *SinglyLinkedList) Count() int {
    return l.count
}

로그인 후 복사

필요한 마지막 함수는 연결 목록의 다음 노드를 반환해야 하는 함수입니다.


func (l *SinglyLinkedList) GetNext() (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    return l.head, nil
}

로그인 후 복사

저는 이 함수의 이름을 노드에 정의된 GetNext 함수와 동일하게 지정하는 것을 선호합니다. 이는 일관성을 높이기 위해 수행됩니다. 연결 목록에 처음 액세스할 때 유형은 연결 목록이므로 노드에 정의된 기능에 액세스할 수 없습니다. 동일한 이름의 함수를 정의하면 목록을 탐색하려는 만큼 GetNext를 사용할 수 있습니다.

제가 항상 추가하는 추가 기능 중 하나는 인덱스로 노드를 검색하는 기능입니다.


func (l *SinglyLinkedList) GetByIndex(index int) (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    if index+1 > l.count {
        return nil, errors.New("index out of range")
    }
    node, _ := l.GetNext()
    for i := 0; i < index; i++ {
        node, _ = node.GetNext()
    }
    return node, nil
}

로그인 후 복사

이 기능은 다음과 같습니다.

오류를 반환하려면 헤드가 비어 있는지 확인하세요
오류를 반환하려면 인덱스 1이 목록의 개수보다 큰지 확인하세요. 배열과 마찬가지로 0부터 시작하는 인덱스를 고려하므로 인덱스가 아닌 인덱스 1을 확인합니다.
l.GetNext()를 node라는 변수에 할당하고(_로 오류를 무시함) 제공된 인덱스보다 적은 인덱스에 대해 루프를 수행합니다. 이미 node 변수에 첫 번째 인덱스가 저장되어 있으므로 현재 노드의 다음 노드를 할당합니다. node를 다시 node로 사용하세요.
순회한 노드를 오류 없이 반환합니다.

테스트

이제 연결 목록과 노드 정의가 있으므로 아래와 같이 main.go 파일에서 테스트할 수 있습니다.


func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    firstNode, err := list.GetNext()
    if err != nil {
        panic(err)
    }

    secondNode, err := firstNode.GetNext()
    if err != nil {
        panic(err)
    }

    thirdNode, err := secondNode.GetNext()
    if err != nil {
        panic(err)
    }

    println(firstNode.ToString())  // One
    println(secondNode.ToString()) // Two
    println(thirdNode.ToString())  // Three
}

로그인 후 복사

또는 GetByIndex 함수 사용:


func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    node, err := list.GetByIndex(2)
    if err != nil {
        panic(err)
    }

    fmt.Println(node.ToString()) // Three
}

로그인 후 복사

그런데! 여기에서 내 무료 Node.js 필수 전자책을 확인하세요: