golang에서 이중 연결 목록을 구현하는 방법

이중 연결 목록은 요소 간에 양방향 연결을 설정할 수 있는 일반적인 데이터 구조로, 연결 목록의 삽입, 삭제, 순회 등의 작업을 매우 효율적으로 만듭니다. Go 언어에서 이중 연결 목록의 구현은 매우 간단합니다. 이 기사에서는 Go를 사용하여 이중 연결 목록을 구현하는 방법을 소개합니다.

이중 연결 리스트는 연결된 구조이며 각 노드에는 이전 포인터 prev, 후속 포인터 next 및 데이터 필드 데이터의 세 부분이 포함됩니다. Go에서는 이중 연결 목록의 노드를 나타내는 구조체를 정의할 수 있습니다.

type ListNode struct {
    prev *ListNode
    next *ListNode
    data interface{}
}

여기서 prev 和 next 分别指向当前节点的前驱和后继节点，data는 노드에 저장된 데이터입니다.

이중 연결 목록을 구현하려면 연결 목록의 헤드 노드와 꼬리 노드에 대한 포인터와 연결 목록 크기의 길이를 포함하는 LinkedList 유형을 정의해야 합니다.

type LinkedList struct {
    head *ListNode
    tail *ListNode
    size int
}

각각을 구현해 보겠습니다. 이중 연결 리스트를 하나씩 작업합니다.

요소 삽입

이중 연결 목록에 요소를 삽입하는 경우에는 세 가지 주요 상황이 있습니다.

1. 연결 목록의 머리 부분에 요소를 삽입합니다.
2. 연결리스트 끝에 요소를 삽입하세요.
3. 연결리스트 중간에 요소를 삽입하세요.

Go에서는 위의 세 가지 상황을 구현하기 위해 Insert 메서드를 정의할 수 있습니다.

func (list *LinkedList) Insert(data interface{}) {
    node := &ListNode{data: data}
    if list.head == nil {
        list.head = node
        list.tail = node
    } else {
        node.prev = list.tail
        list.tail.next = node
        list.tail = node
    }
    list.size++
}

먼저 삽입할 데이터를 저장할 새 노드 노드를 만듭니다. 연결리스트가 비어 있으면 새 노드가 헤드 노드와 테일 노드로 사용됩니다. 그렇지 않으면 꼬리 노드 뒤에 새 노드를 삽입하고 꼬리 노드 포인터를 새 노드로 업데이트합니다. 마지막으로 연결리스트의 길이가 1 증가합니다.

요소 삭제

요소 삽입과 유사하게 요소 삭제에도 세 가지 상황이 포함될 수 있습니다.

1. 연결된 목록의 헤드 요소 삭제.
2. 연결리스트의 꼬리 요소를 삭제하세요.
3. 연결리스트 중간에 있는 요소를 삭제하세요.

다음은 삭제 메소드의 구현 예입니다.

func (list *LinkedList) Delete(data interface{}) {
    node := list.find(data)
    if node != nil {
        if node.prev != nil {
            node.prev.next = node.next
        } else {
            list.head = node.next
        }
        if node.next != nil {
            node.next.prev = node.prev
        } else {
            list.tail = node.prev
        }
        list.size--
    }
}

func (list *LinkedList) find(data interface{}) *ListNode {
    node := list.head
    for node != nil && node.data != data {
        node = node.next
    }
    return node
}

먼저 삭제할 노드 노드를 찾아야 하는데, 이는 찾기 기능을 통해 구현됩니다. 삭제할 노드가 발견되면 노드의 위치를 ​​기준으로 선행 노드와 후속 노드의 포인터를 업데이트해야 합니다. 삭제할 노드가 헤드 노드인 경우 헤드 노드 포인터를 다음 노드로 업데이트하고, 삭제할 노드가 테일 노드인 경우 테일 노드 포인터를 이전 노드로 업데이트합니다. 마지막으로 연결리스트의 길이를 1만큼 줄입니다.

요소 탐색

이중 연결 목록 탐색은 매우 간단합니다. 헤드 노드에서 시작하여 다음 후속 포인터를 따라 계속 탐색하면 됩니다. 역방향 순회는 꼬리 노드에서 시작하여 이전 포인터 prev를 따라 순회할 수 있습니다. 다음은 각각 정방향 순회와 역방향 순회를 구현하는 두 가지 방법입니다.

func (list *LinkedList) Traverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.head
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.next
    }
    return result
}

func (list *LinkedList) ReverseTraverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.tail
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.prev
    }
    return result
}

순회할 때 순회 결과를 저장하기 위해 슬라이스를 생성한 다음 헤드 또는 테일 노드에서 시작하여 포인터를 따라 각 노드를 순회합니다. 데이터는 조각으로 저장됩니다.

Summary

위 코드를 통해 이중 연결 리스트의 기본 연산을 성공적으로 구현했습니다. 실제 응용에서는 연결 목록의 특정 위치에 요소를 삽입하거나 삭제하거나 인덱스를 통해 요소에 액세스하는 등 이중 연결 목록에 대한 많은 확장 및 최적화가 있습니다. 독자들은 필요에 따라 추가 연구와 실습을 수행할 수 있습니다.

이 기사의 코드 예제는 독자의 참조를 위해 GitHub에 업로드되었습니다: https://github.com/linjiawei123/golang-doubly-linked-list

위 내용은 golang에서 이중 연결 목록을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!