Linked List 구현하기

선형적인 특징을 가진 Linked List 구현을 해보게씀다..!

선형적이라는 것은 선처럼 일자로 데이터의 배열이 되어 있다는 것이죠!

 

Linked List를 구현하기 위해선 데이터가 되는 Node를 우선 구현해야하고, 그 노드들을 탐색하며 데이터를 추가하거나, 지우기 위한 manager 역할을 하는 Linked List를 만들어 줄껍니다!

 

## 기본적인 Linked List를 알고 있다고 가정하고 만들게씀다!

 

우선 Linked List에 필요한 Node는 아래와 같이 자신의 데이터를 가지고 있고, 자신 다음의 Linked된 데이터를 가지기 위한 next를 가지고 있어야 합니다!

Linked List에서의 노드의 모습

 

 

 

위와 같은 모습을 만들어주기 위해 Node를 우선 구현해 줍시다!

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

 노드는 Int, Double, 혹은 객체까지도 가질 수 있기에, 제너릭 타입을 갖는 노드를 만들어 주었고, 해당 노드는 Linked List의 특성상, 다음 노드가 있을 수도 있고!, 없을 수도 있기때문에, next는 옵셔널타입을 가집니다.

 

 

 

그럼, 노드들을 관리하는 Linked List도 함께 구현해줍시다!

 

Linked List는 어떤 기능이 있어야 할까요?

 

프로퍼티로는

1. Linked List의 처음 데이터를 갖고 있는 head값

2. Linked List에 데이터가 총 몇개인지 가지고 있는 count값

 

함수로는,

1. Linked List의 가장 뒤에 데이터를 넣는 append()

2. 중간 원하는 자리에 데이터를 넣는 insert()

3. 마지막 데이터를 지우는 removeLast()

4. 원하는 위치의 데이터를 지워버리는 remove()

5. 데이터가 Linked List안에 있는지 확인하는 searchNode()

 

증말 많다.. 일단 써보고 천천히 구현해보자!

class LinkedList<T> {
    private var head: Node<T>?
    private var count: Int = 0
    
    func append(data: T) {

    }
    
    func insert(data: T, at index: Int) {

    }
    
    func removeLast() {

    }
    
    func remove(at index: Int) {

    }
    
    func searchNode(at data: T) -> Node<T>? {
        
    }
    
    func printAllNode() {

    }
    
}

 

마지막에 데이터를 넣어주는 append 먼저 가볼까여

1. append()

    func append(data: T) {
        // 데이터가 없는 상황일때
        if head == nil {
            head = Node(data: data, next: nil)
            count += 1
            return
        }
        
        var node = head // head의 위치를 직접 바꾸는 과정이 아님
        while node?.next != nil {
            node = node?.next
        }
        node?.next = Node(data: data, next: nil)
        count += 1
    }

크게 생각해볼 점은, Linked List가 비어있을때의 경우이다.

 

Linked List가 비어 있을때는 head에 우리의 데이터를 가진 노드를 넣어 주어야 하고, 

그렇지 않을 경우, 가장 마지막 노드의 next로 우리의 노드를 넣어주면 된다!

 

아! 물론 데이터가 추가되면 그 이후에 count 값을 +1 해주어야 한다!

 

2. insert()

    func insert(data: T, at index: Int) {
        // 만약 index가 가장 마지막을 가리킨다면, append로 책임을 넘겨주자!
        if count == index {
            self.append(data: data)
            return
        }
        // index값이 우리 데이터 갯수보다 크다면 주저없이 Error를 print하자!
        if count - 1 < index {
            print("Wrong Insert index!")
            return
        }
        // Linked List가 비어있는 경우! append로 넘겨줄수도, 여기서 만들어주어도 된다!
        if head == nil {
            head = Node(data: data, next: nil)
            count += 1
            return
        }
        // head 값으로, 데이터를 추가하는 경우
        if index == 0 {
            var node = Node(data: data, next: head)
            head = node
            count += 1
            return
        }
        
        // 일반적으로 중간에 데이터를 넣어주는 경우
        var node = head
        for _ in 0..<index-1 {
            node = node?.next
        }
        var insertNode = Node(data: data, next: node?.next)
        node?.next = insertNode
        count += 1
    }

 

뭔가 많다.. 그러나 읽어보면 다 그냥 아~ 하면서 넘어갈 수 있음! 

다만 생각해볼 부분은 가장 마지막인 일반적으로 중간에 데이터를 넣는 경우인데,

아래와 같은 순서로 insert 작업이 진행된다!

 

 

Node insert 과정

 

 

3. removeLast()

    func removeLast() {
        // 데이터가 없을때
        if head == nil {
            return
        }
        
        // 데이터가 head 하나 있을때
        if head?.next == nil {
            head = nil
            count -= 1
            return
        }
        
        // 일반적인 데이터에서 가장 뒤를 지울때
        var node = head
        while node?.next?.next != nil {
            node = node?.next
        }
        
        node?.next = node?.next?.next
        count -= 1
    }

 removeLast()도 insert(), append()와 거의 비슷한 논리로 구성되고,

다만 마지막 노드의 전 노드를 잡아서 해당 노드의 next값을 nil로 만들어주는 뿐이다.

 

 

4. remove()

    func remove(at index: Int) {
        // Linked List 비었을 때
        if head == nil {
            return
        }
        // 인덱스를 넘은 놈을 지우려 할 때
        if count - 1 < index {
            print("Wrong remove Index")
            return
        }
        // 가장 마지막 index를 지우려 할때, removeLast()를 불러준다
        if count - 1 == index {
            self.removeLast()
            return
        }
        // head 노드를 지우려 할때
        if index == 0 {
            var node = head
            head = node?.next
            node?.next = nil
            count -= 1
            return
        }
        
        // 중간에 있는 노드를 지울경우
        var node = head
        for _ in 0..<index-1 {
            node = node?.next
        }
        
        node?.next = node?.next?.next
        count -= 1
    }

 

이도 역시, 중간에 있는 노드를 지우는 경우가 포인트인데,

 

remove(at: )

근데.. deleteNode의 next가 남아있는데 저러면 안되는거 아닌가?

 

 똑똑한 Swift는 저런 경우 deleteNode를 접근할 수 없고, 필요없는 class로 생각해 자동으로 메모리에서 해제해주게 되므로, 걱정하지 않아도 된다!

실제로 Node가 deinit()된다 :)

 

5. searchNode()

 func searchNode(at data: T) -> Node<T>? {
        var node = head
        
        while node?.data != data {
            node = node?.next
            if node == nil {
                return nil
            }
        }
        
        return node
    }

찾는 데이터의 노드가 있다면 해당 노드를 return 하고, 원하는 데이터의 노드가 없다면 nil값을 return하게 된다ㅎ 쉽당

 

 

이렇게 노드를 head값을 옮기며 탐색할 수 있는 Linked List 구현을 완료했다..!

 

일반 Array와 비해서는 최적의 메모리 공간을 활용하며 데이터를 저장해 장점이 있지만, 

아무래도, 선형적인 구조이기 때문에, 찾거나 삭제할 경우 O(n)의 시간복잡도를 가진다.

 

위의 코드로 Linked List를 구현할때 생각해봐야 할 점들을 알게 된 것 같다!

 

끗!