Swift - Singly Linked Lists(단방향 연결리스트)

📗 연결리스트란?

구현은 다 해놓고선 바빠서 글을 올리지 못했던 자료구조에 대해 글을 올려본다.

📚 배열

먼저, 배열은 아주 사용하기 편리한 자료구조이다. (swift에서 사용되는 배열은 동적배열로 여기서 말하는 배열은 정적배열이다.)

 

배열의 장점은 메모리 공간 안에 데이터가 나란히 저장되어 있다.

따라서 내가 배열을 사용할 때 index를 통해 데이터 접근이 가능하며

index를 알고 있다면 데이터에 대한 접근이 매우 빠르다.

 

배열은 컴파일되기 전에 사용할 메모리의 크기를 정해줘야하며

 

배열 중간에 원소를 삽입의 경우 메모리 크기를 늘린
배열을 선언 후 이 배열에 값을 다시 복사해주는 연산이 필요하다.

 

배열 중간에 원소를 삭제하는 경우 삭제한 공간만큼 앞으로 땡겨주는

연산이 필요하다.

 

즉, 원소들을 재배치하거나, 복사연산의 작업때문에

오버헤드가 발생하는 단점이 생기는 것이다.

📚 연결리스트

연결리스트는 이러한 배열의 단점을 보완해주기 위해 나온 자료구조로서,
데이터를 저장할 수 있는 노드와 다른 노드가 연결되어 있는 집합이다. 이러한 방식으로 노드는 메모리의 어느 곳에나 위치할 수 있으며,
노드는 다른 노드의 주소를 저장할 수 있는 주소공간을 가지고 있어 배열의 중간 위치에 원소를 추가하는 연산 속도가 매우 빠르다.

 

그러나.. 데이터가 점점 쌓이게 되면서 접근이 무조건 순차적으로 가야하기 때문에 맨 마지막 노드에 접근하는 속도가 매우 느리다는 점

다음 노드의 주소를 저장할 별도의 공간이 필요하여 공간효율성은 그다지 좋진 않은 것 같다.

 

📚 단방향 연결리스트

단방향 연결리스트는 말그대로 단방향이다.

한 쪽 방향으로만 데이터 접근이 가능하다는 것이다.

즉, 내가 어떤 데이터에 접근 하려고 노드를 순회하는 도중 전에 노드의 데이터에 접근이 불가능한 것.

 

위 모양이 앞서 말하고 있는 노드(Node)의 모양이다.

연결리스트는 이 노드끼리 연결되어 있는 집합 모양의

자료구조이다.

📕 노드의 구현

먼저 노드에 대한 구현에 대해 알아본다.

노드의 타입으로서는 어떤 데이터 타입으로 연결리스트가 선언될 지 모르기 때문에
제네릭 타입으로 선언.

 

데이터를 연결리스트에 추가하는 경우

노드를 생성하여 노드의 데이터에 저장하는 것.

• data: 노드에 저장할 데이터
• next: 옵셔널 타입으로 다음 순서에 올 노드의 주소를 저장하는 공간
  • 마지막 노드는 다음 노드의 주소를 갖고있을 수 없기 때문에 옵셔널 타입으로 선언

class Node<T> {
    public var data: T
    public var next: Node?

