[Swift:자료구조] LinkedList 1편 : Node 와 LinkedList 에 추가하기

Newon·2022년 7월 7일
linkedlistswift
0

스위프트 자료구조

목록 보기
2/3
post-thumbnail

LinkedList 란?

링크드리스트는 특정 값들을 일렬로, 그것도 단방향으로 저장하는 형태의 자료구조를 의미합니다.

이때 링크드리스트가 담고 있는 값의 형태를 노드(node) 라고 표현합니다.
노드는 값 과 다음 노드의 메모리 주소 를 갖고 있습니다.
만약 다음 노드가 없다면 메모리주소에는 nil 을 할당합니다.
이는 해당 노드가 링크드리스트의 마지막임을 뜻하기도 합니다.

상단의 그림에서 노드는 총 3개로, 편의상 왼쪽부터 노드 1,2,3 으로 부른다면

  • 노드 1 : 12 값과 노드 2의 메모리주소를 가진 노드
  • 노드 2 : 99 값과 노드 3의 메모리주소를 가진 노드
  • 노드 3 : 37 값과 다음 메모리 주소가 없는 노드

로 구분할 수 있습니다.
노드의 값은 중복될 수 있지만, 메모리주소는 당연히 중복될 수 없습니다.
메모리 내 같은 공간에 2개의 정보를 동시에 담을 순 없으니까요 :)
하지만 양자 컴퓨터가 나온다면 어떨까? 양.자.컴.퓨.터


노드 구현

링크드리스트를 구현하기 이전에, 링크드리스트에 포함될 노드를 먼저 구현해보겠습니다.

class Node<T> {
	var value: T
    var next: Node?
    
    init(value: T, next: Node? = nil) {
    	self.value = value
        self.next = next
    }
}

// 밑의 코드는 print 시 편의를 위해 사용 
// 출처 : raywenderlich node
extension Node: CustomStringConvertible {
	var description: String {
    	guard let next = next else {
        	return "\(value)"
        }
        return "\(value) -> " + String(describing: next) + " "
    }
}

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

노드를 구현한 class 를 확인해보겠습니다.

우선 struct 가 아닌 class 로 구현되어 모든 노드들이 참조 타입 이 되도록 설정되었습니다. 이는 next 가 다음 노드의 메모리 주소를 참조한다는 것으로 이어집니다.

class 내부는 간단하게 되어있습니다. 제네릭타입으로 어떤 형태든 값을 받을 수 있는 var value: T 와 다음 노드를 저장할 next, 그리고 생성 시 초기화를 위한 init 이 있습니다.

* 여기서 T는 제네릭 타입으로, 어떤 자료형이든 초기에 받는
그 자료형을 이 변수의 자료형으로 사용하겠다 라는 의미입니다.
Int 를 주면 앞으로는 Int, String 을 주면 String,
자신이 생성한 구조체를 주면 그 구조체가 됩니다.
T 는 임의의 명칭으로, 자유롭게 바꿔서도 쓸 수 있습니다.

이후 하단에서 node1, node2, node3 을 생성하고
각각 1,2,3 이라는 값을 준 후, 1의 next 를 2, 2의 next를 3으로 주고
출력을 했더니

쨔잔 1 -> 2 -> 3 이라는 굉장히 직관적인 결과가 나왔습니다.
노드는 이와 같이 값과 다음 노드의 메모리주소를 갖는 class 입니다.


만약 struct 로 class 를 구현하면 어떻게 될까요?
그렇다면 Hashable, Equtable 프로토콜을 준수하도록 하고, 이후 메소드에서도 계속해서 값이 아닌 참조를 하도록 강제해야 합니다.

왜냐하면 struct 는 생성 및 할당 시 새로운 인스턴스를 생성, 즉 매번 새롭게 메모리에 적재되는 값 타입 인 반면 class 는 할당을 하더라도 그 주소가 할당되는 참조 타입 이기 때문입니다. 자세한 내용은 값 타입과 참조 타입을 확인해주세요.


