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

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

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

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

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

이중 연결 리스트라고도 함

장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

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

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

이렇게

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

class Node { 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 { // first of Linked List var head: Node? // tail of Linked List var tail: Node? // current Node of Linked List var node: Node? // 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? { 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? { 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

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

from http://tnqtnq.tistory.com/83 by ccl(A) rewrite - 2021-09-11 10:00:41