LinkedList

오늘은 모든 자료 구조의 base라고 할 수 있는 Linked List 중에서 Single Linked List에 대해서 알아보고 직접 코드로 구현해 볼 예정이다.

Single Linked List 개념

위의 그림이 바로 Single Linked List라고 할 수 있다. 그림에서 보듯이 각각의 노드는 data 만 가지는 것이 아니라 reference field, 즉 다음 노드를 가르키는 정보도 가지는 것을 확인해 볼 수 있다.

위와 같은 노드를 간단하게 작성해 보면 다음과 같이 작성할 수 있다.

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

배열과는 다르게 우리는 single-linked list의 random element에 상수 시간내에 접근을 할 수 없다. 즉, 우리가 ith 번째 element에 접근을 하고 싶다면 우리는 head node부터 순차적으로 하나씩 다음 노드를 통해서 접근해야한다. 따라서 linked-list의 길이가 N이라고 하면, 평균적으로 index를 통해서 element에 접근을 하려면 O(N) 이라는 시간 복잡도를 가지게 된다.

위의 그림을 통해서 예시를 들어보면, head node는 23이 되게 되고 3번째 element에 접근을 하기 위한 방법은 오직 head node에서 두 번째 노드를 가르키는 next 노드를 사용해야하고, 그 다음에도 마찬가지로 세번째 노드를 가르키는 6의 next 노드를 통해서 3번째 element에 접근할 수 있다.

여기까지만 본다면 배열은 index를 통한 접근에 O(1) 이라는 시간 복잡도가 걸리는데 굳이 O(N)의 시간 복잡도가 걸리는 비효율적인 linked list를 왜 사용해야할까? 라는 의문을 가질 수도 있다. 이에 대해서는 앞으로 나올 insert 와 delete 연산에 대해서 알아보면 해결할 수 있을 것이다.

Add Operation

만약 linked-list에 prev 다음에 새로운 원소를 추가해주고 싶다면 다음과 같은 과정을 따라야 할 것이다.
1. 새로 추가할 노드인 cur 노드에 data 값을 주면서 초기화를 해준다.

2. cur 노드의 next를 prev가 가르키고 있는 next를 가르키게 한다.

3. prev노드의 next를 cur로 변경해준다.

만약 배열에서 원소들 사이에 새로운 원소를 추가한다고 하면, 해당 원소를 삽입하고 이후의 원소들을 전부 한 칸씩 이동해 주어야하는 비용이 발생하게 되며 이러한 비용은 평균적으로 O(N) 의 시간복잡도가 걸린다.
반면에 linked-list의 경우에는 원소들 사이에 새로운 원소를 삽입하는데 링크들만 변경해 주면 되므로 O(1) 이라는 시간복잡도를 가지게 된다.

다시 처음의 그림으로 예시를 들어보면 다음과 같다.

여기서 6과 15사이에 새로운 원소인 9를 삽입한다고 할 때 다음과 같다.
먼저 cur노드를 9로 초기화하고, 9의 next를 15로 지정해준다. 마지막으로 6의 next를 9로 연결해주면 아래의 그림과 같은 결과를 확인할 수 있다.

Add Node at the Beginning

linked-list는 전체 리스트를 대표하는 head 노드를 가지고 있다. 따라서 만약 맨 처음에 원소를 넣게 된다면 head 노드를 업데이트 해주는 것이 중요하다.
1. new node인 cur 노드를 새로운 값과 함께 초기화한다.
2. new node인 cur 를 원래의 head에 연결해준다.
3. cur 를 head 로 할당해준다.
위의 그림에서 9를 list의 맨 처음에 삽입한다고 해보자. 9라는 값을 가진 새로운 노드를 생성하고 cur의 next를 기존의 head에 연결해준다.

다음은 cur를 head로 변경해주면 된다.

Delete Operation

linked-list에서 cur 노드를 삭제하고 싶은 경우에는 어떻게 해야할까?
다음과 같은 단계를 거쳐야 할 것이다.
1. cur 노드의 전 노드인 prev 노드와 다음 노드인 next 를 찾아야 한다.

2. prev 노드의 next를 cur에서 next 노드로 변경해주면 된다.

이 과정에서 삭제 연산의 시간복잡도는 어떻게 될까?
첫 번째 단계에서 linked-list의 cur 노드의 prev 와 next 를 찾아야한다고 했는데, 이는 head로 부터 cur 까지 순차적으로 접근하면 되므로 어려운 일은 아니다. 하지만 linked-list의 개념을 소개할 때 말했듯이 list의 사이즈가 N이라고 할 때 평균적으로 i번째 원소에 접근하는의 시간복잡도는 O(N) 이라고 했다. 따라서 cur 까지의 접근시간인 O(N) 이 바로 delete 연산의 시간복잡도이다.

delete the First Node

만약 첫 번째 노드인 head node를 삭제하는 것은 어떻게 해야할까? 이는 삽입 연산과 비슷하게 head 를 업데이트 해주는 것이 중요하다.
아래의 그림에서 head 인 23을 삭제한다고 해보자.

