[Linked List 연결리스트] 배열과의 차이점 / 그리고 Swift로 구현 해보기

배열이란? (Array)

프로그래밍에서 데이터 값을 저장하는 공간을 변수라고 부른다.

독립적인 한 개의 값만 저장할 때는 변수를 사용하지만, 연관된 데이터를 한꺼번에 묶어서 저장할 때는 주로 배열을 사용한다.

언어마다 배열을 다루는 함수나 방법들이 다 다르지만 일반적으로 배열은 연속된 물리적 메모리 공간에 데이터를 저장한다.

데이터에 접근하기 위해서는 인덱스(데이터의 위치)로 접근한다.

인덱스를 통해 데이터에 접근하는 시간 복잡도는 O(1) 이 소요된다. => 빠르다.

 

배열은 새로운 값을 삽입하려면 삽입하고자 하는 위치보다 뒤에 있는 원소들을 한 칸씩 뒤로 밀어주어 삽입할 공간을 확보해주어야 한다. 또한 중간에 있는 값을 삭제하려면 뒤에 이어지는 원소들을 한 칸씩 앞으로 당겨서 삭제된 빈 공간을 채워 주어야 하는 번거로움이 있다.

 

즉, 배열은 탐색 및 정렬에는 유리하지만, 삽입과 삭제에는 불리한 자료구조라고 할 수 있다.

 

연결 리스트란? (Linked List)

연결 리스트를 사용하면 배열의 삽입과 삭제에서 느꼈던 불편함을 해소할 수 있다.

연결 리스트에도 이중 연결 리스트, 순환 연결 리스트 등 다양한 종류가 있지만

일반적으로는 단순 연결리스트로, 노드들이 자신 다음에 이어질 값의 주소 값을 가지고 있는 형태이다.

 

단순 연결리스트의 Node 구현

연결 리스트를 구현하기 위해서는 Node를 먼저 구현해야 한다.

class Node<T> {
    var value: T
    var next: Node?

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

<T>라고 작성한 부분은 제네릭 타입(Generic Type) 문법이다. 유연하고 재사용성을 높일 수 있는 방법이다.

제네릭으로 선언하면 Int 형 값을 가지는 노드, Double 형 값을 가지는 노드, 혹은 Class Type 노드도 따로 구현할 필요가 없다.

Node 객체를 생성할 때 저 <T> 자리에 원하는 타입을 작성하면 된다.

Node<Int> 또는 Node<Person> 이런 식으로 말이다! (Person이라는 구조체 혹은 클래스가 있다고 가정한다.)

value는 해당 노드가 갖는 유의미한 값을 저장하는 프로퍼티이다.

next는 해당 노드 다음에 이어질 노드를 가리키는 프로퍼티이다. 옵셔널로 지정하여, 뒤에 아무 노드도 오지 않을 경우 nil이 저장된다.

 

단순 연결 리스트 구현

단순 연결 리스트에는 가장 첫번째 요소를 가리키는 head와 마지막 요소를 가리키는 tail을 지정해주었다.

class LinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?

    init(head: Node<T>? = nil) {
        self.head = head
        self.tail = head
    }
}

 

단순 연결리스트에는 다음과 같은 기능이 필요하다.

* size() 연결리스트의 크기를 구한다.

* findNode(at:) 특정 위치에 있는 노드를 반환한다. (찾고자 하는 위치가 리스트의 크기보다 클 경우 nil 반환)

*append(_:) 연결리스트의 맨 뒤에 새로운 노드를 추가한다.

* insert(_: at:) 특정 위치에 새로운 노드를 삽입한다. (삽입하고자 하는 위치가 리스트의 크기보다 클 경우 맨 뒤에 추가)

* remove(at:) 특정 위치에 있는 노드를 삭제한다.(삭제하고자 하는 위치가 리스트의 크기보다 클 경우 아무 동작하지 않음)

* contains(_:) 특정 값을 가지는 노드를 포함하고 있는지 탐색하여 Bool 값을 반환한다.

* firstIndex(of:) 특정 값을 가지는 노드의 인덱스 Int? 값을 반환한다.

 

<size>

head가 nil이라면 노드가 1개도 없으므로 0을 반환한다.

