[Algorithm] 연결 리스트 자료구조( LinkedList )[1/3]_자료구조(DataStructure_Swift)

연결 리스트( LinkedList ) [1/3]

 

 

연결 리스트란 무엇인가?

• 선형적으로 (직선 같은 ) 단방향 연속성으로 정렬된 값의 모음이다.
• A collection of values arranged in a linear unidirectional sequence.
• 배열(Array)와는 다른 구조이다.

특징

• 값을 가지고 있다.
• 다음 노드의 ‘참조 정보’를 가지고 있다. (참조 정보를 가지고 있기 때문에 다음 노드를 가리킬 수 있다.(포인터 역할))

---

위의 설명을 바탕으로 실제 코드로 구현합니다.

코드 & 설명

---

Node 구현

public class Node<Value> { //Node 클래스를 <Value> 라는 Generics 타입으로, public 으로 모든 모듈에서 접근 가능하도록 정의 한다.
    public var value: Value //Node가 가지고 있는 값
    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.zip

0.01MB

---

출처 : 스위프트 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조: #swift :: 씩이 머릿속