[Algorithm] 연결 리스트 값 추가 하기( LinkedList )[2/3]_자료구조(DataStructure_Swift)

연결 리스트 값 추가 하기( LinkedList ) [2/3]

 

 

연결 리스트 종류?

1. Push: 리스트 맨 앞에 값 추가 하기
2. Append: 리스트의 맨 뒤에 값 추가 하기
3. Insert(after): 리스트의 특정 노드 뒤에 값 추가(삽입)하기

---

• head와 tail 선언 하기

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 이면 빈 연결리스트 라는 걸 표현.
    }

---

< Push 구현 하기 >

• push(value:) 리스트의 맨 앞에 값 추가 하기

    //MARK: - Push ( adding a value at the front of the list )
    public mutating func push(_ value: Value) {
        // mutating : LinkedList가 구조체 이기 때문, 이 메 소드는 LinkedList 하위에 들어가는 것.
        // 구조체는 클래스와는 다른 '값 타입' 이기 때문에 구조체 인스턴스 내부에 값을 수정하고 싶다면 mutating 붙여줘야함
        head = Node(value: value, next: head) // head 생성 , head 에 Node 인스턴스의 참조정보를 저장 됨을 유의, Node는 클래스 이기 떄문에
        if tail == nil {
            tail = head
            // head 의 메모리 주소를 tail 넣는다.  tail 을 통해 head 바꿀 수 있다.
            // 참조정보: Node는 클래스라서 그의 인스턴스에는 참조정보가 저장될 뿐!
        }
    }
}

• 결과 확인

example(of: "push") {
    var list = LinkedList<Int>()
    list.push(3)
    // value = 3 인 노드의 참조 정보가 list.head에 할당, tail == nil 이므로 tail에 head의 참조정보가 할당 된다.
    // 현재 value 3, next nil / head와 tail의 위치가 같다.
    list.push(2)
    // value = 2 인 노드의 참조정보가 list.head에 할당, tail은 nil이 아니므로 새로 값이 설정되지 않는다
    // 현재 value 2, next는 이전 단계의 head인 value 3의 참조 정보 들어온다
    // tail은 그대로 value 3
    // 즉 새로운 노드가 앞으로 가고 tail은 자동으로 뒤로 가기 때문에 push 발생
    list.push(1)
    print(list)
}

---

< Append 구현 하기 >

• append(value: ) 리스트의 끝에 값 추가 하기

    public mutating func append(_ value: Value) {
        guard !isEmpty else{ //연결리스트가 비어있는지 체크후 비어있다면 push 메소드 실행. 첫번째 노드 추가하는 것 동일
            push(value)
            return
        }
        // 두번째 이상 노드를 추가할 때 실행 되는 과정
        tail!.next = Node(value: value)
        // tail은 head와 같은 Node(1,nil) 인스턴스 참조 하고있음!
        // tail.next에 새로운 Node 인스턴스를 할 당하면 참조 정보를 가진 head.next도 바뀌게 된다
        tail = tail?.next
        // tail 이라는 변수에 원래는 head와 같은 첫번째 노드 인스턴스의 참조 를 가지고 있지만
        // 새로 들어온 노드인스턴스의 참조정보 할당해 준다
        // 그럼 자연스럽게 추가하는 노드는 tail변수가 참조하게 되고 tail이 이 뒷부분을 참조 하는 것처럼 된다
    }

• append 실행

example(of: "append") {
    var list = LinkedList<Int>()
    list.append(1) // 첫 노드니까 push(1)과 같은 과정
    list.append(2)
    // 두번쨰 노드 2 추가. tail.next = Node(2)
    // tail.next 는 tail에 있는 참조정보를 이용해서 next에 접근하는 것이다
    // 그 곳에 Node(2)라는 새로운 노드 인스턴스를 할당
    // 현재 상태 -> tail.next / head.next 둘다 Node(2)를 가리키는 상태
    // tail과 head가 같은 Node(1)을 가리키고 있었기 때문에 tail로 접근해도 head가 같이 바뀐다 (참조의 특성)
    // tail = tail.next 실행
    // 원래는 tail과 head가 같은 Node(1)를 가리키고 있었는데 tail에 tail.next 에 있는 Node(2)의 참조 정보를 할당
    // 이로써 head는 앞에꺼, tail은 뒤에 노드의 참조정보를 따로 가지게 되는 것이다.
    // 이러면 연결리스트의 뒤에 추가 되고 append 과정이 수행 되는 것
    list.append(3)
    print(list)
}

• 결과 확인

---

< Insert 구현 하기 >

• 리스트의 특정 노드 뒤에 값 추가(삽입)하기는 2과정으로 수행됨

  1. 연결리스트의 특정 노드를 찾고
  2. 찾은 노드 뒤에 새로운 노드를 추가 하기

• 특정 노드 찾기

  // Insert 1 - 삽입을 원하는 노드의 위치 (Index) 찾기
    public func node(at index: Int) -> Node<Value>? { // 매개변수에 원하는 X번째 노드 넣으면 노드 반환해준다
        var currentNode = head // 탐색하기 전 시작 포인트 설정해주기. head는 연결리스트의 첫 노드
        var currentIndex = 0 // 시작 포인트 0 부터
  
        while currentNode != nil && currentIndex < index {
            // 헤드 노드가 nil이 아니고 : 빈 노드인지 확인
            // 현재 노드 탐색하고 끝 포인트가 매개 변수로 들어온 index 보다 작을 때까지 무한 반복.
            currentNode = currentNode!.next // 현재 노드가 다음 노드가 됨 -> '탐색'
            currentIndex += 1 // 인덱스 하나 올라감 -> 하나하나 '탐색'
        }
        return currentNode
        // 반환하는 현재 노드는 매개 변수 index의 값 번째 Node가 된다.
    }

• 찾은 노드 위에 노드 삽입

  // Insert 2 - 값을 삽입하기
    public mutating func insert(_ value: Value, after node: Node<Value>){
        // 두번째 매개변수에 먼저 알아낸, 내가 원하는 특정 노드 넣어서 그 뒤에 값 삽입하기
        guard tail !== node else {
        // tail과 node 둘 모두 클래스의 인스턴스라서 참조 정보를 가지고 있다.
        // 그러므로 ==, != 이용 할 수 없다. 값이 아니라 참조 정보 비교해야해서
        // ===, !== 이용해서 해당 인스턴스를 비교하는 방법 사용한다.
        // 넣어준 두번째 매개변수 node가 tail노드라면 append() 쓰면 된다
        append(value)
        // return tail! -> 새로 들어간 노드 반환하고 싶으면 이거 쓰면됨
            return
        }
        node.next = Node(value: value, next: node.next)
        // 특정 노드의 인스턴스를 알고 있는 상태. (탐색해서 두번째 매개변수로 넣어 주었으니까)
        // 그 노드의 다음 노드에 삽입하고자 하는 새로운 노드의 인스턴스 할당 한다.
        // 새로운 노드의 next는 삽입하기 전 노드의 다음 노드를 넣어준다
        // 이러면 가운데에 들어가게 된다.
        // return node.next! -> 새로 들어간 노드 반환하고싶을 때
    }
  }

• insert 실행

  example(of: "Insert at a particular index") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1) // 1, 2, 3 인 연결리스트
  
    print("삽입전 리스트 \(list)")
    list.insert(-1, after: list.node(at: 1)!) // 인덱스 1 번째 노드 (컴퓨터에선 2 번째) 뒤에 -1 삽입
    print("삽입후 리스트 \(list)")
  }

   

 

전체 코드

LinkedList.zip

0.01MB

---

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