연결 리스트의 head부터 next 노드를 탐색하면서 카운트를 더해준다.

next가 nil에 도달했을 때 카운트를 반환한다.

func size() -> Int {
    guard var node = self.head else {
        return 0
    }
    var count = 0
    while node.next != nil {
        count += 1
        node = node.next!
    }
    return count
}

 

<findNode>

head가 nil이면 아무 노드도 없으므로 nil을 반환한다.

for문으로 1부터 index까지 반복문을 돌린다. 반복문에서는 노드의 next를 계속 탐색한다.

node의 next가 nil일 경우 index위치까지 도달하기 전에 리스트가 끝났다는 말이므로, nil을 반환한다.

반복문이 종료되면 찾은 노드를 반환한다.

func findNode(at index: Int) -> Node<T>? {
    guard var node = self.head else {
        return nil
    }
    for _ in 1...index {
        guard let nextNode = node.next else {
            return nil
        }
        node = nextNode
    }
    return node
}

 

<append>

tail이 nil이 아니라면 tail.next를 nextNode로 바꿔준다. 그리고 tail을 tail.next로 바꿔준다.

tail이 nil이면 당연히 head도 nil일테고, 그러면 head와 tail을 newNode로 저장해주면 된다.

func append(_ newNode: Node<T>) {
    if let tail = self.tail {
        tail.next = newNode
        self.tail = tail.next
    } else {
        self.head = newNode
        self.tail = newNode
    }
}

 

<insert>

만약 삽입하고자 하는 위치가 연결 리스트의 길이보다 클 경우, 연결리스트의 맨 뒤에 새로운 노드를 삽입해준다.

연결 리스트에서 새로운 노드를 삽입하기 위해서는 먼저 삽입할 위치보다 한 칸 앞에 있는 노드를 찾아야 한다.

한칸 앞의 노트를 frontNode라고 하면,

newNode.next를 frontNode.next로 바꿔주고 frontNode.next를 newNode로 바꿔주면 된다.

func insert(_ newNode: Node<T>, at index: Int) {
    // head가 nil이라면 head와 tail에 모두 newNode를 저장한다.
    if self.head == nil {
        self.head = newNode
        self.tail = newNode
        return
    }

    // index-1 위치의 노드를 찾을 수 없다면 연결리스트의 맨 뒤에 새로운 노드(newNode)를 붙여 주면 된다.
    guard let frontNode = findNode(at: index-1) else {
        self.tail?.next = newNode
        self.tail = newNode
        return
    }

    // index-1 위치의 노드(frontNode) 다음이 nil이라면 index-1 위치의 노드(frontNode)가 tail이라는 뜻이다.
    // index-1 위치의 노드(frontNode) 뒤에 새로운 노드(newNode)를 붙여주고 tail을 새로운 노드(newNode)로 갱신해주면 된다.
    guard let nextNode = frontNode.next else {
        frontNode.next = newNode
        self.tail = newNode
        return
    }

    // index 위치의 노드(nextNode)는 새로운 노드의 다음으로 붙이고,
    // 새로운 노드는 index-1 위치의 노드(frontNode)의 다음으로 붙인다.
    newNode.next = nextNode
    frontNode.next = newNode
}

 

<remove>

insert와 비슷하게, 삭제하고자 하는 위치보다 한 칸 앞에 있는 노드(frontNode)를 먼저 찾아야 한다.

frontNode.next를 removeNode.next로 바꿔주면 된다.

더 이상 사용하지 않는 인스턴스인 removeNode의 메모리 해제는 신경 쓰지 않아도 된다. Swift의 ARC 특성 때문이다.

func remove(at index: Int) {
    // index-1 위치의 노드(frontNode)를 찾을 수 없는 경우 -> 아무 동작 하지 않음
    guard let frontNode = findNode(at: index-1) else {
        return
    }

    // index-1 위치의 노드(frontNode)가 마지막 노드인 경우 -> 아무 동작 하지 않음
    guard let removeNode = frontNode.next else {
        return
    }

    // index 위치의 노드(removeNode)가 마지막 노드인 경우 -> tail에 frontNode를 저장함
    guard let nextNode = removeNode.next else {
        frontNode.next = nil
        self.tail = frontNode
        return
    }

    // index 위치의 노드(removeNode)가 마지막 노드가 아닌 경우
    frontNode.next = nextNode
}

 

