[Swift 자료구조] 1. List

Ted·2023년 3월 12일
0

자료구조

목록 보기
1/1
post-thumbnail

리스트는 목록 형태로 이루어진 데이터 형식이며 리스트는 노드라는 개별 요소를 통해서 목록을 이룬다. 보통 리스트의 처음 노드를 헤드, 마지막 노드를 테일이라고 부른다. 리스트에는 기본적으로 Append, Insert, Remove, GetAt의 연산을 갖추고 있다.

1. 리스트와 배열

기본적으로 리스트와 가장 많이 비교되는 것이 배열이다. 배열은 리스트처럼 데이터 목록을 다룬다. 배열은 배열을 생성하는 시점에서 반드시 배열의 크기를 지정하게 되며 생성되고 난 후엔 그 크기를 변경할 수 없다. 하지만 리스트는 배열처럼 집합 보관 기능을 가지면서 동시에 크기를 유연하게 바꿀 수 있다.

1.1 배열

배열은 index를 사용하여 한 메모리 공간 안에 데이터들이 나란히 저장되어있는 형태이다.


이와 같이 배열의 경우 index만 안다면 값에 대한 접근이 매우 빠르다. 하지만 마지막 index가 아닌 element를 삭제하거나 삽입할 경우에 element를 재배치해야하므로 오버헤드가 발생하여 시간이 오래 걸린다.

1.2 리스트

그래서 이를 해결하는 것이 LinkedList이다.

원하는 때에 메모리에 공간을 할당해서 쓰고 배열과 같이 중간에 element를 삽입, 삭제 시에 재배치하는데 오버헤드도 발생하지 않아 좋다.

하지만 이 단방향인 LinkedList는 데이터에 접근하기 위해서 첫 번째 데이터부터 찾고자하는 데이터까지 순차적으로 찾아가야 하므로 배열에 비해선 접근 속도가 상당히 느리다. 그리고 다음 데이터에 대한 연결 정보를 저장하는 별도의 데이터 공간이 필요하기에 저장 공간의 효율도 높지 않다는 단점이 존재한다.

1.2.1 단방향 연결 리스트 (LinkedList)

일단 단방향 연결리스트부터 살펴보자.

리스트를 구현하는 여러 가지 기법 중에서도 가장 간단한 기법이다. LinkedList는 말그대로 노드를 연결해서 만든 리스트이며 노드는 데이터를 보관하는 필드, 다음 노드와 연결 고리 역할을 하는 포인터로 이루어 진다.

데이터와 포인터로 이루어진 노드들을 모두 주렁주렁 엮게되면 LinkedList가 되는 것이다.

노드를 생성해보자.

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

이렇게 구현이 된다. Swift의 경우 데이터 타입에 대한 제한이 강하므로 데이터 타입에 국한되지 않게 Generic< T >로 선언해준다.

이것을 이용해서 LinkedList 클래스를 구현하고 필요 기능들을 구현해보자.

1.2.2 Append

class LinkedList<T> {
	private var head: Node<T>?
}

로 일단 헤드를 구성하고 LinkedList 맨 마지막에 노드를 추가하는 코드를 구현해보자.

노드의 가장 마지막을 찾는 방법으론 head노드부터 돌면서 한 Node의 다음 노드가 가리키는 값이 nil인 경우를 찾으면 된다.


func append(data: T?) {
	if head == nil {
    	head = Node(data: data)
        return
    }
    
    var node = head
    while node?.next != nil {
    	node = node?.next
    }
    node?.next = Node(data: data)
}

이런 식으로 말이다.

1.2.3 Insert

다음은 연결리스트의 중간에 노드를 추가하는 방식이다..

연결리스트의 경우 배열과 달리 index가 없기 때문에 중간에 추가하거나 삭제하는 것이 상당히 귀찮다.

func insert(data: T?, at index: Int){
	if head == nil {
    	head = Node(data: data)
        return
    }
    
    var node = head
    for _ in 0..<(index - 1) {
    	if node?.next == nil { break }
        node == node?.next
    }
    
    let nextNode = node?.next
    node?.next = Node(data: data)
    node?.next?.next = nextNode
}

찾고 있는 index가 Node의 범위를 벗어나게 되면 가장 마지막 추가해주는 방식이다. 노드 간 연결만 바꿔주는 식으로 중간에 삽입을 구현한다.

1.2.4 Remove