    init(_ data: T, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

 

📙 단방향 연결리스트 구현

배열처럼 노드를 추가, 수정, 삭제 등

노드를 관리해줄 프로퍼티 및 메서드를 담고있는

LinkedList 구조체(상속할 필요도 없으니..)를 선언

struct LinkedList<T> {}

 

📚 head :: 첫 노드를 가리키는 프로퍼티

연결리스트에는 가장 첫 노드를 가리키는 head 라는 친구를 항상 갖고있다.

이유는, 연결리스트는 노드들이 연결, 연결되어 있는 구조다.

데이터에 접근 하기 위해서는 순차적으로 확인해야 하는데

 

그러기 위해서는 첫 번째 노드의 메모리 주소를 알고 있어야 하는 것이다.

물론 그냥 노드라고 칭하면 되지 않겠냐 라는 생각을 할 수 있지만,

편의상 맨 꼭대기에 있다는 의미에서 head라고 개발자들끼리 약속을 한 것이다.

 

물론 첫 노드를 가리키는 프로퍼티 라고 했지만,

그냥 첫 번째 노드구나 라고 생각하면 되겠다.

 

코드는 이러하다.

// 연결리스트의 첫 번째 Node를 가리키는 head
private var head: Node<T>?

 

📚 append(element:) :: 마지막 노드 뒤에 원소 삽입 메서드

배열과 같이 마지막에 원소를 추가해주는 메서드이다.

연결리스트의 경우 첫 노드 즉, head 노드부터 노드의 next를 확인하면서

순회하면서 next가 nil인 노드를 확인 후

새 노드를 만들어 nil인 노드의 next에 연결해주면 끝이다.

(매우 간단.)

 

코드는 이러하다.

// 원소를 맨 뒤에 추가해주는 메서드
mutating func append(_ element: T) {
    // head가 비어있는 경우 Node 할당 후 head로 지정
    if head == nil {
        self.head = Node(element)
        return
    }

    // node가 존재할 경우
    var node: Node? = head
    while node?.next != nil {
        node = node?.next
    }
    node?.next = Node(element)
}

 

📚 insert(element:at:) :: 노드와 노드 사이에 중간 삽입 메서드

 

1. 삽입하려는 위치의 전에 위치하는 노드를 head 노드부터 순회하면서 찾는다.
2. 찾았으면 삽입하려는 데이터를 담은 노드를 생성해준다.
3. 순회하면서 찾은 노드의 next에 새로 생성해준 노드를 연결해준다.
4. 새로 생성해준 노드의 next에 원래 기존에 연결되어 있던 노드의 다음 노드를 연결해준다.

근데 중간에 원소를 중간에 삽입 하기 위해서는 인덱스를 알려줘야한다.

몇 번째 순서인지는 알아야할테니..

하지만 배열과는 다르게 연결리스트에서는 인덱스가 존재하지 않기 때문에

인덱스 만큼 반복해주면서 head 노드부터 순회하면 되는 것이다.

 

코드는 이러하다.

mutating func insert(_ element: T, at index: Int) {
    do {
        // out of range 검사
        try rangeOverIndex(index)

        // 0번째 인덱스에 값이 들어온다면 헤드에 값이 들어오는 것이기 때문에
        // 새로운 node를 할당하고 새로운 node의 next는 head를 가리키고
        // head는 다시 새로운 node를 가리킨다
        if index == 0 {
            let newNode: Node = Node(element)
            newNode.next = head
            head = newNode
            return
        }

        // 해당 인덱스 - 1 만큼 iterator node로 순회하며
        // 새로운 node를 할당 후 새 node의 next는 iterator node의 next를 가리키고
        // iterator node의 next가 새 node를 가리키게 한다
        var node = head
        for _ in 0..<(index - 1) {
            if node?.next == nil { break }
            node = node?.next
        }

        let newNode: Node = Node(element)
        newNode.next = node?.next
        node?.next = newNode

    // 전달받은 index 값이 마지막 node의 인덱스보다 크다면 error 출력
    } catch AccessError.outOfRange {
        print("Fatal error: Index out of range")
    } catch {
        print("Fatal error: Unknown Access")
    }
}

 

위에 rangeOverIndex(index:) 메서드는 input으로 들어온 index 값이

연결리스트의 노드 개수보다 크다면 Error를 throw 하는 메서드이다.

 

코드는 아래와 같다.

// 연결리스트의 사이즈를 카운트를 반환하는 프로퍼티
public var count: Int {
    var cnt: Int = 0
    // head가 nil인 경우 0을 반환
    if head == nil {
        return cnt
    }

    // head가 nil이 아닌
    // head의 next가 존재하는 경우
    // head의 next를 계속 순회하며 count 후 반환
    var node: Node? = head
    cnt += 1
    while node?.next != nil {
        cnt += 1
        node = node?.next
    }
    return cnt
}

// 전달인자로 전달받은 index 값이 연결리스트의 마지막 인덱스보다 크면
// outOfRange 에러를 throw 한다
private func rangeOverIndex(_ index: Int) throws {
    guard index <= count - 1 else { throw AccessError.outOfRange }
}

 

 

📚 removeFirst() -> T? :: 연결리스트 head 노드 삭제 메서드

 

첫 번째 노드인 head 노드를 삭제하는 메서드로

이 과정 자체는 매우 간단하다.

첫 번째 노드를 가리키고 있는 head를 head의 next 노드를 가리키면 되는 것이다.

 

코드는 아래와 같다.

// 연결리스트의 첫 번째 원소 제거 메서드
mutating func removeFirst() -> T? {
    // 연결리스트가 비었을 때
    if head == nil {
        return nil
    }
    guard let data: T = head?.data else { return nil }
    head = head?.next
    return data
}

 

📚 remove(at:) :: 연결리스트 중간 노드 삭제 메서드

 

삭제하려는 원소의 index를 input으로 받아 해당 원소를 갖고있는 node를 삭제하는 메서드

노드와 노드 사이에 있는 노드를 삭제하는 중간 노드 삭제 메서드이다.

순서를 보자면 매우 간단하다

1. head 노드부터 순회하면서 입력받은 순서에 해당하는 노드의 전 노드를 찾는다
2. 전 노드의 next에 입력받은 순서의 다음에 해당하는 노드를 연결한다.

Note
node의 next로 참조하고 있던 node와의 연결이 끊기면 해당 node는 Swift의 언어가
자동적으로 메모리에서 해제해버린다.

 

코드는 아래와 같다.

// 전달받은 인덱스에 해당하는 원소 제거 메서드
mutating func remove(at index: Int) {
    // 연결리스트가 비었을 때
    guard head != nil else { return }
    do {
        try rangeOverIndex(index)

        if index == 0 {
            head = head?.next
        }
        var node: Node? = head
        for _ in 0..<(index - 1) {
            if node?.next?.next == nil { break }
            node = node?.next
        }

        node?.next = node?.next?.next

    } catch AccessError.outOfRange {
        print("Fatal error: Index out of range")
    } catch {
        print("Fatal error: Unknown Access")
    }
}

 

📚 removeLast() -> T? :: 연결리스트 마지막 노드 삭제 메서드

 

연결리스트의 마지막 노드를 삭제하는 메서드로

흔히 tail 노드라고 부르는 꼬리 노드를 삭제하는 메서드이다.

과정 자체도 매우 간단하다.

1. 마지막 노드의 전에 해당하는 노드를 찾는다.
2. 전 노드와 마지막 노드와의 연결을 끊기 위하여 전 노드의 next에 nil을 넣어준다.

코드는 아래와 같다.

// 연결리스트의 마지막 원소 제거 메서드
mutating func removeLast() -> T? {
    // 연결리스트가 비었을 때
    if head == nil {
        return nil
    }
    var node: Node? = head
    while node?.next?.next != nil {
        node = node?.next
    }
    guard let data = node?.next?.data else { return nil }
    node?.next = node?.next?.next
    return data
}

 

📚 contains(element:) :: 데이터가 존재하는 유무를 반환하는 메서드

public func contains(_ element: T) -> Bool {
    guard head != nil else { return false }
    var node = head
    while node?.next != nil {
        if node?.data == data { return true }
        node = node?.next
    }

    return false
}

 

위의 메서드를 구현하는 과정에서 노드의 데이터와 입력받은 데이터를 비교하는 코드에서 에러가 발생했다.

위의 에러가 발생하였는데

그 이유는, 노드의 데이터와 input으로 받은 element의 데이터 타입을 연결리스트가 선언되기전까지

알 수 없고, Equatable을 채택하지 않은 데이터 타입이 들어오게되면 두 데이터를 비교할 수 없기 때문이다.

이 에러를 해결하기 위해서는 LinkedList 구조체의 제네릭에 Equatable 프로토콜을 채택하여

LinkedList 선언 시, Equatable을 채택한 데이터 타입만 받도록 해주면 되는 것이다.

 

요로코롬

struct LinkedList<T: Equatable> {}

자잘한 메서드나 프로퍼티도 구현을 해놨으나 따로 설명할 필요는 없을 것 같아 써놓진 않았지만,
혹시 이 블로그를 봤는데 궁금하신 분이 계시다면 전체 코드가 담긴 깃허브 링크를 남겨놓겠습니다.

 

DataStuctures-Algorithms-in-Swift/DataStructures_in_Swift/Singly Linked List/Singly Linked List/main.swift at main · bdrsky2010