[Swift] 자료구조 - 단방향 / 양방향 연결 리스트(Linked List)

안녕하세요~

 

오늘은 큐에 이어서 연결리스트에 대해서 정리하려고 합니다 : )

 

[ Queue 포스팅 ]

[Swift] 자료구조 - 큐(Queue)

 

 

---

 

연결리스트가 필요한 이유

연결리스트를 사용하는 이유는 여러 가지가 있겠지만 

배열과 비교하면서 설명해보겠습니다.

 

배열은 임의 접근(Random Acess)이 가능하기 때문에

인덱스를 통해 값에 바로 접근할 수 있습니다.

 

하지만 삽입, 삭제의 경우에는 

배열을 재배치해야 하는 로직이 추가되게 됩니다.

 

예를 들어 다음과 같은 배열이 있다고 가정해 봅시다.

 

원소	1	3	5	7
인덱스	0	1	2	3

 

여기서 0번째 인덱스를 제거하게 되면 어떻게 될까요?

 

원소	?	3	5	7
인덱스	0	1	2	3

 

위와 같이 0번째 인덱스에는 아무런 값도 없게 됩니다. 

따라서 재배치과정이 필요하게 되는 것이죠.

 

이런 불편함을 보안하기 위해서 사용하는 것이 연결 리스트라고 생각하시면 됩니다.

 

단방향 연결 리스트

 

위의 그림에서 하나의 노드가 다른 노드를 가리키고 있는 게 보이실 겁니다.

그리고 마지막 노드는 다음 노드가 없기에 nli로 처리하게 됩니다.

이를 단방향으로 연결된 리스트라고 합니다.

노드(node)란 리스트에서 데이터를 저장하는 단위로 데이터와 이전, 이후 혹은 두 방향의 노드를 가리키는 포인터로 이루어진 객체입니다.

 

여기서 A데이터를 제거한다고 하면 

바로 Head 포인터만 B로 넘겨주면 됩니다.

물론 A노드는 메모리해제를 해주어야 하고요.

 

재배치가 필요하지 않으니

배열보다는 삽입하거나 삭제할 때 시간복잡도 측면에서 이득을 취할 수 있게 되는 것입니다.

 

 

---

 

노드와 양방향 연결 리스트 구현

- 위에서 단방향 연결리스트를 소개했는데 양방향 리스트의 경우에는 다음이 아닌 이전을 가리키는 노드도 존재합니다. 이름 그대로 앞, 뒤 양쪽 방향 모두를 알 수 있게 되는 것입니다..

 

1. 노드(Node)

// 노드
class Node<T> {
    // 노드에는 데이터와 앞, 뒤를 가르키는 노드가 존재!
    var prev: Node?
    var data: T? 
    var next: Node?
    
    init(data: T?, prev: Node? = nil, next: Node? = nil) {
        self.prev = prev
        self.data = data
        self.next = next
    }
}

 

- 양방향 연결리스트에서의 노드는 위와 같이 이전과 이후를 가르키는 prev, next 가 존재합니다.

 

2. 양방향 연결 리스트(Linked List)

- 연결리스트는 메모리 공간에서 데이터들을 연결해 주는 자료구조이기 때문에 양방향 연결리스트에서는 가장 앞의 노드를 가르키는 head와 가장 뒤에 노드를 가르키는 tail 노드가 있어야합니다.  이는 임의 접근이 가능했던 배열과 다르게 순차 접근을 해야하는 이유이기도 합니다.

 

따라서 다음과 같이 만들 수 있습니다.

// 연결 리스트
class LinkedList<T> {
    // 연결리스트의 첫번째 노드를 가르키는 head 프로퍼티
    var head: Node<T>?
    // 연결리스트의 마지막 노드를 가르키는 tail 프로퍼티
    var tail: Node<T>?
    
    init(head: Node<T>? = nil, tail: Node<T>? = nil) {
    	self.head = head
        self.tail = tail
    }
}

데이터를 추가하고 삭제하고 탐색하는 방법까지 알아봅시다.

 

3.  연결 리스트의 크기, 탐색,  삽입, 삭제

3.1 크기

- 연결 리스트의 크기 즉, 데이터의 개수를 구하는 메서드입니다.

- 마지막 노드의 경우 다음 데이터를 가르키는 노드가 없으므로 nil인 점을 이용해 사이즈를 확인할 수 있습니다.

 

func size() -> Int {
    // 노드가 존재하는지!
    guard var node = self.head else {
        return 0
    }
    var count = 0
    // 마지막 노드는 nil을 가지고 있는 것을 활용해
    // 탐색 및 개수를 카운트 합니다!
    while node.next != nil {
        count += 1
        node = node.next!
    }
    return count
}

