Data Structure) 링크드 리스트(Linked List) in Swift

< 출처 >

'How to Implement Linked List' - LBTA

(https://www.letsbuildthatapp.com/course_video?id=4292)

영상을 참고하였습니다.

 

 

그래프 탐색을 공부하기 위해 BFS, DFS 를 공부하다가

Queue 에 대해 알게 되었고 Queue 를 공부하다가

링크드 리스트를 갑자기 공부하게 되었다. ...뭐지?

 

아무튼 나의 첫 링크드 리스트, 시작해보자.

이번에 다뤄볼 리스트는 단방향 링크드 리스트이다.

 

출처 : 나무위키 - 연결 리스트

위의 사진에서 네모 한 칸(보라색 + 파란색)을 노드(Node)라 한다.

보라색 네모는 값을 가지고 있는 Data(or Value) 이고

파란색 네모는 다음 노드의 주소를 나타내고 있는 Pointer(포인터 or Next) 이다.

 

사진에서는 나오지 않았지만 저 가장 좌측에서 좌측 기준으로 첫 번째 네모를 가르키고 있는 놈은 HEAD 라 한다.

링크드 리스트에서 HEAD 의 주소를 잃어버리면 이 자료구조에 접근할 수 없다는 특징이 있다.

이 HEAD 에는 가장 첫 네모의 주소를 가지고 있으며, 이 첫 네모의 파란색 네모에 저장된 다음 노드의 주소를 통해서 

쭉쭉 오른쪽으로 이동한다. 

(아 HEAD 가 오른쪽으로 이동하면 다시 못 돌아온다는 특징이 있다!!)

 

위의 네모 한 칸(노드 하나)을 코드로 구현하면 다음과 같다.

티스토리 버전은 올리면 코드 색이 망가져서 두 가지 버전으로 올린다.

(작성할 땐 잘 뜨는데 왜 완료 누르면 티스토리 코드블록은 망가질까...)

class Node {
    let value: Int                      // Node의 값
    var next: Node?                     // 다음 Node의 주소를 가진 변수
    
    init(value: Int , next: Node?) {
        self.value = value
        self.next = next
    }
}

 

< 링크드 리스트와 노드 삽입 구현 >

 

자 이제 이 노드(Node)들과 헤드(HEAD)를 관리할 LinkedList 클래스를 살펴보자. (아래 코드를 플레이그라운드에 복사하세요)

class LinkedListLBTA {
    
    var head: Node?                     // 노드가 옵셔널인 이유는 처음에는 노드가 존재하지 않기 때문 !
    
    func insert(value: Int) {
        
        // 노드가 아무것도 존재하지 않을 때 -> 헤드가 첫 노드를 가리킬 수 있도록 한다.
        if head == nil {
            head = Node(value: value, next: nil)
            return
        }
        
        // 그렇지 않다면, 노드의 가장 마지막에 새로운 값을 가진 노드를 추가해줄 수 있도록 한다.
        var current = head
        while current?.next != nil {
            current = current?.next // 이 과정을 통해, current 가 가장 마지막 노드로 접근할 수 있게 되었다.
        }
        
        // 이제 마지막 노드에 도착한 current 의 next 에 새로운 노드를 추가해준다.
        current?.next = Node(value: value, next: nil)
    }
    
    func displayListItems() {           // Head의 위치를 기준으로 가장 마지막 노드까지 확인하는 부분
        var current = head
        while current != nil {          // current 가 nil 이 되는 경우는 헤드의 위치가 가장 마지막 노드라는 뜻.
            print(current?.value ?? "") // 모든 노드를 정상적으로 통과하는지 확인하기 위해 값을 프린트 한다.
            current = current?.next
        }
    }
    
}

head 변수는 자신이 가르킬 노드가 저장되기 위해서 타입이 Node? 로 선언되었다.

insert(value:) 메서드를 통해서 노드를 가장 마지막에 추가한다.

displayListItems() 메서드를 통해서 현재 head 로부터 가장 마지막 노드까지 진행한다. 진행 여부를 판단하기 위해 print() 문을 넣었다.

 

자 이제 LinkedListLBTA 인스턴스를 생성한 후, insert 함수를 통해서 노드를 추가한다.

그다음 displayListItems() 메서드를 통해 정상적으로 뜨는지 확인해 보자.

 

 

 

 

 

< 삭제(Deletion) 구현 >

 

 

이제 삭제(delete)에 대해 알아보고자 한다.

하나씩 살펴보자.

if head?.value == value {
   head = head?.next
 }

이 구문이 존재하는 이유는 첫 번째 노드를 제거하기 위함이다. (일단 if 문 아래 코드는 무시하자)

링크드 리스트에서 HEAD 는 가장 첫 노드를 가리키고 있기 때문에 만약 삭제할 value 가 1인 경우

if 문의 head?.value == value 가 TRUE 가 된다.

그럼 head = head?.next 는 무엇이냐? 

아까 위에서 1, 2, 3 을 추가해주었기 때문에 현재 head 의 상태는 대략 Node(value: 1, next: Node(value:2, next: ... 이다.

그러니까 현재 HEAD 의 next 는 두 번째 노드를 가리키고 있다. 즉, HEAD 가 다음 노드를 가르키도록 만들어주는 부분이다.

만약 노드가 1 하나밖에 없다면, next 는 nil 이기 때문에  HEAD 에 nil 이 담겨, 아무런 노드가 존재하지 않게 될 것이다.

만약 HEAD -> 1 -> 2 -> 3 의 노드가 존재하는 상황에서 삭제 값으로 2를 넣는다면 아무 일도 일어나지 않을 것이다.

 

 

그렇다면 이제 2 나 3 번째 노드를 제거할 방법을 구현해야 할 것이다.

이 부분이 약간 이해하기가 어려웠지만 천천히 뜯어보면 이해하는데 성공할 수 있다.

 

이전 노드를 저장할 변수 previous 와 현재 HEAD 가 가리키고 있는 노드 변수인 current 를 선언했다.

(기본적으로 링크드 리스트는 HEAD 가 첫 번째 노드를 가리키고 있는 것에서 시작한다는 것을 인지하고 있어야 한다)

 

그리고 이 while 문이 중요한데, 안의 조건은 current 가 nil 이 아니면서 current 의 값과 삭제하고자 하는 값이 달라야 한다는 것이다.

이렇게만 보면 어려운데 만약 삭제하고자 하는 값이 3이라고 가정해보면 쉽다.

 

1) HEAD -> 1 -> 2 -> 3 에서 3 번째 노드를 제거하려고 한다.

2) if 문에서 현재 HEAD 는 첫 번째 노드를 가리키고 있기 때문에 head.value 와 내가 삭제하고자 하는 value 는 같지 않다(=FALSE). 그러므로 if 문을 패스한다.

3) 그렇다면 HEAD 를 3번째 노드로 옮겨줘야 삭제를 할 수 있다는 사실을 잘 기억해야 한다.

