스위프트 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조: #swift

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• Swift4: 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• Swift4: 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• Swift4: 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• Swift4: 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

연결리스트 ( Linked List ) (1 / 3)

• What is LinkedList
• 연결리스트는 선형적으로( 직선같은 ) 단방향 연속성으로 정렬된 값의 모음입니다. 
• 해석이 모호한데 영문 정의는 이렇습니다.
• A collection of values arranged in a linear unidirectional sequence.
• 배열 ( Array ) 와는 다른 자료구조 입니다! 
• 자료구조의 아이디어는 모두 비슷하거나 동일합니다. 다만 이러한 아이디어들을  Swift4 를 사용해서 컴퓨터에 구현하는게 목적입니다.
• 어떻게 생겼어?
• Node 와 Reference 는 그림과 같습니다.
• 그림에서 보는 것과 같이 2 가지 특징이 있습니다.
•  값을 가지고 있다.
• 다음 노드의 '참조정보' 를 가지고 있다. ( 참조를 가지고 있어서 다음 노드를 가리킬 수 있는 것입니다. C 에서 포인터의 역할인 것이죠. )

• 이 과정들을 모두 컴퓨터로 구현합니다.
• 준비 단계 -> 추가, 삽입하기 -> 제거하기  순으로 진행
• 1. 준비 단계 (1 / 3)
• Node 구현

public class Node<Value> { // Node 클래스를 <Value> 라는 Generics 타입으로, public 으로 모든 모듈에서 접근 가능하도록 정의합니다.
    public var value: Value // 노드가 가지고 있는 값.
    public var next: Node? 
    // 노드가 가리키는 노드 (다음 노드)
    // 마지막 노드는 다음 노드가 nil 이기 때문에 옵셔널로 선언합니다. 
    
    public init (value: Value, next: Node? = nil) { 
        // 두 번째 매개변수 next 를 nil 로 초기화 이유 
        // 노드 인스턴스 생성할 때 두 번째 매개변수 next 를 굳이 명시하지 않아도 nil 로 초기화 하게 초기값 지정해 준 것.
        self.value = value
        self.next = next
    }
}

• 연결리스트 출력하는 description 확장 구현 ( 연결리스트를 만들었는데 볼 수 없다면 안되니까요! )

extension Node: CustomStringConvertible { 
    //CustomStringConvertible 프로토콜을 채택하는 객체는 자기 타입에 대한  description을 제공해야 합니다.
    public var description: String { // 연산 프로퍼티 네요.
        guard let next = next else { // nil 이 아니라면, 즉 다음 노드가 있다면
            return "\(value)" // 다음 노드가 없다면 value 값만 출력시킴.
        }
        return "\(value) -> " + String(describing: next) + " " 
        // String(describing:) 메소드가 다음 노드의 description 을 호출합니다. 
        // 이는 결국 연쇄적으로 다음, 다음의 다음, 다음의 다음의 다음, 이렇게 연결리스트의 노드를 한 눈에 보여주는 역할을 합니다.
    }
}

• 예제들을 테스트 할 때 사용할 유틸함수

public func example(of description: String, action: () -> Void) {
    print("---Example of \(description)---")
    // 첫 번째 매개변수에 테스트에 대한 설명 써주긔.^^
    action() 
    // 두 번째 매개변수 실행시키기
    // 이 함수를 쓸 때는 클로져를 활용할 예정입니다. 그래서 매개변수에 함수 타입이 들어간 것.
    print() // 한줄 띄우기 역할
}

• 간단한 예제를 보여 드릴게요.

example(of: "creating and linking nodes") { // 유틸함수로 테스트 한다고 했쥬?
    let node1 = Node(value: 1) // Node 클래스 인스턴스 1
    let node2 = Node(value: 2) // Node 클래스 인스턴스 2
    let node3 = Node(value: 3) // Node 클래스 인스턴스 3 , 3개의 서로 다른 Node클래스의 인스턴스 임을 유의.
    
    node1.next = node2 // next 를 의미하는 프로퍼티에 node2 참조정보 할당.
    node2.next = node3
    
    print(node1) // extension 으로 구현한 Node 클래스의 description 출력되겠죠? 
}

• 결과는 다음과 같습니다.

• 연결리스트 전체를 표현할 LinkedList

public struct LinkedList<Value> { 
// 전체 연결리스트를 관리하는 하는 LinkedList 구조체
    public var head: Node<Value>? // 헤드 노드 : 연결리스트의 첫 번째 노드 표현.
    public var tail: Node<Value>? // 테일 노드 : 연결리스트의 마지막 노드 표현.
    
    public init() {} // 모든 프로퍼티들 옵셔널이면 nil 로 초기화됨.
    
    public var isEmpty: Bool { // 비어 있어? 
        return head == nil 
        // head 와 nil 을 비교해서 nil 이라면 true 반환. head 가 nil 이면 빈 연결리스트 라는 걸 표현.
    }
}
// 연결리스트는 왜 구조체를 씁니까? 하면.. 보통은 구조체를 쓰고 특정 목적으로 클래스를 쓰는데요.
// Node 는 연결리스트에서 노드가 추가되고, 제거되는 과정에서 메모리가 추가되고 메모리가 해제되는데 그 과정은 모두
// 하나의 노드들이 참조가 추가되고 참조가 추가되는 과정이거든요. 
// Node 가 구조체라면 next 에 새로운 노드가 생길 때마다 값이 복사되서 불 필요한 많은 노드들이 생기게 되겠죠!! 
 
extension LinkedList: CustomStringConvertible { // 연결리스트 출력할 때 description 지정.
    
    public var description: String {
        guard let head = head else { // 헤드노드가 nil 이면 연결리스트에 아무것도 없는 상태에요.
            return "Empty List"
        }
        return String(describing: head) // 헤드노드에 모두 연결되므로 헤드노드 출력하면 연결리스트 나옵니다.
    }
}

전체 소스 파일

• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )