[자료구조] 단순 연결 리스트( Singly Linked List )

한쪽으로만 연결이 되어 있는 자료구조입니다.

단순 연결 리스트 의 가장 큰 특징은 연속되지 않은 데이터끼리의 연결 입니다.

 

 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.

원하는 위치의 데이터의 추가는 O(n+1) 의 시간복잡도를 갖습니다.

 

 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다.

원하는 위치의 데이터의 제거는 O(n+1) 의 시간복잡도를 갖습니다.

 

데이터에 순차적으로 접근해야 해서 데이터 접근 속도가 느립니다.

ex) list.head.next?.next?.next?.value

다음 데이터의 연결을 저장하는 공간이 필요해서 공간 효율이 좋지 않습니다.

 

Singly Linked List 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다.

단순 연결 리스트_001

아래 그림과 같이 동작하게 됩니다.

fisrt	Singly Linked List 에서 제일 앞에 있는 데이터 입니다. == head
last	Singly Linked List 에서 제일 뒤에 있는 데이터 입니다.
append	Singly Linked List 가장 뒤에 데이터를 추가합니다.
insert(item: , index: )	Singly Linked List 의 index 위치에 데이터를 추가합니다.
remove(index: )	Singly Linked List 의 index 위치의 데이터를 제거합니다.

단순 연결 리스트_002

---

구현

 

LinkedList 는 Swift 를 사용하여 아래와 같이 구현하며, 아래와 같이 사용할 수 있습니다.

// MARK: Deque 구현
class SinglyLinkedListNode<T> {
    var value: T 
    // 노드가 가지고 있는 값
    var next: SinglyLinkedListNode? 
    // 다음 노드의 참조
    
    init(_ value: T) { 
    // 초기화 함수
        self.value = value
        self.next = nil
    }
}

class SinglyLinkedList<T> {
    var head: SinglyLinkedListNode<T>? 
    
    var isEmpty: Bool { 
    // Singly Linked List 가 비어있는지 true/ false 를 반환합니다.
        return head == nil
    }
    
    var first: LinkedListNode<T>? { 
    // Singly Linked List 의 head 를 반환합니다.
        return head
    }
    
    var last: LinkedListNode<T>? { 
    // Singly Linked List 의 마지막 노드를 가리킵니다.
        if var node = head {
            while case let next? = node.next {
                node = next
            }
            return node
        } else {
            return nil
        }
    }
    
    func append(_ value: T) { 
    // Singly Linked List 의 마지막 노드에 데이터를 추가합니다.
        let newNode = SinglyLinkedListNode(value)
        if let lastNode = last {
            lastNode.next = newNode
        } else {
            head = newNode
        }
    }
    
    func node(atIndex index: Int) -> LinkedListNode<T>? { 
    // Singly Linked List 에서 주어진 index 의 노드를 반환합니다.
        if index >= 0 {
            var node = head
            var i = index
            while node != nil {
                if i == 0 { return node }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }
    
    func insert(_ value: T, atIndex index: Int) { 
    // Singly Linked List 의 index 위치에 데이터를 추가합니다.
        let newNode = SinglyLinkedListNode(value)
        if index == 0 {
            newNode.next = head
            head = newNode
        } else if let prevNode = node(atIndex: index-1) {
            newNode.next = prevNode.next
            prevNode.next = newNode
        }
    }
    
    func remove(atIndex index: Int) -> T? { 
    // Singly Linked List 의 index 위치의 데이터를 제거하고 반환합니다.
        if index == 0 {
            head = head?.next
            return head?.value
        } else if let prevNode = node(atIndex: index-1), let nodeToRemove = prevNode.next {
            prevNode.next = nodeToRemove.next
            return nodeToRemove.value
        } else {
            return nil
        }
    }
}

var mSLkList = SinglyLinkedList<Int>()

mSLkList.append(10)		// 데이터 추가, 뒤
mSLkList.append(20)		// 데이터 추가, 뒤
mSLkList.insert(30, 1)		// 데이터 추가, 사이
mSLkList.insert(40, 2)		// 데이터 추가, 사이

mSLkList.isEmpty			// 비어있는지 확인
mSLkList.first			// head 확인
mSLkList.last			// 가장 뒤의 값 확인
mSLkList.node(0)			// index 위치 노드 반환

mSLkList.remove(2)		// 데이터 제거, index 위치 [T, T, X, T]
mSLkList.remove(0)		// 데이터 제거, index 위치 [X, T, T]
mSLkList.remove(0)		// 데이터 제거, index 위치 [X, T]
mSLkList.remove(0)		// 데이터 제거, index 위치	[X]

 

Swift 자체에는 지원하지 않으니 Singly Linked List 를 사용하려면 직접 구현해서 쓰셔야 합니다 ^^.

 

P.S

추가적으로 생각나거나 찾은 내용은 날짜를 덧붙여 업데이트 하겠습니다.