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

 

 

 

안녕하세요 :) 소들입니다

이제 연휴가 정말 없군요....! 빡공 모드 On~~

이번 포스팅에선 저번 단방향 연결 리스트를 보완한

양방향 연결 리스트에 대해서 공부해보려고 해요 :)

 

단방향보다는 조금 더 간단하게 알아보려고 합니다..!

append, search, removeLast 정도만 알아볼 예정 :)

 

그럼 고고씽

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 양방향 연결 리스트란?

 

이전 포스팅에서 간단하게 언급하긴 했음!

단방향 연결 리스트의 경우 다음과 같이

 

 

 

 

원하는 데이터를 search 하려면 head부터 순회해야 하기 때문에,

만약 내가 찾고자 하는 데이터가 가장 마지막에 있으면

모든 연결 리스트를 순회해야하는 단점이 있었음!

 

따라서, 이를 보완한 것이 양방향 연결 리스트인데,

양뱡향 연결 리스트의 경우 다음과 같이

 

 

 

 

가장 첫 노드를 가리키는 head와, 

가장 마지막 노드를 가리키는 tail을 두고,

내 이전 노드와, 내 다음 노드 두 노드를 모두 연결하여

양방향에서 탐색이 가능하게 하는 것이 양방향 연결 리스트임!

 

따라서, 만약 내가 찾고자 하는 데이터가 연결 리스트의 마지막 쪽과 가깝다면,

tail을 이용해서 찾으면 되고,

찾고자 하는 데이터가 연결 리스트의 처음 쪽과 가깝다면

head를 이용해서 찾으면 됨!

 

어렵지 않군 :) 구현하러 가보자

 

 

 

 

2. 양방향 연결 리스트

 

양방향 연결 리스트의 경우, 단방향 연결 리스트와 다르게

노드(Node)의 생김새가 조금 다름!

 

 

 

 

당연히 내 이전 노드와, 내 다음 노드를 모두 저장해야 하기 때문에

prev란 내 이전 노드의 주소값을 저장하는 것이고,

data는 내 데이터를 저장하는 것이고,

next는 내 다음 노드의 주소값을 저장하는 것임!

 

이제 코드로 봐봅시다 👀

 

 

 

2-1. Node를 생성해보자

 

우린 Node가 prev, data, next로 생겼단 것을 알았으니,

이를 class로 구현해보도록 하겠음

 

 

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라는 놈이 추가된 것 뿐임!

이제 Node를 관리해주는 DoublyLinkedList라는 클래스를 다음과 같이 만들어 보겠음!

 

 

class DoublyLinkedList<T: Equatable> {
}

 

 

제네릭에 Equatable이란 프로토콜을 채택한 것은

노드 안의 데이터를 비교하기 위한 것임! 단방향 때 공부 했음

 

 

 

2-2. head, tail : 가장 처음, 가장 마지막 노드를 가리키는 프로퍼티

 

양방향 연결 리스트는 head 뿐만 아니라, tail도 같이 가지고 있기 때문에,

 

 

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
}

 

 

이렇게 head와 tail이란 프로퍼티를 추가해주셈 :)

 

 

 

2-3. append(data:) : 연결 리스트 맨 마지막에 노드 추가하기

 

 

 

자, 단방향 연결리스트의 경우,

head부터 마지막 노드까지 찾은 후에 추가해줘야 했지만!!

양방향 연결 리스트의 경우, tail이란 마지막 노드를 알고 있기 때문에 

그런 과정이 필요 없음!

 

 

func append(data: T?) {
        
   //연결 리스트가 빈 경우, Node를 생성 후 head, tail로 지정한다
   if head == nil || tail == nil {
       head = Node.init(data: data)
       tail = head
       return
   }
        
   let newNode = Node.init(data: data)
   tail?.next = newNode
   newNode.prev = tail
   tail = newNode
}

 

 

이렇게 현재 tail의 next에다가 newNode를 연결 시켜주고,

newNode의 prev를 현재 tail로 연결 시켜주고,

tail은 늘 마지막 노드를 가리켜야 하니, tail을 newNode로 바꿔주면 됨!

(중간에 추가하는 insert는 tail을 바꾸지 않고 단방향 연결 리스트에서 prev만 신경쓰면 되니,

어렵지 않아 생략하겠음 :))

 

 

 

2-4. removeLast : 연결 리스트 맨 마지막 노드 삭제하기

 

 

 

그림으로 보면 delete할 노드의 바로 이전 노드의 next를 nil로 바꿔주면서,

tail의 위치 또한 같이 옮겨주는 것을 볼 수 있음!

코드로 보면 다음과 같음 :)

 

 

func removeLast() {
    
    if head == nil || tail == nil { return }
    
    //head를 삭제하는 경우(연결 리스트에 노드가 1개밖에 없는 경우)
    if head?.next == nil {
        head = nil
        tail = nil
        return
    }
    
    tail?.prev?.next = tail?.next
    tail = tail?.prev
}

 

 

이렇게 해주면 될 것 같음 :)

(index로 노드 삭제하는 것은 Insert와 같은 이유에서 다루지 않겠음!)

 

+ 현재 Node의 경우 Class로 구현되어 있어,

참조만 끊어주면 ARC에 의해 자동으로 메모리에서 해제됨!

 

 

 

2-5. searchNode(from:) : data로 head에서부터 노드 찾기

 

양방향 연결 리스트를 쓰는 이유는 뭐다?

탐색이 head, tail 두 방향에서 된다!!!

따라서 이번엔 head에서부터 특정 데이터로 노드 찾는 방법임

 

 

갈수록 화질구지

 

 

만약, 특정 데이터가 연결 리스트 앞 쪽에 위치한다!! 할 때 사용하면 됨!

 

 

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

 

 

요롷게 구현하면 되겠군!

이 경우는 사실 단방향 연결 리스트와 완전 동일함!

그럼 양방향 연결 리스트의 특징인 tail로 찾을 때를 봐보자 :)

 

 

 

2-5. searchNodeFromTail(from:) : data로 tail에서부터 노드 찾기

 

 

 

 

이번엔 위 그림처럼 tail에서부터 탐색하는 코드를 봐보겠음

 

 

func searchNodeFromTail(from data: T?) -> Node<T>? {
    
    if head == nil || tail == nil { return nil }
    
    var node = tail
    while node?.prev != nil {
        if node?.data == data { break }
        node = node?.prev
    }
    
    return node
}

 

 

사실, head에서 찾는 거랑 코드는 거의 똑같은데,

탐색의 시작점이 tail이란 것과, next가 아닌 prev로 거꾸로 가면서 찾아한단 것만 다름!!

만약, 특정 데이터가 연결 리스트 뒤 쪽에 위치한다!! 할 때 사용하면 됨!

 

 

 

 

 

 

.

.

.

 

자, 이렇게 해서 양방향 연결 리스트도 끝났습니다~~~

하나도 어렵지 않져?!?!?

어렵다면 코드로 직접 한번 짜보세여!! 매우 매우 재밌음!!!

 

혹시라도 잘못된 내용이나 피드백은 댓글로 남겨주시고,

insert, remove(at:) 같은 함수의 구현이 궁금하다 하시면 또 댓글 남겨 주세요 :)

양방향은 단방향보다 간단하게 봤기 ㄸㅐ..문..(귀..차니..즘)

 

그럼 20,000