var previous: Node?
var current = head
        
while current != nil && current?.value != value {
    previous = current
    current = current?.next
}
    
previous?.next = current?.next

4) 이전 노드를 저장할 변수 previous 를 선언하고 HEAD 의 위치를 가질 current 를 선언했다.

(그 이유는 내려가다 보면 알게 될 것이다)

 

4 - 결과)

previous : nil 인 상태

current : 첫 번째 노드

 

5) 이제 while 문을 만났다. 현재 HEAD 는 nil 이 아닌 것은 맞다(첫 번째 노드를 가리키고 있으니까). 하지만 그 current(HEAD) 와 내가 삭제하고자 하는 value 인 3도 일치하지 않아 while 문은 TRUE 가 되어 while 문 내부에 들어가게 된다.

6) 현재 current 인 첫 번째 노드의 상태를 previous 변수에 저장하고, 이 첫 번째 노드의 next 인 두 번째 노드를 current 에 담는다. 

7) 그럼 previous 에는 첫 번째 노드가 들어가 있는 상태이고, current 에는 두 번째 노드가 들어가 있는 상태이다.

 

5 ~ 7 결과)

previous : 첫 번째 노드

current : 두 번째 노드

 

 

7) 다시 while 문의 조건을 확인한다. 여기서도 True 가 나오는데 1~6의 과정을 잘 이해했다면 True 라는 것을 아는 것은 어렵지 않다.

8) 자 previous 는 이제 두 번째 노드를 가지게 되고, current.next 인 세 번째 노드가 current 에 담기게 된다.

 

7 ~ 8 결과)

previous : 두 번째 노드

current : 세 번째 노드

 

9) 다시 while 문의 조건을 확인한다. current 의 상태는 nil 이 아니지만 current.value 인 3과 내가 parameter 로 전달한 value 인 3이 같게 되었다. FALSE 이기 때문에 이제 while 문을 탈출한다. 결국 이 while 문은 내가 삭제하고자 하는 노드까지 HEAD 를 이동시키는 과정인 것이다.

 

 

10) 마지막 코드인 'previous?.next = current?.next' 은 굉장히 재미있다. 현재 HEAD(코드에서는 current) 가 While 문을 통해서 마지막 노드까지 오게 되었다. 자 current.next 는 무엇인가? 바로 nil 이다. current 가 마지막 노드이기 때문에 마지막 노드의 next 는 존재하지 않는다. 그래서 nil 이다. 이것을 previous(두 번째 노드) 의 next 에 넣는다. 이 마지막 코드를 통해서

Node(value: 2, next: Node(value: 3, next: nil)) 이었던 두 번째 노드가

Node(value: 2, next: nil) 이 된다. 즉, 3번째 노드를 나타내는 주소가 nil 이 되었기 때문에 혼자 덩그러니 남은 3번째 노드는 삭제되는 것이다.

 

9 ~ 10 결과)

previous : Node(value: 2, next: nil)

current : Node(value: 3, next: nil) 이지만 이제 두 번째 노드의 next 가 nil 이 되었기 때문에 세 번째 노드에 접근할 방법은 없어진다.

 

 

 

링크드 리스트의 삽입과 삭제에 대해서 알아보았다.

끝.