연결리스트의 맨 마지막 노드를 삭제하는 것 또한 앞과 비슷하다. 찾고자 하는 값을 찾아 그 노드와 연결된 노드들을 끊고 끊긴 두 노드를 붙인 다음 해당 노드를 소멸시키면 된다.

다음 코드는 맨 마지막 노드를 삭제하는 코드이다.

func remove() {
	if head == nil { return }
    
    if head?.next == nil {
    	head = nil
        return
    }
    
    var node = head
    while node?.next?.next != nil {
    	node = node?.next
    }
    
    node?.next = node?.next?.next
}

다음 코드는 중간 노드를 삭제하는 코드이다.

func remove() {
	if head == nil { return }
    
    if index == 0 || head?.next == nil {
    	head = head?.next
        return
    }
    
    var node = head
    for _ in 0..<( index - 1 ) {
    	if node?.next?.next == nil { break }
    	node = node?.next
    }
    
    node?.next = node?.next?.next
}

왜 이 코드에는 python과는 다르게 del 메서드가 없냐라고 할 수 있는데 python은 del을 호출해야 메모리에서 제거가 되지만 Swift의 경우 Node를 class로 구현했기 때문에 ARC(Automatic Reference Counting)에 의해서 참조만 끊어주면 알아서 메모리에서 해제가 되기 때문에 필요가 없다.

자세한 설명은 이 게시물을 참고해주길 바란다.
Swift ARC에 관한 내용

1.2.5 SearchNode

노드를 저장된 데이터에서 검색하여 값을 반환하는 코드를 살펴보자

func search(from: T?) -> Node<T>? {
	if head == nil { return nil }
    
    var node = head
    while node?.next != nil {
    	if node?.data == data { break; }
        node = node?.next
    }
    
    return node
}

라고 짜면된다. 하지만 Swift에선 오류를 발생시킨다.
search에서 node?.data와 data를 비교하지 못하게 하기 때문이다. 두 값 전부 제네릭으로 선언되어 있고 프로토콜이 채택되어있지 않기에 그렇다.

따라서 Equatable이라는 프로토콜을 채택하여 만들어 줘야한다. 어디에? LinkedList 클래스에!!

class LinkedList<T: Equatable> {
	private var head: Node<T>?
}

1.3 양방향 연결리스트

앞에서 보았듯이 단방향 연결리스트의 경우 배열과 다르게 원하는 값을 찾는데에 상당한 시간을 허비하는 것을 볼 수 있었다. 그래서 이를 해결하기 위해 양방향 연결리스트를 공부해보자.

가장 첫 노드를 가리키는 head와 마지막을 가리키는 tail, 하나의 저장공간을 더 추가한 형태이다.

양방향 연결리스트를 통해서 역행이 가능하다는 점에서 탐색 시간은 두 배가량 줄었다.

내 이전 노드와 다음 노드 두 노드를 모두 연결하여 양방향에서 탐색을 가능하게 한 것이다.

하지만 이 방법의 경우 공간 복잡도가 좋지않다. 각 노드마다 이전 노드까지 저장해야하고 tail도 알아야한다.

그럼 구현해보자.

1.3.1 Append

일단 노드를 생성한다.

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

제네릭 T를 사용하지 않으려면 이렇게 만들 수 있다.

class Node{
	var prev: Node?
    var data: Int = -1
    var next: Node?
    
    init(data: Int, prev: Node? = nil, next: Node? = nil) {
    	self.prev = prev
        self.data = data
        self.next = next
    }
}

다음은 Node를 관리하는 DoublyLinkedList 클래스를 만들어 준다.

class DoublyLinkedList<T: Equatable> {
	private var head: Node<T>?
    private var tail: Node<T>?
    // var size: Int = 0
    // var isEmpty: Bool { size == 0 }
}

다음엔 양방향 연결리스트 맨 마지막에 노드를 추가해보려 한다. 단방향의 경우 head부터 마지막까지 가서 추가를 해줘야 했지만 이젠 그럴 이유가 없다.

func append(data: T?){
	if head == nil || tail == nil {
    	head = Node.init(data: data)
        tail = head
        return
    }
    
    let newNode = Node.init(data: data)
    tail?.next = newNode
    newNode.prev = tail
    tail = newNode
}

현재 tail의 next에 newNode를 연결하고 newNode의 prev를 현재 tail에 연결한 다음 tail을 newNode로 바꾸면 된다.

