[알고리즘] 패스트캠퍼스 챌린지 06일차

또 링크드리스트.. 오늘이 마지막!!!

 

다양한 형태의 링크드 리스트

더블 링크드 리스트(Doubly linked list) 기본 구조

• 이중 연결 리스트라고도 함
• 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

>> 이전에 계속 다뤘던 건 한 방향으로만 (->) 연결이 되는 링크드 리스트는 특정 노드를 탐색하는데 항상 앞에서부터 검색해야하므로 오래걸린다.

 

>> 노드에 (데이터, 다음 데이터 주소) 만 저장하지 않고 (이전 데이터의 주소, 데이터, 다음 데이터 주소)의 형태로 이전 데이터 주소도 함께 저장해 양방향으로 탐색이 가능하도록 함!!

이렇게

 

기존 단방향 링크드 리스트 노드에 이전 노드를 가리키는 변수(prev)가 하나 더 필요하다.

class Node<DataType: Comparable> {
    var data: DataType?
    var next: Node?
    var prev: Node?
    
    init(_ data: DataType, next: Node? = nil, prev: Node? = nil) {
        self.data = data
        self.next = next
        self.prev = prev
    }
}

 

그리고, 링크드리스트도 맨 처음 노드(헤드)와 함께 맨 마지막 노드(테일) 정보가 필요하다.

기본적으로 Double Linked List의 맨 마지막에 새로운 데이터를 추가하는 함수(add)와

처음부터 끝까지 출력하는 함수(desc)를 Swift로 구현해봤다.

class DoubleLinkedList<DataType: Comparable> {
    // first of Linked List
    var head: Node<DataType>?
    // tail of Linked List
    var tail: Node<DataType>?
    // current Node of Linked List
    var node: Node<DataType>?
    
    // add data to at the end of Linked List
    func add(data: DataType) {
        guard self.head != nil else {
            // no head >> make head, tail
            self.head = Node(data)
            self.tail = Node(data)
            return
        }
        
        node = self.head
        while node?.next != nil {
            node = node?.next
        }
        // add New last node
        let newNode = Node(data)
        node?.next = newNode
        // new last node's previous node == current last node
        newNode.prev = node
        // set linked List's tail Node == new node
        self.tail = newNode
    }
    
    // print data from start to end
    func desc() {
        // print linked list from first to the end
        var node = head
        while(node != nil) {
            print(node?.data)
            node = node?.next ?? nil
        }
    }
}

 

그리고 특정 데이터로 노드를 탐색하는 함수도 만들어봤다.

Double Linked List 이므로 맨 처음(Head) 또는 맨 마지막(Tail)에서부터 찾는 두가지 방법이 있다.

둘다 구현하고 테스트도 해봤다.

    // search node with data from head to tail
    func searchNodeFromHead(data: DataType) -> Node<DataType>? {
        guard self.head != nil else {
            // no head
            print("no head!!")
            return nil
        }
        
        var node = head
        while(node != nil) {
            if node?.data == data {
                return node!
            } else {
                node = node?.next
            }
        }
        print("No exact Node with input Data")
        return nil
    }
    
    // search node with data from tail to head
    func searchNodeFromTail(data: DataType) -> Node<DataType>? {
        guard self.head != nil else {
            // no head
            print("no head!!")
            return nil
        }
        var node = self.tail
        while(node != nil) {
            if node?.data == data {
                return node!
            } else {
                node = node?.prev
            }
        }
        print("No exact Node with input Data")
        return nil
    }

 

특정 데이터로 노드를 찾아 그 노드 앞에 새로운 데이터를 추가하는 함수도 구현해봤다.

좀 복잡함!

[방법]

누구 앞에 추가할건지 찾는다.

tail(맨 끝)에서부터 찾아준다.

그럼 이제 찾은 현재 노드(node), 새로 추가할 노드(newNode), 원래 현재 노드의 이전노드(beforeNewNode)의 관계를 지어준다.

 

// insert new data before the exact data
    func insertData(newData: DataType, before beforeData: DataType) {
        guard self.head != nil else {
            // no head >> new node == head
            self.head = Node(newData)
            return
        }
        
        var node = self.tail
        while node?.data != beforeData {
            // move to previous node
            node = node?.prev
            guard node != nil else {
                // no previous node >> cannot insert data
                return
            }
        }
        // find node. insert new node before the node
        // new node to insert
        let newNode = Node(newData)
        
        // set order
        // beforeNewNode -> NewNode -> node
        let beforeNewNode = node?.prev
        beforeNewNode?.next = newNode
        newNode.prev = beforeNewNode
        newNode.next = node
        node?.prev = newNode
    }

 

그리고 이와 반대로 특정 데이터로 노드를 찾아 그 노드 뒤에 새로운 데이터를 추가하는 함수는 연습문제로 주어졌다.

혼자 만들어봤다.

    // insert data after the exact data
    func insertData(newData: DataType, after data: DataType) {
        guard self.head != nil else {
            // no head >> new node == head
            self.head = Node(newData)
            return
        }
        
        var node = self.head
        while node?.data != data {
            // move to next node
            node = node?.next
            guard node != nil else {
                // no next node >> currentnode == last node >> cannot insert data
                return
            }
        }
        // find node. insert new node after the node
        // new node to insert
        let newNode = Node(newData)
        
        // set order
        // node -> NewNode -> afterNewNode
        let afterNewNode = node?.next
        afterNewNode?.prev = newNode
        newNode.prev = node
        newNode.next = afterNewNode
        node?.next = newNode
    }

강의 수강 인증샷..!

어렵지만.. 강의 계속 반복해서 들으면서 이해했다.

해답 코드 안보고 직접 생각하고 이해하고 짜봤다.

링크드리스트는 3일엔 걸쳐 끝나긴 끝났는데.. 다음에 혼자서도 할 수 있겠징?

안까먹게 블로그 글이라도 틈틈이 조금씩 읽어봐야겠다.

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.