[DataStructure] 링크드 리스트를 Swift로 구현하기

https://m.hanbit.co.kr/store/books/book_view.html?p_code=B3450156021
이 글은 책 '뇌를 자극하는 알고리즘' 에서 배운 내용을 적극 참고하고 있습니다.
또한, 모든 자료구조 및 알고리즘은 Swift로 구현하고 있음을 먼저 알립니다.

뇌를 자극하는 알고리즘

 

0. 서론
배열을 알고 계신가요?
같은 타입의 데이터가 메모리에 연속적으로 저장되어 있는 자료구조입니다.
메모리에 연속적으로 저장되어 있다는 특징으로 인해 빠른 접근속도에 강점을 가지는것이 특징이기도 합니다.
그러나, 초기에 할당한 크기 만큼만 사용할 수 있으며 이를 넘어서는 크기의 자료를 저장하기 위해선
더 큰 공간을 할당하여 데이터를 이주시키는 등 추가적인 작업이 필요한 것 또한 특징입니다.

그렇다면, 여러 데이터를 연속적으로 저장할 수 있으면서도, 데이터 이주등의 번거로운 작업에서 벗어날 수 있는 자료구조는 없을까요?
다 알고 계시겠지만, 링크드 리스트는 이에 적합한 자료구조 입니다.
하나의 데이터에 다음 데이터를 가리키는 정보가 담겨있어, 계속해서 데이터를 꼬리에 꼬리를 무는 모습으로 주렁주렁 달 수 있죠.

링크드 리스트에 대한 소개는 이쯤 끝내고, 이에대한 구현을 구조정의-삽입-탐색-삭제 순으로 진행해보도록 하겠습니다.

1. 구조 정의

링크드 리스트는 데이터와 다음 자료에 대한 위치정보로 이루어진 덩어리가, 여러 꼬리를 물어 주렁주렁 달려있는 형태입니다.
따라서 이 덩어리를 '노드' 라고 부르고, 다음과 같이 정의해보도록 하죠.

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

 

제네릭을 모르시는 분은 Swift-제네릭을 공부하고 오시길 바랍니다.
노드는 데이터와 다음 노드의 위치를 알고 있어야 하므로 코드와 같은 멤버를 갖습니다.
이제 이를 줄줄이 엮어볼까요?
비엔나 소세지에도 처음 소세지가 있기 마련이니, 이것을 머리라고 해 둘까요.
더 생각할 필요 없이, 지금까지 말한 정보를 토대로 간단하게 구현해보도록 하겠습니다.

class SingleLinkedList<T>{
    var head: Node<T>?
}

자, head(머리)를 가진 링크드 리스트가 완성되었습니다!
이제 여러분은 원하는 만큼 자료들을 모아 보관할 수 있게 됐습니다!
그런데, 이걸 어떻게 쓰냐고요?
다행입니다. 어디에 써야하는지 보다 훨씬 간단한 질문이군요. 차근차근 알아가보도록 합시다.

2. 삽입

기차놀이를 생각해 봅시다.
이미 기차놀이를 하고 있는 사람을 하나 더 늘리고 싶다면, 다음 중 한가지 경우일 겁니다.

1. 맨 첫 사람 앞에 추가한다.
2. 사람과 사람 사이에 추가한다.
3. 맨 뒷 사람 뒤에 추가한다.

1번을 먼저 살펴보면, 이미 기차놀이를 하고 있는 사람이 있거나 없을 수 있겠군요! 마치 슈뢰딩거의 고양이 같습니다.
그러나 컴퓨터는 이런 유머에 능숙하지 못하므로, 두가지 경우에 대해 나눠 알려줘야 합니다.

    ///리스트의 처음에 노드 추가
    @discardableResult
    func insertNodeAtFirst(_ newNode: Node<T>, _ idx: Int)->Node<T>?{
        if self.head == nil{
            self.head = newNode
            return newNode
        }
        newNode.nextNode = self.head
        self.head = newNode
        return newNode
    }

헤드가 비어있다면 새 노드를 헤드로, 헤드가 이미 있다면 헤드에 있는 노드를 새 노드의 다음 노드로 달아놓은 후
링크드 리스트의 자체적인 헤드는 새 노드로 변경하면 끝납니다.