그렇다면 head 노드의 다음 노드인 6을 새로운 head로 지정해주어야한다. 그리고 나서 23을 가지는 노드를 삭제해주면된다.

Array VS Linked-List

배열의 장점과 단점

장점 : 항목 접근 속도가 빠르고 일정하다.

배열은 자료형에 따라 한 배열 항목의 크기가 결정이 된다. 
4byte INT 데이터를 담는 배열을 선언하는 경우, 항목 크기 역시 4byte가 된다. 
배열의 기본 주소는 배열의 맨 처음 부분을 가르키고, 블럭 단위로 메모리를 차지한다. 
따라서 "기본주소 + (자료형의 크기 x Index)"로 특정 인덱스에 위치한 항목에 접근할 수 있다. 
예를 들면 INT 배열 5번 인덱스에 접근할 때에는 (기본주소 + 4 * 5)를 계산한 결과로 나온 메모리를 찾아가면 찾을 수 있다.
따라서 이처럼 위치에 상관없이 한 번의 연산으로 항목을 찾아 갈 수 있어서 접근 속도가 빠르다.

단점 
1. 크기가 고정되어 있다. 사용하기 전에 배열 크기를 지정해야한다.
(물론 동적배열로 해결이 가능하나 동적배열의 경우에도 배열이 꽉차면 기존의 크기의 2배씩 크기를 늘리므로 비효율적이다.)

2. 메모리를 한 덩어리로 차지하므로, 배열 크기가 큰 경우 배열 전체를 위한 메모리를 할당 받지 못하는 경우가 있다.

3. 삽입이 복잡하다.
(배열은 중간에 삽입하려면 우선 기존에 있는 항목들을 밀어내고 해당 공간을 비워야하므로 최대 N번의 항목이동이 발생한다.)

Linked-List의 장점과 단점

장점 : 삽입이 간단하며 항목 생성 후 포인터 값만 변경해주면 된다.

단점
1. 항목 접근이 오래 걸린다.
첫 항목부터 순차적으로 접근하므로 최소는 O(1)부터 최대 O(N)의 시간이 걸린다.

2. 물리적으로 인접한 메모리에 위치해있지 않다.
배열의 항목은 물리적으로 인접해있어 접근 시간 단축과 캐싱에 유리하다고 하지만 연결리스트는 그렇지 않다.

3. 참조 포인터를 위한 메모리 공간이 낭비된다. 

어떠한 상황에 Array를 사용해야하며 어떠한 상황에 Linked-List를 사용해야 할까?
저장할 데이터의 개수가 정해져 있고 리스트의 중간에 데이터를 삽입, 삭제하는 작업이 많지 않으며 인덱스를 이용한 빠른 검색이 필요한 경우에는 배열을 사용하는 것이 효율적이다.

반면 저장될 데이터의 개수가 정해져 있지 않고 리스트의 중간에 데이터를 삽입, 삭제하는 작업이 많고 삽입, 삭제에 비해서 특정 위치의 데이터를 검색하는 작업이 많지 않을 경우 연결 리스트를 사용하는것이 효율적이다

Single-Linked-List code in Swift

코드의 작성은 leetcode에서 Single-Linked-List를 구현하는 페이지에서 진행하였다. 구현해야하는 사항은 다음과 같다.

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the index'th node in the linked list. If the index is invalid, return -1.
• void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the index'th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Delete the index'th node in the linked list, if the index is valid.

class MyLinkedList {
    
    class Node {
    var data: Int
    var next: Node?
    init(data: Int, next: Node? = nil) {
        self.data = data
        self.next = next
        }
    }
    var head: Node?
    
    init() {
        self.head = nil
    }
    
    func get(_ index: Int) -> Int {
        guard let node = node(at: index) else {
            return -1
        }
        return node.data
    }
    
    func node(at: Int) -> Node? {
        guard at > -1, var node = head else {
            return nil
        }
        guard at > 0 else {
            return head
        }
        for _ in 1...at {
            guard let nextNode = node.next else {
                return nil
            }
            node = nextNode
        }
        return node
    }
    
    func addAtHead(_ val: Int) {
        let newNode = Node(data: val, next: head)
        self.head = newNode
    }
    
    func addAtTail(_ val: Int) {
        guard head != nil else {
            head = Node(data: val)
            return 
        }
        var node = head
        while node?.next != nil {
            node = node?.next
        }
        node?.next = Node(data: val)
    }
    
    func addAtIndex(_ index: Int, _ val: Int) {
        if index <= 0 {
            addAtHead(val)
            return
        }
        guard let prevNode = node(at: index - 1) else {
            return
        }
        let newNode = Node(data: val, next: prevNode.next)
        prevNode.next = newNode
    }
    
    func deleteAtIndex(_ index: Int) {
        if index == 0, head != nil {
            head = head?.next
            return
        }
        guard let prevNode = node(at: index - 1) else {
            return
        }
        prevNode.next = prevNode.next?.next
    }
}

참고 링크

leetcode single-linked-list
배열과 연결리스트