Swift) 단방향 연결 리스트(LinkedList) 구현 해보기

 

 

 

안녕하새요 :) 소들입니다!

오늘은 연결 리스트에 대해 공부해보려고 해요!!!! 🤪

그 중에서도 이번 포스팅에선 단방향에 대해 다룰 것입니다..!

 

제가 옛~~날에 자료구조 수업 들을 때 되게 재밌게 공부했던 부분인데,

다시 공부하려니까 기억도 새록새록 나면서 헷갈리고 재밌고 그렇네영

Swift로 짜려니까 새롭기도 하고

 

처음 공부하면 조금 어려운 개념인 만큼,

Queue, Stack처럼 쉽게 코드만 설명하기보다, 이해하기 쉽게 그림과 함께 설명하려고 합니다 :)

이 글을 읽는 개린이 누군가를 위해서라기보다..

나중에 또 까먹고 고생하고 있을 나를 위해^^;

 

그럼 출~~발~~~~

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 배열 vs 연결 리스트

 

자, 먼저 우리가 앞서 배웠던 Queue, Stack은 모두 배열로 구현 했었음

그럼 연결 리스트는 뭔데 갑툭튀해서 배열과 비교하나 싶지 않음..?

 

ㅇㅕ러분

이 포스팅의 카테고리가 '자료구조'잖음??

연결 리스트 또한 배열과 같이 데이터를 표현하는 자료구조 중 하나임!!!

 

다만, 배열과 연결 리스트는 서로의 장단점을 보완하고 있기 때문에

보통 연결 리스트를 설명할 때 배열과 함께 묶어서 보는 것임

이렇게만 말하면 뭔말인지 1도 모르니까

먼저 배열부터 보겠음

 

 

 

1-1. 배열의 특징은

 

우리가 앞서 공부한 배열의 특징은, index를 이용하여 

다음과 같이 한 메모리 공간 안에 데이터들이 "나란히" 저장되어 있음

 

 

 

 

이렇게!

따라서 우리는 메모리에 저장할 때 index를 통해 데이터에 접근할 수 있고!

따라서, 배열의 경우 index만 알면 값에 대한 접근이 매우 빠른 것이 배열의 장점임!

 

그러나, Queue에서도 설명 했듯이,

배열의 경우, 마지막 index가 아닌 element를 삭제하거나 삽입할 경우,

 

 

 

 

이런 식으로 element를 재배치하는 작업 때문에

오버헤드가 발생하는 단점이 있음

 

그럼, 연결 리스트는 이를 보완한 것이겠네!? 맞음 :)

 

 

 

1-2. 연결 리스트의 특징은

 

앞서 설명했듯이, 연결 리스트는 배열의 단점을 보완한 것임!

따라서, 배열과 같이 순차적으로 데이터를 보관하는 것이 아닌,

각각 떨어진 공간에 존재하는 데이터를 연결해 놓은 것임!

 

이후 자세히 설명할 것이지만, 간단하게 그림으로 보자면 다음과 같음

 

 

 

 

이런 식으루!

따라서, 원하는 때에 메모리에 공간을 할당해서 쓰면 되고,

또 배열처럼 중간 element를 삽입, 삭제 시 재배치에 발생하는 오버헤드도 발생하지 않음!

(이후 볼 거지만 연결만 바꿔주면 되니까)

 

연결 리스트는 이렇게 배열의 단점을 보완하긴 했지만,

 

 

 

 

배열처럼 index로 접근하는 것이 아니기 때문에,

데이터에 접근하려면 첫 번째 데이터부터 원하는 데이터까지 (단방향 연결 리스트)

위 짤처럼 순차적으로 찾아가야 해서 접근 속도가 느림

만일 데이터가 1000개인데, 1000번째 데이터에 접근하려면 1000번 순회해야됨 개오바;

 

또한, 내 다음 데이터에 대한 연결 정보를 저장하는 별도의 데이터 공간이 필요해서,

저장 공간의 효율이 높지 않음..!

 

 

.

.

쨌든 정리하자면,

 

 

	배열	연결리스트
장점	- 인덱스 값을 미리 알고 있는 경우, 데이터에 매우 신속한 접근 가능 - 새로운 요소 삽입이 빠름	- 데이터 삽입 및 삭제 속도가 빠름
단점	- 크기가 고정되고, 삭제 및 검색이 느림	- 검색 속도가 느림 -저장 공간 효율이 높지 않음

 

 

배열과 연결 리스트는 이러한 차이가 있음 :)

그럼 연결 리스트 사용법을 봐보자!

 

 

 

 

2. 단방향 연결 리스트

 

자, 먼저 단방향 연결 리스트에 대해서 보겠음!

