LinkedList 의 특징과 예제

John Jeonguk Hur·2023년 3월 30일
0

DSA

목록 보기
1/1

Leet code를 연습하던중 기본 자료구조인 LinkedList에 대한 이해를 가지려고 배운것을 토대로 블로그에 남기게 됩니다.

LinkedList 특징

링크드 리스트(Linked List)는 데이터를 노드(Node)에 담아 연결하여 저장하는 자료구조입니다. 링크드 리스트를 사용하면, 노드 간의 연결만 수정하면 되기 때문에 삽입, 삭제, 검색 등의 작업이 효율적으로 수행됩니다.

구현 방법

Swift에서 링크드 리스트를 구현하는 방법을 알아보겠습니다. 먼저, 노드를 나타내는 LinkedListNode 클래스를 정의합니다. 이 클래스는 제네릭으로 선언되어, 어떤 타입의 값을 담을 수 있는지 지정할 수 있습니다. 노드는 value와 next 프로퍼티를 가지고 있습니다. value는 해당 노드가 담고 있는 값이고, next는 다음 노드를 가리키는 포인터입니다.

class LinkedListNode<T: Equatable> {
    var value: T
    var next: LinkedListNode?
    
    init(value: T) {
        self.value = value
    }
}

다음으로, 링크드 리스트를 구현하는 LinkedList 클래스를 정의합니다. 이 클래스도 제네릭으로 선언되어, 어떤 타입의 값을 담을 수 있는지 지정할 수 있습니다. head 프로퍼티는 링크드 리스트의 첫 번째 노드를 가리키는 포인터입니다.

class LinkedList<T: Equatable> {
    var head: LinkedListNode<T>?
    
    // 삽입
    func append(_ value: T) {
        let newNode = LinkedListNode(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
            tail = newNode
        } else {
            head = newNode
            tail = newNode
        }
    }
    // 검색
    func search(_ value: T) -> LinkedListNode<T>? {
        var currentNode = head
        while let node = currentNode {
            if node.value == value {
                return node
            }
            currentNode = node.next
        }
        return nil
    }
}

데이터 생성

LinkedList 클래스에는 append(:)와 search(:) 메서드가 구현되어 있습니다. append(:)는 새로운 노드를 맨 끝에 추가하는 메서드이며, search(:)는 특정 값이 저장된 노드를 찾는 메서드입니다. search(_:)는 해당 값이 저장된 노드를 반환하며, 값이 없는 경우 nil을 반환합니다.

이제 링크드 리스트를 사용하는 방법을 알아보겠습니다. 다음과 같이 노드를 생성하고, next 프로퍼티를 이용해 연결합니다.

var list1 = LinkedListNode(value: 2)
list1.next = LinkedListNode(value: 5)
list1.next?.next = LinkedListNode(value: 10)

링크드 리스트를 구현한 LinkedList 클래스를 사용해서 노드를 추가하고 검색하는 예제 코드입니다.

// LinkedList 클래스를 생성합니다.
var list = LinkedList<Int>()

// LinkedList에 노드를 추가합니다.
list.append(1)
list.append(2)
list.append(3)
list.append(4)

// LinkedList에서 특정 값을 검색합니다.
if let node = list.search(3) {
    print("찾은 값은 \(node.value)입니다.") // 출력: 찾은 값은 3입니다.
} else {
    print("해당 값이 존재하지 않습니다.")
}

위 코드에서는 LinkedList 클래스를 생성한 후에 append 메서드를 사용하여 값을 추가하고, search 메서드를 사용하여 원하는 값을 검색하고 있습니다.

노드를 추가할 때에는 append 메서드를 사용하고, 원하는 값을 검색할 때에는 search 메서드를 사용하면 됩니다. 검색 결과가 있으면 해당 노드의 값을 출력하고, 검색 결과가 없으면 메시지를 출력합니다.

결론

링크드 리스트는 데이터의 삽입과 삭제가 용이하며, 순차적으로 데이터를 검색할 때 성능이 좋습니다. 따라서 링크드 리스트를 사용하면 데이터의 삽입과 삭제가 빈번하게 일어나는 상황에서 유용하게 사용할 수 있습니다.

profile
Hi, I'm an iOS Developer. I will archive the minor details.

0개의 댓글