[Data Structure] 연결리스트에 대해 알아보자(Linked List)

 

안녕하세요 Foma👟 입니다.

 

오늘은 연결리스트에 대해서 알아보려고 하는데요.

 

얼마 전에 2021 카카오 인턴쉽에 출제되었던 "표편집" 이라는 문제를 풀게 되었는데

 

해당 문제는 연결 리스트를 꼭 사용해야 효율성을 통과할 수 있는 문제였습니다.

 

 그 동안 연결 리스트를 사용해볼 일이 거의 없어서 구체적으로 알아본 적이 없었는데

 

이번 기회에 연결 리스트의 장점과 구현하는 방법에 대해 정리하려고 합니다.

 

바로 시작할게요~

---

Linked List란?

 

"연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다." - 위키 백과 -

 

즉, 포인터를 통해서 노드가 연결되어 있는 데이터 자료구조를 연결 리스트라고 합니다.

 

장점

 

삭제나 추가가 O(1) 시간에 가능하다.

 

보통 배열은 아래와 같이 index로 크기가 정해져 있습니다.

 

 

여기서 하나의 데이터를 삭제하려고 하면 그 다음 모든 데이터들이 재배치되어야 합니다.

 

 

 

추가 또한 마찬가지로 추가되는 인덱스 다음 모든 데이터들이 재배치가 됩니다.

 

 

하지만 연결리스트는 데이터가 삭제되거나 추가되면 해당 노드의 가리키는 포인터만 변경해주기 때문에

 

배열보다 삭제나 추가에서 효율적입니다.

 

 

단점

 

특정 데이터를 검색하는데  무조건 O(n)의 시간이 걸린다.

 

배열의 경우 특정 데이터를 찾을 때 인덱스가 있어 검색할 때 효율적입니다.

하지만 연결 리스트는 정해진 위치를 알지 못하기 때문에 검색 시 데이터를 순회해 특정 데이터를 찾아야 합니다.

 

---

Linked List 구조

 

단일 연결리스트를 예시로 들겠습니다.

 

연결 리스트는 아래와 같이 노드와 포인터로 이루어져 있고 다음 노드와 연결되어 있습니다.

 

가장 첫 번째 노드를 헤더라고 부르고 가장 마지막 노드를 테일이라고 부릅니다.

---

Linked List 종류

 

1. 단일 연결리스트

 

각 노드 당 한 개의 포인터가 있고 포인터는 다음 노드의 위치를 가르킵니다.

 

테일은 가장 마지막이므로 다음을 가리키는 포인터를 갖지 않습니다.

 

 

2. 이중 연결 리스트

 

단일 연결 리스트는 포인터를 한 개 가지고 있어 다음 노드만 가리킬 수 있었다면

 

이중 연결 리스트는 포인터를 두 개 가지고 있어 이전 노드와 다음 노드를 가리킵니다.

 

 

3. 원형 연결 리스트

 

단일 연결 리스트의 테일에 포인터가 추가된 형태로 테일의 포인터는 헤더를 가르켜 원형이 되도록 합니다.

 

---

Code

 

지금부터는 연결리스트를 구현해보겠습니다.

 

(연결리스트 중에서 단일 연결리스트를 구현하겠습니다.)

 

Node

 

노드는 현재 값과 다음 노드를 가지고 있습니다.

 

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

 

Linked List

 

헤드가 무조건 존재하는 연결리스트로 선언했습니다. 

 

class LinkedList<T> {
    var head:Node<T>!
    init(head:Node<T>) {
        self.head = head
    }   
 }

 

append

 

head부터 다음 노드가 없는 노드를 찾아냅니다. (마지막 노드)

 

그리곤 해당 노드의 다음 노드를 현재 값으로 설정해줍니다.

 

 func append(value:T) {
        var node:Node = head
        while node.next != nil {
            node = node.next!
        }
        node.next = Node(value: value)
    }

 

insert(at:)

 

만약 0번째 삽입한다면 head가 되므로 현재 값을 가지는 Node를 head로 만들어주고 

 

head의 다음 값을 이전의 head로 넣어줍니다.

 

그게 아니라면 index의 바로 전 번째를 찾아서 다음 값을 변경해줍니다.

 

  func insert(value:T,at index:Int) {
        var node = head
        
        if index == 0 {
            let pastHead = head
            head = Node(value: value)
            head.next = Node(value: pastHead!.value,next:pastHead?.next)
            return
        }
   
        for _ in 0..<index-1 {
            node = node?.next
        }
        
        if node?.next == nil {
            fatalError("list의 크기보다 index가 커서 insert가 안됩니다.")
        }
        
        let next = node?.next
        node?.next = Node(value:value,next:next)
    }

 

remove(at:)

 

0번째는 head를 지우는 것이므로 그 다음 값을 head로 만들어줍니다.

 

0번째가 아니라면 해당 index의 바로 전 Node를 찾아서 다음 Node 값을 변경해줍니다.

 

    func remove(at index:Int) {
        var node = head
        
        if index == 0 {
            if head.next == nil {
                fatalError("head말고 다른 값이 없어서 remove가 안됩니다.")
            }
            head = Node(value: head.next!.value, next: head.next?.next)
            return
        }
        
        for _ in 0..<index-1 {
            node = node?.next
        }
        
        if node?.next == nil {
            fatalError("list의 크기보다 index가 커서 remove가 안됩니다.")
        }
        
        if let next = node?.next?.next {
            node?.next = Node(value:next.value,next:next.next)
        }else {
            node?.next = nil
        }
    }

---

이렇게 오늘은 연결리스트가 무엇이고 간단하게 구현해보았는데요.

 

혹시라도 틀린 점이 있거나 지적해주실 부분이 있다면 언제든 댓글로 알려주세요!