LinkedList 구현

struct LinkedList<T> {
	var head: Node<T>?
    var tail: Node<T>?
    
    init() { }
    
    var isEmpty: Bool {
    	head == nil
    }
}

// 밑의 코드는 print 시 편의를 위해 사용 
// 출처 : raywenderlich node
extension LinkedList: CustomStringConvertible {
	var description: String{
    	return "Empty list"
    }
    return String(describing: head)
}

Linked List 구조체를 만들어보았습니다.
Node<T>? 를 받는 2개의 변수 head 와 tail 이 있고,
head 가 nil 이면 이 링크드리스트는 비어있다 라고 표현하고 있네요.


위의 그림을 다시 가져와서 살펴보면
head 는 링크드리스트의 가장 첫번째 노드를 의미합니다.
tail 은 next 가 없는 노드, 즉 링크드리스트의 가장 마지막 노드를 의미합니다.

만약 head 의 next 가 없다면 head 는 tail 이기도 한거죠!

LinkedList 를 구현해보았지만, 무언가가 많이 부족합니다.
아직까지는 LinkedList 에 노드를 추가할수도, 삭제할수도 없기 때문입니다.

앞으로 push, append, insert 메소드를 구현해서 노드를 추가해보고
pop, removeLast, remove(after:) 메소드를 구현해서 노드를 삭제해보겠습니다.

많냐

LinkedList - 노드 추가하기

LinkedList 에는 3개의 방법으로 노드를 추가할 수 있습니다.

  1. push : 링크드리스트의 가장 앞에 node 를 추가합니다.
  2. append : 링크드리스트의 가장 맨 뒤에 node 를 추가합니다.
  3. insert(after:) : 링크드리스트 내 특정 노드 뒤에 노드를 추가합니다.

push

struct LinkedList<T> {
	...
    mutating func push(_ value: T) {
    	head = Node(value: value, next: head)
        if tail == nil {
        	tail = head
        }
    }
}

// 출력 예제
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

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

push 메소드는 추가하고자 하는 값을 알려주면
그 값을 지닌 Node 를 만들어서 head 로 선언해주고,
동시에 이전의 head 는 next 로 선언해줍니다.

이때 만약 tail 이 nil 이였다면 (== 처음 노드를 넣는다면)
tail 을 head 로 지정합니다.

append

struct LinkedList<T> {
	...
    mutating func append(_ value: T) {
    	guard !isEmpty else {       // 1️⃣
        	push(value)
            return
        }
        
        tail!.next = Node(value: T) // 2️⃣
        tail = tail!.next           // 3️⃣
    }
}

// 출력 예제
var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)

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

append 메소드는 추가하고자 하는 값을 알려주면
링크드리스트의 가장 마지막에 해당 노드를 만들어 추가해줍니다.

이때 로직은 3단계로 나누어집니다.

  1. 만약 LinkedList 가 비어있다면, 이는 push 와 동일하기에 push 에 값을 넘겨주고 종료합니다.
  2. LinkedList 가 비어있지 않다면, tail 의 next 에
    전달받은 값으로 Node 를 생성하고 next 로 지정합니다.
  3. tail 을 tail!.next 로 설정합니다.
    이때 tail 은 반드시 존재하니 ! 로 옵셔널을 해제해줍니다.

insert(after:)

insert 는 해당 링크드리스트의 특정 노드 뒤에 새로운 노드를 추가하는 메소드입니다.

단, 바로 작성하기에는 문제가 하나 있는데
왜냐하면 지금 우리는 특정 노드가 몇번째에 있는지 알 수 없기 때문입니다.

노드들은 중복된 값을 가질 수 있고, 한편 LinkedList 는 [] 를 통해서 접근할 수 도 없으니 우선 해당 노드가 몇번째 노드인지 먼저 찾는 메소드부터 작성하고서, 그 후에 원하는 값을 노드로 추가해줄 수 있게됩니다.