2번을 살펴볼까요. 타자치기 힘드니 기차놀이 비유는 이쯤 그만두어도 이해하실거라 생각하겠습니다.
노드와 노드 사이에 새 노드를 추가하는 경우에, 빈 링크드 리스트는 새 노드가 헤드 노드가 되겠군요.
삽입하려는 위치가 존재하지 않다면 맨 마지막에 달거나 달수 없도록 할 수도 있겠습니다.
이 경우에 달지 않고 nil을 반환하도록 해 볼까요?

    func insertNodeAt(_ newNode: Node<T>, _ idx: Int)->Node<T>?{
        if self.head == nil{
            self.head = newNode
            return newNode
        }
        var currentNode = head
        for _ in 0..<(idx-1){
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        newNode.nextNode = currentNode?.nextNode
        currentNode?.nextNode = newNode
        
        return newNode
    }

이제 리스트의 마지막에 노드를 추가하는 함수를 만들어 보겠습니다.
특정 위치까지 도달한다는 조건이 없으므로, for문을 while문으로 바꾼다고 생각하면 쉽겠네요!

    ///리스트 마지막에 노드 추가
    @discardableResult
    func appendNode(_ newNode: Node<T>)->Node<T>{
        if let head = self.head{
            var tail = head
            while(tail.nextNode != nil){
                tail = tail.nextNode!
            }
            tail.nextNode = newNode
        }else{
            self.head = newNode
        }
        return newNode
    }

 

2. 탐색

사실 삽입에서 필요로하는 모든 소양을 여러분께서는 경험하셨습니다.
'특정 위치에 접근하여, 지정된 작업을 수행한다' 가 링크드 리스트의 모든 연산에 공통된 부분이기 때문이지요.
그렇다면, 노드를 삽입하는 각각의 함수를 조금 수정하면 금방 구현할 수 있겠군요!

    ///리스트의 특정 위치의 노드 반환
    func getNodeAt(_ idx: Int)->Node<T>?{
        if self.head == nil {return nil}
        var currentNode = head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        return currentNode
    }
    ///리스트의 첫 위치의 노드 반환
    func getNodeAtFirst()->Node<T>?{
        if self.head == nil{return nil}
        return self.head
    }
    ///리스트 마지막 위치의 노드 반환
    func getLastNode()->Node<T>?{
        if self.head == nil{return nil}
        var currentNode = self.head
        while(currentNode != nil){
            currentNode = currentNode?.nextNode
        }
        return currentNode
    }

 

3. 삭제

삭제 또한 삽입의 응용입니다. 삭제할 노드의 직전 노드까지 접근하여, nil을 할당하면 나머지는 똑똑한 ARC가 처리할 예정이죠.

    ///리스트의 첫 노드 제거
    @discardableResult
    func removeFirst()->Node<T>?{
        if self.head == nil{return nil}
        self.head = self.head?.nextNode
        return head
    }
    ///리스트 마지막 노드 제거
    @discardableResult
    func removeLastNode()->Node<T>?{
        if self.head == nil{
            print("List is empty")
            return nil
        }
        
        if self.head?.nextNode == nil {
            var removeNode = self.head
            self.head = nil
            return removeNode
        }
        
        var currentNode = self.head
        while(currentNode?.nextNode?.nextNode != nil){
            if currentNode?.nextNode == nil {break}
            currentNode = currentNode?.nextNode
        }
        var removedNode = currentNode?.nextNode
        currentNode?.nextNode = nil
        return removedNode
        }
    //리스트의 특정위치의 노드 제거
    @discardableResult
    func removeNodeAt(_ idx: Int)->Node<T>?{
        if self.head == nil{
            print("List is empty")
            return nil
        }
        var currentNode = self.head
        for _ in 0..<idx-1{
            if currentNode?.nextNode?.nextNode == nil {break}
            currentNode = currentNode?.nextNode
        }
        let removeNode = currentNode?.nextNode
        currentNode?.nextNode = currentNode?.nextNode?.nextNode
        return removeNode
    }

만약, 사용자가 입력한 리스트의 인덱스의 위치에 노드가 없다면 마지막 노드를 삭제하는것으로 구현하였습니다만...
이 부분은 취향껏 nil을 반환하도록 구현하실 수 있겠네요!
이제 저 함수들을 SingleLinkedList 클래스에 담는것으로 코딩은 끝입니다.

4. 결론

오늘은 배열과 비슷하지만 다른 녀석, '링크드 리스트'에 대해 끄적여 보았습니다.
링크드 리스트는 배열에 비해 다음과 같은 장점을 가지고 있습니다.

• 새로운 노드의 추가/삽입/삭제가 쉽고 빠릅니다.
  링크드 리스트에 비해 배열은 요소를 삽입하거나 제거하기가 어렵습니다.
• 현재 노드의 다음 노드를 얻어오는 연산에서 발생하는 비용이 발생하지 않습니다.
  (라고 책에 적혀있으나, 매우 적다고 받아들였습니다)

이에 대비되는 단점은 다음과 같습니다.

• 특정 위치의 노드를 얻는데 드는 비용이 크고, 속도도 느립니다.
  배열은 상수 시간 ( O(1) ) 에 노드를 얻을 수 있는 반면, N개의 노드를 가진 리스트의 경우에 최작의 경우 N회의 탐색루프( O(n) )를 거쳐야 찾을 수 있습니다.
  
  
• 다음 노드를 가리키는 포인터를 위하여, 4byte의 메모리가 추가로 필요합니다. (C기준)
  (언어마다 다른 부분이고, Swift는 공식문서를 참고해 Node<Any>? 메모리를 찍어보았을 때 8바이트임을 확인하였습니다)
• print(MemoryLayout<Node<Any>?>.size) //8

이로써 링크드 리스트, 정확히 '싱글' 링크드 리스트의 간단한 구현이 마무리되었습니다.
몇몇 분들은 여러분은 클래스의 이름이 SingleLinkedList인 것과, 삽입 - 삭제 시에 타겟 노드가 아닌 타겟 직전의 노드에 접근하여
일련의 명령을 처리하는 것에 위화감과 불편함을 느끼셨을거라고 생각합니다. 저만 그런가요?
그다지 놀랍지는 않지만, 많은 사람들이 불편함을 느낀 것 같습니다. '더블' 링크드 리스트가 세상에 탄생한 것을 보면 말이죠!

다음 글에서는 더블 링크드 리스트에 대해 얘기하고, 구현해보도록 하는 시간을 갖겠습니다.
읽어주셔서 감사합니다!

(다음 글 - https://bpeeper.tistory.com/28)

[DataStructure] 이중 링크드 리스트를 Swift로 구현하기

*소스코드 전문

//
//  SingleLinkedList.swift
//  Swift-Practice
//
//  Created by Yune gim on 2024/03/20.
//

class SingleLinkedList<T>{
    var head: Node<T>?
    ///리스트의 특정 위치의 노드 반환
    func getNodeAt(_ idx: Int)->Node<T>?{
        if self.head == nil {return nil}
        var currentNode = head
        for _ in 0..<idx{
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        return currentNode
    }
    ///리스트의 첫 위치의 노드 반환
    func getNodeAtFirst()->Node<T>?{
        if self.head == nil{return nil}
        return self.head
    }
    ///리스트 마지막 위치의 노드 반환
    func getLastNode()->Node<T>?{
        if self.head == nil{return nil}
        var currentNode = self.head
        while(currentNode != nil){
            currentNode = currentNode?.nextNode
        }
        return currentNode
    }
    ///리스트의 처음에 노드 추가
    @discardableResult
    func insertNodeAtFirst(_ newNode: Node<T>, _ idx: Int)->Node<T>?{
        if self.head == nil{
            self.head = newNode
            return newNode
        }
        newNode.nextNode = self.head
        self.head = newNode
        return newNode
    }
    ///리스트의 중간에 노드 추가
    @discardableResult
    func insertNodeAt(_ newNode: Node<T>, _ idx: Int)->Node<T>?{
        if self.head == nil{
            self.head = newNode
            return newNode
        }
        var currentNode = head
        for _ in 0..<(idx-1){
            if currentNode == nil {return nil}
            currentNode = currentNode?.nextNode
        }
        newNode.nextNode = currentNode?.nextNode
        currentNode?.nextNode = newNode
        
        return newNode
    }
    ///리스트 마지막에 노드 추가
    @discardableResult
    func appendNode(_ newNode: Node<T>)->Node<T>{
        if let head = self.head{
            var tail = head
            while(tail.nextNode != nil){
                tail = tail.nextNode!
            }
            tail.nextNode = newNode
        }else{
            self.head = newNode
        }
        return newNode
    }
    ///리스트의 첫 노드 제거
    @discardableResult
    func removeFirst()->Node<T>?{
        if self.head == nil{return nil}
        self.head = self.head?.nextNode
        return head
    }
    ///리스트 마지막 노드 제거
    @discardableResult
    func removeLastNode()->Node<T>?{
        if self.head == nil{
            print("List is empty")
            return nil
        }
        
        if self.head?.nextNode == nil {
            var removeNode = self.head
            self.head = nil
            return removeNode
        }
        
        var currentNode = self.head
        while(currentNode?.nextNode?.nextNode != nil){
            if currentNode?.nextNode == nil {break}
            currentNode = currentNode?.nextNode
        }
        var removedNode = currentNode?.nextNode
        currentNode?.nextNode = nil
        return removedNode
        }
    //리스트의 특정위치의 노드 제거
    @discardableResult
    func removeNodeAt(_ idx: Int)->Node<T>?{
        if self.head == nil{
            print("List is empty")
            return nil
        }
        var currentNode = self.head
        for _ in 0..<idx-1{
            if currentNode?.nextNode?.nextNode == nil {break}
            currentNode = currentNode?.nextNode
        }
        let removeNode = currentNode?.nextNode
        currentNode?.nextNode = currentNode?.nextNode?.nextNode
        return removeNode
    }
    func printAllNode(){
        var currentNode = self.head
        while(currentNode != nil){
            print(currentNode?.data)
            currentNode = currentNode?.nextNode
        }
    }
    
}