연결 리스트

안녕하세요. 그린입니다🟢

이번 포스팅에서는 연결 리스트에 대해 알아보고 Swift로 구현해보겠습니다🧑🏻‍💻

연결리스트

 : 이전 / 다음의 올 값의 참조 정보 가지는 배열의 형태

 - 물리적 순서가 순차적이지 않음

 - 한번에 찾는 데이터에 접근 불가

 - 데이터 삽입 및 삭제 시 이동 없이 참조 값 변경만 해주면되서 배열보다 쉬움 (속도가 빠름)

 - 노드와 데이터로 구성

 - 노드에는 다음 주소를 나타내는 포인터를 지님

 - 검색 속도가 느리고 저장 공간 효율성이 떨어짐

Swift로 단방향 연결 리스트 구현하기

import Foundation

// 노드 정의, Node의 값인 value와 다음 노드의 주소를 가진 next
class Node<T> {
    var data: T?
    var next: Node?
    
    init(data: T?, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

// 노드를 관리해주는 단방향 연결 리스트 구조체
struct LinkedList<T: Equatable> {
    var head: Node<T>?
    
    init(head: Node<T>? = nil) {
        self.head = head
    }
    
    // 맨 뒤에 새로운 노드 추가 시
    mutating func append(_ data: T?) {
        // 리스트에 값이 없을때 새롭게 헤드 지정
        if head == nil {
            head = Node(data: data)
            return
        }
        // 리스트에 값이 이미 존재할때 다음 노드가 없는곳까지 찾은 다음 마지막에 배치
        var node = head
        while node?.next != nil {
            node = node?.next
        }
        node?.next = Node(data: data)
    }
    
    // 특정 위치에 새로운 노드 삽입
    mutating func insert(_ data: T, at index: Int) {
        // 리스트 값 없을때 새롭게 헤드 지정
        if head == nil {
            head = Node(data: data)
            return
        }
        // 중간에 데이터 삽입 시
        var node = head
        for _ in 0..<(index - 1) {
            if node?.next == nil {
                break
            }
            node = node?.next
        }
        let nextNode = node?.next
        let insertNode = Node(data: data)
        node?.next = insertNode
        insertNode.next = nextNode
    }
    
    // 마지막 데이터 요소 삭제
    mutating func removeLast() {
        // 데이터 없을 시 미삭제
        if head == nil {
            return
        }
        // 데이터 1개일 시 헤드 삭제
        if head?.next == nil {
            head = nil
            return
        }
        // 데이터 여러개일 시 마지막 요소 찾아서 삭제
        var node = head
        while node?.next?.next != nil {
            node = node?.next
        }
        node?.next = nil
    }
    
    // 원하는 위치 요소 삭제
    mutating func remove(at index: Int) {
        // 데이터 없다면 탈출
        if head == nil {
            return
        }
        // head를 삭제할때
        if index == 0 {
            head = nil
            return
        }
        // 삭제할 노드의 다음 노드를 이전 노드가 연결하게 변경
        var node = head
        for _ in 0..<(index - 1) {
            // 삭제할 노드가 맨 마지막 노드일때 삭제
            if node?.next?.next == nil {
                break
            }
            node = node?.next
        }
        node?.next = node?.next?.next
    }
    
    // 전체 연결 리스트 삭제
    mutating func removeAll() {
        head = nil
    }
    
    // 데이터로 원하는 노드 찾기
    mutating func search(data: T?) -> Node<T>? {
        // 데이터가 없으면 nil 반환
        if head == nil {
            return nil
        }
        var node = head
        while node?.next != nil {
            if node?.data == data {
                break
            }
            node = node?.next
        }
        return node
    }
    
    // 연결 리스트의 사이즈 측정
    func size() -> Int {
        var node = head
        if node == nil {
            return 0
        }
        var count = 1
        
        while node?.next != nil {
            node = node?.next
            count += 1
        }
        return count
    }
    
    // 찾는 데이터가 있는지에 대해 판별
    func contains(_ data: T) -> Bool {
        var node = head
        
        while true {
            if node?.data == data {
                return true
            }
            node = node?.next
            if node?.data == nil {
                return false
            }
        }
    }
    
    // 연결 리스트가 비어있는지 판별
    var isEmpty: Bool {
        return head == nil
    }
}

var linkList = LinkedList<Int>(head: Node(data: 1, next: nil))
linkList.append(2)
print(linkList.contains(2)) // true
print(linkList.size()) // 2
print(linkList.insert(3, at: 1))

노드의 제네릭에 Equatable 프로토콜을 채택한 이유는 이후 search와 contains 메서드에서 값을 비교해주기 위해 채택해야한다. 

실제로 연결 리스트를 구현해보면서 느꼈던점이 다음 노드를 가르키고 있어 삭제하거나 할때에는 해당 노드의 연결을 끊어주면

실제로 삭제된것으로 볼 수 있다.

그래서 전체 삭제 시에도 헤드 노드만 없애주면 전체 리스트를 접근하지 못함으로 삭제라 볼 수 있다.

배열보다 해당 원하는 인덱스 노드의 접근은 불편하지만 데이터가 삽입되고 삭제될때 다시 재연결만 시켜주면 되는것으로

배열처럼 모든 인덱스가 이동이 일어나는것보다 효율적이라 생각된다.