연결 리스트 앞에 '단'이 붙은 건 일단 스킵하고 보셈

 

앞서 설명 했듯이, 연결 리스트는 

연속되지 않은 메모리에 저장된 데이터들을 연결시켜 놓은 것

이라고 했음!

 

근데, 이때 연결을 어떻게 하냐면

내 다음 순서 데이터의 주소값을 내가 가지고 있어야 함

 

따라서, 단방향 연결 리스트의 경우,

데이터의 모양이 다음과 같이 생겼음

 

 

 

 

data는 내 데이터를 저장하는 것이고,

next는 내 다음 데이터의 주소값을 저장하는 것임!

 

자, 위와 같은 모양을 우리는 노드(Node)라고 부름!

그리고 연결 리스트는, 이 노드들이 연결되어 이루어진 자료 구조인 것을 말함!

이제 코드로 봐보자 👻

 

 

 

2-1. Node를 생성해보자

 

우린 Node가 data와 next로 생겼단 것을 알았으니,

이를 class로 구현해보도록 하겠음 :)

 

 

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

 

 

이렇게 구현하면 되는데,

먼저 데이터의 타입은 국한되지 않게 제네릭<T>로 선언 했음!

 

자, 이제 우린 데이터를 저장하고 싶을 때마다 배열의 element가 아니라,

이 Node를 생성해서 연결해주면 됨!

 

근데 노드를 매번 생성하고 이전 노드와 연결해주는 것을 일일이 매번 코딩할 수 없으니,

Node를 관리해주는 LinkedList라는 클래스를 다음과 같이 만들어 보겠음!

 

 

class LinkedList<T> {
}

 

 

그리고 연결 리스트에 필요한 기능들을 추가해보겠음

 

 

 

2-2. head : 가장 첫 노드를 가리키는 프로퍼티

 

먼저, LinkedList에 head라는 프로퍼티를 추가해줄 것임

왜냐? 연결 리스트는 앞서 말했듯이 데이터들이 '연결' 되어 있는 구조이고,

만약 특정 데이터에 접근하려면,

 

 

 

 

이렇게 첫 번째 노드부터 순차적으로 접근해야 한다고 했음!

때문에 연결 리스트에서는 첫 번째 노드를 항상 가지고 있어야 하고, 이를 head로 가리키는 것임!

위 예제에서는 가장 첫번째에 있는 3이란 data를 갖고 있는 노드가 head가 되는 것임!

 

 

class LinkedList<T> {
    private var head: Node<T>?
}

 

 

따라서, 첫 번째 노드를 가리킬 head 프로퍼티를 위와 같이 추가해주어야 함!

 

 

 

2-3. append(data:) : 연결 리스트 맨 마지막에 노드 추가하기

 

 

 

배열과 빗대어서 생각해보셈!

append의 경우, 연결리스트의 가장 마지막 노드를 찾아내어 그 뒤에 추가해주면 되는데,

노드의 가장 마지막을 찾아내는 방법은 head 노드부터 순회하며,

node.next가 nil인 경우를 찾으면 됨!

(가장 마지막 노드는 연결 할 다음 노드가 없으니까)

 

 

func append(data: T?) {
    
    //head가 없는 경우 Node를 생성 후 head로 지정해준다
    if head == nil {
        head = Node(data: data)
        return
    }
    
    var node = head
    while node?.next != nil {
        node = node?.next
    }
    node?.next = Node(data: data)
}

 

 

이렇게 해주면 되겠군!

 

 

 

2-4. insert(data:at:) : 연결 리스트 중간에 노드 추가하기

 

 

 

연결 리스트의 경우, 중간에 노드를 추가할 수 있지만,

배열과 달리 index가 없기 때문에 만약 index로 추가하고 싶다면

다음과 같이 직접 구현해서 해줄 수는 있음

(이런 식으로 연결리스트는 추가 및 삭제 구현이 귀찮다는 단점이 있음)

 

 

func insert(data: T?, at index: Int) {
    
    //head가 없는 경우 Node를 생성 후 head로 지정한다
    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
    node?.next = Node(data: data)
    node?.next?.next = nextNode
    
}

 

 

이렇게 구현하면 될 것 같음!

만약 찾는 index가 node의 범위를 넘어가면, 가장 마지막에 추가해줬음

중간에 삽입하는 경우 이런 식으로 노드 간 연결만 바꿔주면 되니까

원하는 삽입 방식으로 알아서 커스텀하게 구현해도 될듯 :)

 

 

 

2-5. removeLast : 연결 리스트 맨 마지막 노드 삭제하기

 

 

 

그림으로 보면 delete할 노드의 바로 이전 노드의 next를 nil로 바꿔주는 것을 볼 수 있음!

