swift 자료구조 - 연결리스트 코드로 정리 - 1

swift 자료구조 - 연결리스트 코드로 정리

 

연결 리스트

 

연결리스트는 배열의 단점을 보완한 자료구조입니다.

배열의 단점으로는 크게 2가지가 있습니다.

 

[1] 배열을 선언할 때 배열의 크기를 지정해버리면 지정한 크기 만큼 요소를 할당 할 수 있다는 것. 즉, 배열의 크기가 5면 요소를 6개, 7개 할당을 할 수 가 없다는 것입니다.

 

[2]배열 안의 요소를 삭제할 때 오버헤드가 커진다. 예를 들어 1부터 5까지 5개의 요소가 들어 있는 배열에서 정 가운데 있는 숫자 3을 삭제한다면? 숫자 3의 자리는 비게 되고 빈공간을 채우기 위해서 뒤에 위치한 숫자 4와 5가 한칸씩 앞으로 이동하게 됩니다. 예제가 배열의 크기가 5개라서 그렇지 만개 십만개라면? 그 오버헤드는 엄청 클것입니다.

 

그래서 연결리스트 자료구조가 나왔습니다.

 

연결리스트 자료구조의 특징은 배열의 단점을 보완했다는 것입니다.

 

[1] 리스트의 크기를 지정하지 않고 자유롭게 요소를 할당할 수 있다. 

 

[2] 리스트의 중간에 있는 요소를 삭제해도 오버헤드가 없다. 상수 시간(Constant time)에, 쉽게말하면 엄청 빠른 시간에 중간의 요소를 삭제하고 삭제한 요소 전, 후의 요소가 이어진다. 이 원리는 아래 연결리스트를 코드로 작성해보면서 확인해보자.

 

 

노드의 구조

노드는 두가지 필드로 구성되어 있습니다.

[1] 값을 저장하는 필드

[2] 다음 노드의 위치(주소)를 가리키는 필드

 

먼저 Node의 Class를 아래와 같이 작성할 수 있다. Class 타입으로 생성했고 값과 다음 노드를 할당할 필드가 존재합니다.

 

//MARK: NODE
public class Node<Value> {

    //[1]값
    public var value: Value

    //[2] 다음 노드
    public var next: Node?

    //초기화
    public init(value: Value, next: Node? = nil) {

        self.value = value
        self.next = next
    }
}

/// Node 객체를 출력할 때 자신이 가지고 있는 값과 연결되어 있는 다음 node의 값 출력
extension Node: CustomStringConvertible {

  public var description: String {
    guard let next = next else {
      return "\(value)"
    }
    return "\(value) -> " + String(describing: next) + " "
  }
}

 

아래 처럼 3개의 노드를 생성하고 1부터 3까지 이어줍니다.

 

 

///각각의 노드 생성
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)

node1.next = node2
node2.next = node3

print(node1)
//출력 1 -> 2 -> 3

 

위에처럼 노드들을 let node1 = Node(value: 1) 이렇게 생성해서 

node1.next = node2 이런식으로 연결시켜줄 수도 있는데, 노드가 여러개가 생기면 관리하기가 번거로워질 수 있습니다. 그래서 노드들을 아래와 같이 한번에 연결하고 관리해줄 LinkedList를 만들어봅시다. LinkdedList는 일반적으로 두 개의 필드를 가집니다. 

 

[1] Head 필드 :  제일 첫번째 노드를 가리킵니다.

[2]Tail 필드 : 제일 마지막 노드를 가리킵니다. 그림에서는 D가 tail 노드, 꼬리 노드입니다.

 

 

//MARK: NODE를 관리하는 LinkedList
public struct LinkedList<Value> {

    ///머리
    public var head: Node<Value>?

    /// 꼬리
    public var tail: Node<Value>?

    public init() {}

    /// head가 nil이면 isEmpty는 true
    public var isEmpty: Bool {
        head == nil
    }
  }

extension LinkedList: CustomStringConvertible {

  public var description: String {
    guard let head = head else {
      return "Empty list"
    }
    return String(describing: head)
  }
}

 

이제 LinkedList 에 삽입과 삭제를 담당할 함수들을 넣어주어야 합니다. 먼저 LinkdedList에 값을 추가 하는 함수들을 넣어봅니다.

 

값을 추가하는 함수는 종류별로 3가지가 있습니다.

1.push: LinkdedList 제일 앞에 값을 추가합니다.

2.append: LinkdedList 제일 끝에 값을 추가합니다.

 