<contains>

연결 리스트에 찾고자 하는 값과 node.value 값이 같은 노드가 있다면 true를 반환해야 한다.

모든 노드를 반복문으로 탐색하면서 node.value와 파라미터 value 값을 비교해 주어야 한다.

func contains(_ value: T) -> Bool {
    guard var node = self.head else {
        return false
    }

    while true {
        if node.value == value { // ERROR!!
            return true
        }
        guard let next = node.next else {
            return false
        }
        node = next
    }
}

하지만 7번째 줄에서 에러가 난다. Generic 타입인 T 는 equal(==) 연산을 할 수 없기 때문이다.

스위프트의 모든 기본 타입에서는 == 연산을 사용할 수 있는데, 그 이유는 Swift의 모든 기본 타입이 Equatalbe 프로토콜을 준수하고 있기 때문이다. 이 프로토콜을 따르면 항상 == 연산자를 구현하고 있다는 보장이 된다.

Generic T 타입이 Equatable 프로토콜을 따르고 있다는 제약을 걸어주면 위와 같은 상황에서도 == 연산자를 사용 가능하게 된다.

클래스의 선언부로 돌아가서 T가 Equatable을 준수함을 명시하자.

class LinkedList<T: Equatable> {
    ...
}

 

<firstIndex>

기본적인 로직은 contains 함수와 비슷하지만, 반복문을 돌 때마다 count 를 증가시켜 원하는 값을 찾았을 때 count를 반환해 주면 된다.

만약 값을 찾을 수 없다면 nil을 반환해준다.

func firstIndex(of value: T) -> Int? {
    guard var node = self.head else {
        return nil
    }
    var count = 0
    while true {
        if node.value == value {
            return count
        }
        guard let next = node.next else {
            return nil
        }
        node = next
        count += 1
    }
}

 

전체 코드 살펴보기

class Node<T: Equatable> {
    var value: T
    var next: Node?

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

class LinkedList<T: Equatable> {
    var head: Node<T>?
    var tail: Node<T>?

    init(head: Node<T>? = nil) {
        self.head = head
        self.tail = head
    }

    func size() -> Int {
        guard var node = self.head else {
            return 0
        }
        var count = 0
        while node.next != nil {
            count += 1
            node = node.next!
        }
        return count
    }


    func findNode(at index: Int) -> Node<T>? {
        guard var node = self.head else {
            return nil
        }
        for _ in 1...index {
            guard let nextNode = node.next else {
                return nil
            }
            node = nextNode
        }
        return node
    }

    func append(_ newNode: Node<T>) {
        if let tail = self.tail {
            tail.next = newNode
            self.tail = tail.next
        } else {
            self.head = newNode
            self.tail = newNode
        }
    }

    func insert(_ newNode: Node<T>, at index: Int) {
        if self.head == nil {
            self.head = newNode
            self.tail = newNode
            return
        }
        guard let frontNode = findNode(at: index-1) else {
            self.tail?.next = newNode
            self.tail = newNode
            return
        }
        guard let nextNode = frontNode.next else {
            frontNode.next = newNode
            self.tail = newNode
            return
        }
        newNode.next = nextNode
        frontNode.next = newNode
    }

    func remove(at index: Int) {
        guard let frontNode = findNode(at: index-1) else {
            return
        }
        guard let removeNode = frontNode.next else {
            return
        }
        guard let nextNode = removeNode.next else {
            frontNode.next = nil
            self.tail = frontNode
            return
        }
        frontNode.next = nextNode
    }

    func contains(_ value: T) -> Bool {
        guard var node = self.head else {
            return false
        }
        while true {
            if node.value == value {
                return true
            }
            guard let next = node.next else {
                return false
            }
            node = next
        }
    }

    func firstIndex(of value: T) -> Int? {
        guard var node = self.head else {
            return nil
        }
        var count = 0
        while true {
            if node.value == value {
                return count
            }
            guard let next = node.next else {
                return nil
            }
            node = next
            count += 1
        }
    }
}

 

 

* 잘못된 부분의 지적이나 개선할 점에 대한 조언은 언제나 환영입니다.