struct LinkedList<T> {
	...
    func find(at index: Int) -> Node<T>? {
    	// 1️⃣
    	var currentNode = head
        var currentIndex = 0
        
        // 2️⃣
        while currentNode != nil && currentIndex < index {
        	currentNode = currentNode!.next
            currentIndex += 1
        }
        return currentNode
    }

find(at:) 메소드는 찾고자하는 노드의 인덱스를 주면
해당 인덱스에 해당하는 노드를 찾는 메소드입니다.
그것이 메소드니까..?

  1. 현재노드와 현재 인덱스를 변수로 선언하고, 각각 head 와 0 을 줍니다.
  2. 현재노드 변수는 계속해서 다음 노드를, 현재 인덱스는 계속해서 1을 더해가며 해당 인덱스를 찾거나, tail 다음(nil)에 도달할 때 까지 인덱스에 해당하는 노드를 찾습니다.
  3. 원했던 노드를 리턴합니다.

이제 find 를 통해 insert(at:) 을 구현해보겠습니다.

struct LinkedList<T> {
	...
    // 1️⃣
    @discardableResult
    mutating func insert(_ value: T, after node: Node<T>) -> Node<T> {
    	// 2️⃣
    	guard tail !== node else {
        	append(value)
        	return tail!
        }
    	
        // 3️⃣
        node.next = Node(value: value, next: node.next)
        return node.next!
    }
	    
}

// 출력 예제
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)

print("insert 이전의 링크드리스트 : \(list)")
var middleNode = list.node(at: 1)!
for _ in 1 ... 4 {
	middleNode = list.insert(-1, after: middleNode)
}
print("insert 이후의 링크드리스트 : \(list)")

// insert 이전의 링크드리스트 : 1 -> 2 -> 3
// insert 이후의 링크드리스트 : 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3
  1. @discardableResult 는 해당 함수의 리턴값이 사용되지 않더라도, Swift 컴파일러가 경고해줄 필요는 없다라는 의미입니다.
    insert 후에 해당 결과값이 필요할 수도 있지만, 안 필요한 경우가 더 많기 때문에 눈뽕 경고창을 해당 띄우지 않도록 설정해줍니다.
  2. 만약 특정 노드가 링크드리스트의 tail 이였다면, 이는 append 와 동일한 메소드가 됩니다. append 에 값을 넘겨주고 종료합니다.
  3. append 에서 했던 코드와 유사합니다.
    해당 노드의 next 에 새로운 노드를 만듦과 동시에 새로운 노드의 next 는 기존 노드의 next 로 설정해줍니다.

3번의 경우 한 줄의 코드가 2개의 행동,
특정 노드의 next 를 내가 준 값의 새로운 노드로 설정 과
내가 준 값의 새로운 노드의 next 는 특정 노드의 원래 next 로 설정!

이 한번에 진행되어 헷갈릴 수 있지만 위와 같은 내용으로
insert(after:) 메소드를 만들 수 있습니다.


각 추가 메소드들의 시간복잡도 분석

linkedList 각 메소드들 시간 복잡도 분석

모든 메소드들이 O(1) 로, 단 한번에 노드를 추가할 수 있음을 확인할 수 있습니다 !

왜일까요 ?

다른 노드들을 밀거나, 미루거나의 행동 없이
head, tail 혹은 next 만 재설정해주면 되기 때문입니다.

단, insert(after:) 를 위해서 특정 노드가 몇번째 노드인지 확인하는 행동에는 o(index) 만큼의 시간이 걸린다는 걸 확인할 수 있습니다.



그럼 다음 편에서 삭제를 알아보자네 !
빠이네 !

참고

Data Structures & Algorithms in Swift - fourth Edition
위키백과

profile
Newon
나만 고양이 없어
이전 포스트

[Swift:자료구조] Stack 와 struct

다음 포스트

[Swift:자료구조] LinkedList 2편 : LinkedList 에 노드 삭제하기

0개의 댓글