3.insert(after:) LinkdedList 특정 노드 뒤에 값을 추가합니다.

 

✅ push

LinkdedList 맨앞에 노드를 추가하는 push 함수는 아래와 같습니다.

head에 입력받은 value로 새 Node를 만들어서 할당해주고, 새 Node의 next에는 기존의 head를 할당해 줍니다.

즉, push 함수 에는 head가 가리키는 곳을 변경해주는 것이 핵심입니다.

 

 //MARK: PUSH
    /// 리스트의 맨 앞에 값 추가
    public mutating func push(_ value: Value) {

        //새로 들어온 값이 head가 되고 이전 head가 next 가 된다.
        head = Node(value: value, next: head)

        //꼬리도 비어 있으면 꼬리도 head를 참조하게 한다.
        if tail == nil {
            tail = head
        }
    }

 

✅ push 함수 테스트

LinkedList 에 push 함수로 Node들을 연결 시켜 주면 아래와 같이 출력이 됩니다. 

var list = LinkedList<Int>()

  list.push(3)
  list.push(2)
  list.push(1)

  print(list)
  
//1 -> 2 -> 3

---

 

✅ append

append는 LinkedList의 제일 끝에 Node를 추가하는 함수 입니다. 

먼저 LinkedList가 비어있는지 체크 해야 합니다. 비어있는 LinkedList에 append를 할 수 없습니다.

append는 LinkedList의 제일 끝 Node에 새로운 Node를 붙이는 것이기 때문입니다. 

그래서 LinkedList가 비어있으면 위에서 작성한 push 함수를 호출해줍니다.

 

LinkedList에서 Node가 하나라도 존재하면 tail의 next에 새로운 Node를 할당해주고

tail에 tail의 next를 할당해줍니다.

 

즉, 현재 제일 마지막 Node인 tail의 next에 새로운 Node를 할당.

(tail.next에는 제일 마지막 노드가 할당됨)

그리고 tail을 제일 마지막 Node인 tail.next를 할당해줌

 

 //MARK: APPEND
    /// 맨뒤에 추가
    public mutating func append(_ value: Value) {

        // 1.연결 리스트가 비어있으면 push
        guard !isEmpty else {
            push(value)
            return
        }

        // 2.tail의 next에는 추가된 Node 참조하게 처리(맨뒤에 붙이기)
        tail!.next = Node(value: value)

        // 3.tail에는 제일 마지막 Node 추가
        tail = tail!.next
    }

 

✅ append 함수 test

아래 처럼 LinkedList를 생성하고 위에서 만든 append 함수를 이용해서 1,2,3을 하나씩 붙여봅시다.

 

var list = LinkedList<Int>()

list.append(1)
list.append(2)
list.append(3)

print(list)
//출력 : 1 -> 2 -> 3

---

 

✅ insert(after:) 

마지막으로 특정 위치에 노드를 삽입하는 함수 입니다.

이 함수는 두 단계로 이루어집니다.

 

[1] LinkdedList에서 특정 노드를 찾기

[2] 새 Node를 삽입하기

 

먼저 Node를 어디에 삽입할 것인지 , 어느 Node 뒤에 삽입할 것인지 찾아야 합니다. 

이러한 역할을 하는 함수를 아래와 같이 작성합니다.

 

아래 함수는 제일 앞에 있는 Node인 head를 currentNode라는 변수에 할당하고

While 문을 이용해서 currentNode 에 currentNode의 next를 계속 할당해 주변서

인자로 받은 index의 이전 index를 찾을 때까지 반복문을 반복합니다.

 

예를들어 1->2->3 연결리스트에서 node(at index:1) 함수를 호출하면 어느 노드가 반환될까요?

일단  currentIndex = 0 이고 currentNode(현재 1) 도 비어 있지 않기 때문에 while문을 1번 돕니다.

 

그리고 currentNode는 currentNode.next(2) 가 할당이 됩니다. 그리고 currentIndex 는 + 1이 되어 1이 됩니다. While 조건문에서 index는 1인데, currentIndex가 1 이므로 currentIndex < index  조건을 만족하지 않기 때문에 while문을 빠져나오게 됩니다. 그럼 currentNode는 값이 2인 Node가 리턴이 됩니다.

 

    //MARK: 특정노드 찾기
    /// 중간에 삽입
    public func node(at index: Int) -> Node<Value>? {

        // 1.헤드노드 부터 검색 가능하기 때문에 가장 첫번째 노드 할당
        var currentNode = head
        var currentIndex = 0

        // 2.연결리스트가 비어있지 않고 && 입력받은 index 보다 currentIndex가 작을때까지
        while currentNode != nil && currentIndex < index {
        
            print("currentIndex : \(currentIndex)")

            // 찾는 node에 도달 할때 까지
            currentNode = currentNode!.next
            currentIndex += 1
        }
        return currentNode
    }

 

