[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)

• 연속적인 메모리 위치에 저장되지 않는 선형 자료구조
• 데이터 필드 + 다음의 노드에 대한 참조 를 포함하는 노드로 구성

 

연결 리스트를 사용하는 이유?

배열은 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당받아야 했다. 그렇기 때문에 새로운 요소 삽입의 비용이 많이 든다. (공간 만들기 + 기존 요소의 이동)

 

장점

• 동적인 크기를 가진다.
• 삽입/삭제가 용이하고 속도가 빠르다.

단점

• Random Access가 불가하기 때문에 첫 번째 노드부터 순차적으로 액세스해야한다.
• 검색 속도가 느리다.
• 저장 공간의 효율이 높지 않다.

 

추가(add)

• 노드가 아무것도 없을 때
  • head = nil, tail = nil
  • head 값을 확인 후 새로운 노드를 연결하고 tail도 동일하게 새로운 노드를 연결한다.
• 이미 데이터가 존재하는 경우
  • 가장 마지막 노드를 가리키는 tail을 찾고, 그 다음 노드에 새로운 노드를 연결한다.
  • 가장 마지막 노드가 된 새로운 노드를 tail이 가리키는 노드로 변경한다.

탐색(Search)

• 제일 처음 노드인 head부터 타켓 노드를 찾을 때까지 next를 통해 다음 노드를 탐색한다.
• 포인터 역할을 하는 now를 통해 타겟을 찾아 탐색한다.

삽입(Insert)

• 특정 노드의 앞이나 뒤에 새로운 노드를 삽입하려면 타겟 지점까지 탐색을 먼저 진행한다.
• 타겟 노드 뒤에 새로운 노드를 추가한다. 포인터를 바꾸어준다.
• 타겟 노드를 찾기 위해서 탐색 연산을 수행하기 때문에 O(n)의 시간복잡도가 요구되고, 이후 포인터 변경을 수행하여 O(1)의 시간복잡도가 요구된다.

삭제(Delete)

• 삽입 연산과 유사하게 삭제할 노드를 탐색한다.
• 노드의 next 포인터를 삭제할 노드의 다음 노드로 연결을 바꾸어준다.

 

구현

Node.swift

class Node<T: Equatable> {
    let data: T
    var next: Node?
    
    init(data: T, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

 

LinkedList.swift

struct LinkedList<T: Equatable> {
    var head: Node<T>?
    var tail: Node<T>?
    
    // 추가
    mutating func add(node: Node<T>) {
        // (1) 노드가 아무것도 없을 때
        if head == nil {
            head = node
            tail = node
            return
        }
        
        // (2) 이미 데이터가 존재하는 경우
        // tail의 다음 노드에 새로운 노드를 연결하고, 그 새로운 노드를 tail이 가리키는 노드로 변깋ㅏ기
        tail?.next = node
        tail = node
    }
    
    // 탐색
    func search(data: T) -> Node<T>? {
        // 포인터 역할을 하는 now
        guard var now = head else { return nil }
        
        // now의 데이터와 타겟 데이터를 비교하고, 찾을 때까지 next를 통해 탐색하기
        while now.data != data {
            guard let next = now.next else { return nil }
            now = next
        }
        
        return now
    }
    
    // 삽입
    func insert(index: Int, data: T) {
        // 포인터 역할을 하는 now
        guard var now = head else { return }
        
        // 탐색 시작 인덱스
        var currentIndex = 0
        
        // (1) now를 다음 노드로 이동하면서 삽입하려는 위치 찾기
        while currentIndex < index {
            guard let nowNext = now.next else { return }
            now = nowNext
            
            currentIndex += 1
        }
        
        // (2) 타겟 노드 뒤에 새로운 노드 삽입하기
        now.next = Node(data: data, next: now.next)
    }
    
    // 삭제
    mutating func remove(node: Node<T>) {
        // 포인터 역할을 하는 now
        guard var now = head else { return }
        
        // (1) head를 삭제하는 경우
        guard now !== node else {
            head = now.next
            return
        }
        
        // (2) 특정 노드를 삭제하는 경우 - 특정 노드 탐색하기
        while now.next !== node {
            guard let nowNext = now.next else { return }
            now = nowNext
        }
        
        // (3) 마지막 노드 체크
        if now.next === tail {
            tail = now
        }
        
        now.next = now.next?.next
    }
    
    // print
    func printLinkedList() {
        guard var now = head else { return }
        
        while now != nil {
            guard let nowNext = now.next else {
                print("data: \(now.data), next: \(now.next?.data)")
                return
            }
            print("data: \(now.data), next: \(nowNext.data)")

            guard let nowNext = now.next else { return }
            now = nowNext
        }
    }
}

 

실행 결과