3.2 탐색

- 연결 리스트의 크기를 구하면서 이걸 이용하면 특정한 순서의 노드를 확인할 수 있겠다고 생각했을 수 있습니다. 그 점을 이용해서 다음과 같이 확인할 수 있습니다.

func findNode(at index: Int) -> Node<T>? {
    guard var node = self.head else {
        return nil
    }
    // index에 해당하는 값까지 반복해서 다음 노드로 탐색
    for _ in 1...index {
        guard let nextNode = node.next else {
            return nil
        }
        node = nextNode
    }
    return node
}

- 반대로 특정한 값을 가지고 있는 노드도 찾아볼 수 있습니다.

func firstIndex(of data: T) -> Int? {
    guard var node = self.head else {
        return nil
    }
    var count = 0
    while true {
        // 특정한 데이터의 값을 가지고 있는 노드가
        // 몇번째에 있는지 확인 후 반환!
        if node.data == data {
            return count
        }
        guard let next = node.next else {
            return nil
        }
        node = next
        count += 1
    }
}

 

중요 : 위에서 node.data = data에서 오류가 발생합니다. 바로 제네릭의 경우 "==" 연산자를 사용할 수 없기 때문인데 기존의 LinkedList 클래스에서 LinkedList <T: Equatable>로 바꾸어야 사용할 수 있게 됩니다.

 

3.3 추가

- 새롭게 생성된 노드와 원하는 위치를 입력받고 앞의 노드와 뒤의 노드의 유무를 판별한 다음 연결해주는 메서드입니다. 자세한 내용은 주석을 통해 입력해 두었습니다.

func insert(_ newNode: Node<T>, at index: Int) {
    // head가 nil이라면 아직 아무것도 없다는 거겠죠?
    // 따라서 head와 tail에 새로운 노드(newNode)를 저장해 주면 됩니다! 
    if self.head == nil {
        self.head = newNode
        self.tail = newNode
        return
    }

    // 만약에 앞의 노드를 찾을 수 없다면 즉, 기존의 연결 리스트의 길이보다 긴
    // 인덱스 값이 들어오게 된 것 이기 때문에 
    // 분기처리하거나 가장 뒤에 붙여주면 됩니다유 / 여기서는 가장 뒤에 붙여줬습니당
    guard let prevNode = findNode(at: index-1) else {
        self.tail?.next = newNode 
        self.tail = newNode
        return
    }
	
    guard let nextNode = prevNode.next else {
    	// prevNode 다음이 nil이라면 tail이되기 때문에 바로 다음으로 연결!
        prevNode.next = newNode
        self.tail = newNode
        return
    }
    
    /*
    위의 과정을 모두 거쳤다면
    newNode의 다음은 nextNode가 되고
    prevNode(하나 이전)의 다음은 newNode가 된다.
    prevNode -> nextNode 였던 연결리스트에서 해당 인덱스에 들어오니
    이 두 노드 사이였고
    즉, prevNode -> newNode -> nextNode가 되는 것!
    */
    newNode.next = nextNode
    prevNode.next = newNode
}

 

3.4 삭제

- 삽입과 과정이 비슷합니다. 이전의 노드를 찾고 시작하시면 됩니다.

func remove(at index: Int) {
    // prevNode가 없다면? 즉, 이전의 노드가 존재하지 않는 다는 말!
    // 따라서 할게 없습니당..
    guard let prevNode = findNode(at: index-1) else {
        return
    }

    // prevNode가 마지막 노드라면 위와 마찬가지겠죠!
    // 할게 없습니당..
    guard let removeNode = prevNode.next else {
        return
    }

    // index 위치의 노드(removeNode)가 마지막 노드라면?
    // 이전의 노드가 가르킬 것은 없으니 nil
    // tail의 경우에는 이전의 노드를 가르키고 있어야겠쥬!
    guard let nextNode = removeNode.next else {
        prevNode.next = nil
        self.tail = prevNode
        return
    }

    // index 위치의 노드(removeNode)가 마지막 노드가 아니라면?
    // 당연히 이전의 노드 다음노드가 제거될 노드의 다음 노드를 가르키는!!
    // 즉, prevtNode -> removeNode -> nextNode 상태에서
    // removeNode가 제거 되게 하려면
    // prevNode.next = nextNode가 되야하는 것!
    prevNode.next = nextNode
}

 

 

다음 포스팅은 해시 테이블입니다.

 

[Swift] 자료구조 - 해시 테이블(Hash Table)

 

그럼 이만 👋🏻 👋🏻 👋🏻

 

---

 

참고한 링크들입니다.

감시합니다 👏

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

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