그리고 위에서 작성한 함수를 이용해서 insert 함수를 작성합니다. Insert 함수에는 , after node: Node<Value> 라는 인자가 있습니다. 위에서 만든 함수가 리턴하는 Node를 인자로 넣어줍니다. 이 노드를 대상 노드라고 하겠습니다. 참고로 새로운 노드는 대상 노드 뒤에 붙습니다.  이 함수 안에서도 조건이 있습니다.

 

[1] 대상 노드가 연결리스트의 제일 마지막 노드라면 ? insert를 해주는것이 아니라 append를 해주면 됩니다. insert는 연결 리스트의 중간 즉, 좌, 우에 노드가 있는 위치에서만 insert를 해줄 수 있습니다.

 

 

위의 [1] 조건에 해당안되면 //3번의 코드가 실행이 됩니다.

 

node.next는 대상 노드의 다음 노드 입니다.

대상 노드는 내가 값을 끼워넣을 기준 노드 입니다.

이 대상노드의 다음 노드에 새로운 노드를 삽입합니다.

그럼 이 새로운 노드의 다음 노드는 무엇일까요?

바로 대상노드가 가리키고 있던 다음(next) 노드가 되는것입니다.

 

 //MARK:INSERT

    // 1.경고무시
    @discardableResult // value 8, node 2
    public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {

        // 2. 대상노드가 tail 노드면 추가할 새 노드를 맨뒤에 붙이기
        // 대상 노드가 tail 노드면 즉, tail 노드 뒤에 insert 대신 append 하면되기 때문
        guard tail !== node else {
            append(value)
            return tail!
        }

        // 3.대상 노드가 tail 노드가 아니라면
        // 새 노드의 next는 대상 노드의 next가 된다.
        // 대상 노드의 next는 ,즉 대상 노드 next(다음)에 새로운 추가할 노드를 넣는다.
        node.next = Node(value: value, next: node.next)

        // 대상 노드의 다음 노드 부터 리턴
        return node.next!
    }

 

✅ Insert test

일단 어떤 노드 뒤에 새로운 노드를 끼워넣을것이냐?

대상 노드를 찾아보면  

var middleNode = list.node(at: 1)!

 

1번째 index

 

아래처럼 값이 2인 Node가 리턴이 됩니다. 

(왜 2가 리턴되는지 이해가 되어야 됩니다..위의 node 함수에서 설명해 놓은거 한번 더 확인..)

 

print("middleNode:\(middleNode)") 

//middleNode:2 -> 3 -> 4

 

그리고 8이라는 값을 새로운 노드로 2 뒤에 추가해 봅시다.

 

middleNode = list.insert(8, after: middleNode)

 

print("middleNode:\(middleNode)")

print("After inserting one: \(list)")

 

2와 3 노드 사이에 8이 들어 갔습니다.

 

middleNode:8 -> 3 -> 4  

After inserting one: 1 -> 2 -> 8 -> 3 -> 4  

 

✅ Insert 전체 테스트 코드

var list = LinkedList<Int>()
list.push(4)
list.push(3)
list.push(2)
list.push(1)

print("Before inserting: \(list)")

//해당 노드를 찾고
var middleNode = list.node(at: 1)!

print("middleNode:\(middleNode)") //middleNode:2 -> 3 -> 4
print("")

middleNode = list.insert(8, after: middleNode)
print("middleNode:\(middleNode)")
print("After inserting one: \(list)")
print("")

middleNode = list.insert(9, after: middleNode)

print("middleNode:\(middleNode)")
print("After inserting two: \(list)")


//출력
Before inserting: 1 -> 2 -> 3 -> 4   

currentIndex : 0
middleNode:2 -> 3 -> 4  

middleNode:8 -> 3 -> 4  
After inserting one: 1 -> 2 -> 8 -> 3 -> 4    

middleNode:9 -> 3 -> 4  
After inserting two: 1 -> 2 -> 8 -> 9 -> 3 -> 4

 

LinkdedList.zip

0.04MB

 

참고

코딩퀴즈 - ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9%ED%80%B4%EC%A6%88/id1625309702

코딩퀴즈 - aos

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication

 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/v3.0/chapters/6-linked-list