Linked List (연결 리스트)란?
링크드 리스트는 위의 그림과 같이 데이터를 순차적으로 저장하지 않고 각각 떨어진 공간에 존재하는 데이터를 연결해 놓은 자료구조를 말한다. 위의 그림의 사각형을 노드(Node)라고 하는데 노드는 자신의 데이터와 다음 노드를 연결하는 포인터로 구성되어 있다.
Array와 Linked List
배열과 링크드 리스트는 서로 장단점이 명확하다. 먼저 배열을 살펴보자.
배열은 index를 사용하여 한 메모리 공간 안에 데이터를 순차적으로 저장한다. 사용자는 인덱스를 이용해서 원하는 위치에 있는 데이터를 바로 접근할 수 있다.
하지만 배열의 중간에 데이터를 삽입하거나 삭제할 경우 기존의 데이터를 이동시키는 작업이 필요하다. 그렇기 때문에 삽입과 삭제에 있어서 오버헤드가 발생할 수 있다.
반면, 링크드 리스트의 경우는 삽입과 삭제에 있어서 배열과 같은 오버헤드가 발생하지 않는다. 위의 그림에서 새로운 데이터를 0 다음에 삽입한다고 하면 0번 노드의 포인터를 새로 삽입되는 노드를 가리키게 하고 새로운 노드의 포인터를 6번 노드를 가리키게 하면 되기 때문에 기존의 데이터를 이동시키는 오버헤드가 발생하지 않는다.
하지만 배열과는 달리 index의 개념이 존재하지 않아 원하는 데이터에 바로 접근할 수 없다. 위의 그림에서 2번 노드를 head라고 하는데 이는 링크드 리스트에서 가장 앞에 있는 노드를 의미한다. 6번 노드에 접근하기 위해서는 head 노드인 2번 노드에서 시작하여 포인터를 따라서 순차적으로 접근해야 한다.
이를 정리하면 다음과 같다.
| 배열 | 링크드 리스트 | |
| 장점 | - 인덱스를 사용하여 원하는 데이터에 바로 접근할 수 있다. |
- 삽입과 삭제가 용이하다. |
| 단점 | - 삽입과 삭제가 오래 걸린다. - 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다. |
- 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 한다. |
| 용도 | 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 | - 삽입과 삭제 연산지 잦고, 검색 빈도가 적을 때 |
Linked List의 기본 구조
Node
먼저, 위의 링크드 리스트 그림에서 사각형에 해당하는 노드를 정의한다. 노드에는 실제 데이터와 다음 노드의 참조값이 저장된다.
class Node<T: Equatable> {
let data: T
var next: Node?
init(data: T, next: Node? = nil) {
self.data = data
self.next = next
}
}
Linked List
struct LinkedList<T: Equatable> {
var head: Node<T>?
func printList() {
var now = head
print("===== Linked List =====")
while now != nil {
now?.next == nil
? print("data : \(String(describing: now?.data))")
: print("data : \(String(describing: now?.data)) -> ")
now = now?.next
}
print("========== End print ==========")
}
}LinkedList 구조체에는 가장 앞에 있는 노드를 나타내는 head 프로퍼티가 존재한다. printList()는 head부터 시작하여 링크드 리스트의 마지막 노드까지 출력해주는 메서드이다.
탐색 ( searchNode(data:) ) - O(N)
func searchNode(data: T) -> Node<T>? {
var now = head
while now?.data != data && now != nil {
now = now?.next
}
return now
}입력으로 받은 data와 같은 데이터를 가진 노드를 찾기 위한 메서드이다. head부터 시작하여 순차적으로 접근하여 노드의 데이터와 data가 일치하는 경우가 있는지를 탐색한다.
위의 코드들을 보면 Node 클래스와 LinkedList 구조체를 제네릭을 사용하여 정의할 때 Equatable 프로토콜을 채택한 자료형만을 사용할 수 있게 하였다. 이는 데이터 탐색을 위해 != 연산자를 사용하여 비교하는데 만약 비교할 수 없는 자료형으로 링크드 리스트를 만들게 된다면 != 연산자를 사용할 수 없기 때문이다.
마지막에 데이터 추가 ( (append(data:) ) - O(1) or O(N)
// 마지막에 데이터 추가
mutating func append(data: T) {
let newNode = Node(data: data)
if head == nil {
head = newNode
return
}
var now = head
while now?.next != nil {
now = now?.next
}
now?.next = newNode
}링크드 리스트의 마지막에 데이터를 삽입하기 위해서는 먼저 head부터 시작하여 마지막 지점까지의 탐색이 진행되어야 한다. 탐색하는 과정은 O(N)의 시간 복잡도를 가지고 삽입하는 연산은 O(1)의 시간 복잡도를 가진다.
만약 링크드 리스트의 head가 없다면(즉, 비어있는 링크드 리스트라면) head에 새로운 데이터 노드를 넣어주면 된다. 그렇지 않다면 head부터 시작하여 다음을 가리키는 next가 nil인 노드를 찾아서 next를 새로운 노드를 가리키게 수정하면 된다.
지정된 위치에 데이터 추가 ( insert(data:at:) ) - O(1) or O(N)
// 지정된 위치에 데이터 추가
mutating func insert(data: T, at idx: Int) {
let newNode = Node(data: data)
if head == nil {
head = newNode
return
} else if idx-2 < 0 {
append(data: data)
return
}
var now = head
for _ in 0...idx-2 {
now = now?.next
}
newNode.next = now?.next
now?.next = newNode
}중간에 새로운 노드를 삽입하는 것은 아래의 그림과 같다.
먼저 10번 노드의 포인터를 0번 노드가 가리키던 6번 노드로 지정한 후, 0번 노드의 포인터를 새로운 10번 노드를 가리키게 하면 된다.
마지막 노드 삭제 ( removeLast() ) - O(1) or O(N)
// 가장 마지막 노드 삭제
mutating func removeLast() {
if head == nil { return }
if head?.next == nil {
head = nil
return
}
var now = head
while now?.next?.next != nil {
now = now?.next
}
now?.next = nil
}마지막 노드의 바로 전에 있는 노드까지 탐색을 진행한다. 그 후 해당 노드의 포인터를 nil로 바꿔주면 마지막 노드는 링크드 리스트에서 제거된다. Node를 클래스로 구현했기 때문에 ARC로 인해 참조가 해제된 마지막 노드는 자동으로 메모리에서 해제된다.
지정한 위치의 노드 삭제 ( delete(at:) ) - O(1) or O(N)
// 지정한 위치의 노드 삭제
mutating func delete(at idx: Int) {
if head == nil { return }
if idx == 0 || head?.next == nil {
head = head?.next
return
}
var now = head
for _ in 0..<idx-1 {
if now?.next?.next == nil { break }
now = now?.next
}
now?.next = now?.next?.next
now?.next?.next = nil
}삭제할 노드의 바로 이전 노드의 next를 삭제할 노드의 next로 바꿔주면 된다. 만약 idx가 링크드 리스트에 저장되어 있는 노드의 수보다 많을 경우에는 가장 마지막 노드가 삭제된다.
전체 코드
import Foundation
class Node<T: Equatable> {
let data: T
var next: Node?
init(data: T, next: Node? = nil) {
self.data = data
self.next = next
}
}
struct LinkedList<T: Equatable> {
var head: Node<T>?
func printList() {
var now = head
print("===== Linked List =====")
while now != nil {
now?.next == nil
? print("data : \(String(describing: now?.data))")
: print("data : \(String(describing: now?.data)) -> ")
now = now?.next
}
print("========== End print ==========")
}
func searchNode(data: T) -> Node<T>? {
var now = head
while now?.data != data && now != nil {
now = now?.next
}
return now
}
// 마지막에 데이터 추가
mutating func append(data: T) {
let newNode = Node(data: data)
if head == nil {
head = newNode
return
}
var now = head
while now?.next != nil {
now = now?.next
}
now?.next = newNode
}
// 지정된 위치에 데이터 추가
mutating func insert(data: T, at idx: Int) {
let newNode = Node(data: data)
if head == nil {
head = newNode
return
} else if idx-2 < 0 {
append(data: data)
return
}
var now = head
for _ in 0...idx-2 {
now = now?.next
}
newNode.next = now?.next
now?.next = newNode
}
// 가장 마지막 노드 삭제
mutating func removeLast() {
if head == nil { return }
if head?.next == nil {
head = nil
return
}
var now = head
while now?.next?.next != nil {
now = now?.next
}
now?.next = nil
}
// 지정한 위치의 노드 삭제
mutating func delete(at idx: Int) {
if head == nil { return }
if idx == 0 || head?.next == nil {
head = head?.next
return
}
var now = head
for _ in 0..<idx-1 {
if now?.next?.next == nil { break }
now = now?.next
}
now?.next = now?.next?.next
now?.next?.next = nil
}
}
References
- https://jeonyeohun.tistory.com/320?category=884320
- https://babbab2.tistory.com/86
- https://hongcoding.tistory.com/74
'CS > Data Structure' 카테고리의 다른 글
| [자료구조] Swift로 구현하는 Queue (큐) (0) | 2022.04.28 |
|---|---|
| [자료구조] Swift로 구현하는 Stack (2) | 2022.04.17 |
댓글