이런 방식도 있다.

func append(data: Int){
	let newNode = Node(data: data)
    
	if isEmpty {
    	head = newNode
        tail = head
    } else {
    	tail?.next = newNode
        newNode.prev = tail
        tail = newNode // tail을 새로 설정
    }
}

1.3.2 removeLast

없앨 노드의 바로 이전 노드의 next를 nil로 바꾸면서 tail의 위치를 변경하면 된다.

func removeLast(){
	if head == nil || tail == nil { return }
    
    if head?.next == nil {
    	head = nil
        tail = nil
        return
    }
    
    tail?.prev?.next = tail?.next
    tail = tail?.prev
}

중간에서 삭제를 하는 경우이다.

func remove(at index: Int) { // index를 사용하여 하는 방법이다. 배열과 비슷하다.
	if isEmpty {
    	return
    } else if index <= 0 {
    	removeFirst()
    } else if index <= size {
    	removeLast()
    } else {
    	let half = size / 2
        let isForward = ( index <= half )
        
        var node: Node?
        if isForward {
        	node = head
            for _ in 0..<index {
            	guard let next = node?.next else { break }
                node = next
            }
         } else {
         	node = tail
            for _ in 0..<(size - index - 1) {
            	guard let prev = node?.prev else { break }
                node = prev
            }
         }
         
         node?.prev?.next = node?.next
         node?.next?.prev = node?.prev
         
         size -= 1
    }
    
    if isEmpty {
    	head = nil
        tail = nil
    }
    
    return
}

다음은 모든 노드를 삭제하는 경우다.

func removeAll() {
	head = nil
    tail = nil
    
    size = 0
}

ARC에 의해서 자연스레 수거된다. 시간복잡도도 O(1)

1.3.3 searchNode

head에서부터 특정 데이터로 노드 찾는 방법
만약 특정 데이터가 연결리스트 앞에 위치한다면 쓰면 된다.

func searchNode(from data: T?) -> Node<T>? {
	if head == nil || tail == nil { return nil }
    
    var node = head
    while node?.next != nil {
    	if node?.data == data { break }
        node = node?.next
    }
    
    return node
}

이번엔 tail로 찾는 방법이다.

func searchNodeFromTail(from data: T?) -> Node<T>? {
	if head == nil || tail == nil { return nil }
    
    var node = tail
    while node?.prev != nil {
    	if node?.data == data { break }
        node = node?.prev
    }
    
    return node
}

1.3.4 Insert

func insert(data: Int, at index: Int) {
	let newNode = Node(data: data)
    
    if isEmpty {
    	head = newNode
        tail = head
        
        size += 1
        return
        
    } else if index <= 0 { // 가장 앞에 넣는 경우
    	newNode.next = head
        head?.prev = newNode
        head = newNode
        
        size += 1
        return
        
    } else if index >= size { // 가장 뒤에 넣는 경우
    	append(data: data)
        return
        
    } else { // 중간에 넣는 경우
    	let half = size / 2
        let isForward = (index <= half)
        
        var node: Node?
        if isForward { // 찾는게 앞에 있다면
        	node = head
            for _ in 0..< index - 1 {
            	guard let next = node?.next else { break }
                node = next
            }
        } else {
           	node = tail
            for _ in 0..<( size - index ) {
                guard let prev = node?.prev else { break }
                	node = prev
            }
        }
            
        node?.next?.prev = newNode
        newNode.next = node?.next

        newNode.prev = node
        node?.next = newNode

        size += 1
        return
    }
}

삽입에서의 최악의 경우는 중간 삽입이다. 코드가 긴걸 볼 수 있듯이...

사실 LinkedList의 경우 잘 사용되는 방법은 아니다. 다음 노드를 가리키는 주소가 하나라도 잘못되면 이후의 모든 연결이 끊어지기 때문이다.

그리고 중간의 값에 대해 뭔가 하려하면 데이터의 양이 수만이 넘어가는 순간 엄청 오래걸리게 된다. 이럴 때는 cursor나 center를 사용하여 최적화를 시키는 작업이 필요하다.

하지만 OS에서 free block을 관리하는데 LinkedList가 사용되어 필수 요소이기도 하다. 잘 쓴다면 유리한 자료구조로 쓰일 수 있다.

profile
iOS Developer

0개의 댓글