코드로 보면 다음과 같음 :)

일부러 이해하기 편하라고 배열하고 메서드 이름 같게해서 보고 있음!

 

 

func removeLast() {
    
    if head == nil { return }     // head를 삭제하는 경우
    if head?.next == nil {
        head = nil
        return
    }
    
    var node = head
    while node?.next?.next != nil {
        node = node?.next
    }
    
    node?.next = node?.next?.next
    
}

 

 

왜 nil이 아닌 삭제할 node.next를 지정하냐면,

어차피 맨 마지막 노드의 next는 nil일테니까 :)

 

 

 

2-6. remove(at:)연결 리스트 중간 노드 삭제하기

 

 

 

이또한 마찬가지로,

그림으로 보면 delete할 노드의 바로 이전 노드의 next를

delete 할 노드의 next로 바꿔주면 되는 것을 볼 수 있음!

 

 

func remove(at index: Int) {
    
    if head == nil { return }
    
    // head를 삭제하는 경우
    if index == 0 || head?.next == nil {
        head = head?.next
        return
    }
    
    var node = head
    for _ in 0..<(index - 1) {
        if node?.next?.next == nil { break }
        node = node?.next
    }
    
    node?.next = node?.next?.next
    
}

 

 

이렇게 구현하면 될 것 같음!

만약 삭제하려는 index가 node의 범위를 넘어가면, 가장 마지막을 삭제했음

 

 

 

2-7. searchNode(from:) : data로 노드 찾기

 

 

 

이번엔 노드에 저장된 데이터를 직접 검색해서,

해당 노드를 반환하는 기능을 만들어볼 것임 :)

앞에서 지겹게 봤듯이 head에서부터 순차적으로 찾아야 함!!

 

 

func searchNode(from data: T?) -> Node<T>? {
    
    if head == nil { return nil }
    
    var node = head
    while node?.next != nil {
        if node?.data == data { break; }
        node = node?.next
    }
    
    return node
}

 

 

이렇게 짜면 되겠군 :)

자 근데 이렇게 짜면 에러가 뜸

 

 

 

 

그 이유는,

바로 search에서 node?.data와 data를 비교해야 하는데,

이 둘은 현재 제네릭으로 선언되어 있어 자료형을 런타임 전까진 모를 뿐더러,

따라서 Equatable이란 프로토콜이 채택되지 않은 자료형일 수도 있기 떄문에

 

이 둘을 == 으로 비교할 수 없다!!! 라고 하는 것임

따라서, 만약 searchNode 메서드를 위와 같이 만들고 싶다면

 

 

 

 

이렇게 LinkedList 클래스에 Equatable 프로토콜을 채택해주면 됨!! 

(파이썬은 그냥 되지만 =_=)

 

 

 

 

3. 단방향 연결 리스트를 보완할 순 없을까

 

단방향 연결 리스트에 대해 지금까지 공부 했는데,

가장 큰 문제점은 바로 탐색할 때 있음!

 

만약 100,000개의 노드를 가지는 연결 리스트가 있을 때,

노드를 추가할 때마다 head에서부터 맨 마지막 100,000번째 노드까지

매번 순차적으로 탐색 해야함.. 뷁..

 

따라서 이런 문제점을 보완하고자 나온 것이

바로 다음 포스팅에서 배울 양방향 연결 리스트 라는 것임!!

 

이 양방향 연결 리스트는 다음과 같이

 

 

 

가장 첫 노드를 가리키는 head 뿐 아니라, 가장 마지막 노드를 가리키는 tail도 갖고 있어서,

이런 식으로 양방향으로 접근할 수 있는 방법임!

 

이는 다음 포스팅에서 자세히 공부하겠음 :))))

 

 

 

 

.

.

.

 

이렇게 하면 단방향 연결 리스트가 끝났습니다!!!!1

Swift로 구현해보며 포스팅 해본 것인데..! 흠..~~

이게 10000% 맞는 코드인지 확신이 서진 않네영 :)

옛날에 C언어로 했을 때 생각하면서 했고 테스트 했을 땐 모두 정상 작동 했는데...!

 

혹시라도 잘못된 내용이나 피드백은 언제나 댓글 달아주세요 🤤

 

아, 그리고 저처럼 python으로 공부하고 Swift로 공부하시는 분들

remove 함수 호출할 때 왜 , del 메서드 호출 안 해주냐 할 수도 있는데!

Swift에선 우리가 Node를 Class로 구현 했기 때문에 ARC에 의해

참조만 끊어주면 알아서 메모리에서 해제되기 때문입니다..!

스윞 만세~~~~

 

다음 편에선 

양방향 연결 리스트에 대해서 다뤄보겠습니다 :)

그럼 20,000