Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 2024
- Swift
- 애러처리
- atlasian
- WWDC
- 콜드픽스
- 24
- 쿠키
- persistence
- JSON
- 옆집
- 빗버켓
- xcode
- 데이터장소
- om-4ti
- swiftdata
- decidepolicyfor
- httpcookie
- scenedelegate
- 데이터구조
- wwdc24\
- 연결
- 빝버켓
- BFS
- IOS
- 알고리즘
- navigationaction
- 스위프트
- dfs
- infoplist
Archives
- Today
- Total
내가 iOS 개-발자라니.
옆집 스위프트: 1-4) 데이터 구조 - 연결 리스트(Linked List) 본문
오늘은 스위프트로 연결리스트를 만들어봤다.
4. 연결 리스트(Linked List)
- 연결 리스트에 대하여
- 노드: 연결리스트는 노드로 구성되며 각 노드는 아래에 2가지 구성 요소를 포함한다. 리스트에서 첫번째 노드는 헤드(head)라고 하고, 마지막 노드는 테일(tail)이라고 한다. 테일노드는 nil을 가리켜 리스트의 끝을 나타낸다.
노드의 구성 요소:- 데이터: 노드가 보유하는 값 또는 데이터
- 다음(Next): 리스트에서 다음 노드에 대한 참조 또는 포인터
- 연결 리스트 유형
- 단일 연결 리스트: 각 노드가 리스트의 다음 노드에만 참조 eg. 노드1 → 노드2 → 노드3 → nil
- 이중 연결 리스트: 각 노드는 다음 노드와 이전 노드 모두에 대한 참조 eg. 노드1 ↔ 노드2 ↔ 노드3 → nil
- 원형 연결 리스트: 테일 노드가 헤드를 다시 가리켜 원형구조를 이룸 eg. 노드1 → 노드2 → 노드3 → 노드1
- 연결 리스트의 장단점
- 장점:
- 동적 크기: 연결리스트는 동적으로 늘어나거나 줄어들수있어서 배열보다 유연
- 효율적인 삽입/삭제: 노드를 삽입하거나 삭제하는 것을 상수 시간에 수행할 수 있음(배열에서는 요소를 이동해야 할 수 있음)
- 메모리 효율성: 연결 리스트는 포함된 노드에 대해서만 메모리 할당(배열은 연속된 메모리 블록이 필요)
- 단점:
- 무작위 접근: 요소에 접근하는데 선형시간이 걸리면 시작부터 순회해야함
- 추가 메모리: 다음 노드에 대한 참조를 저장하기위해 추가메모리 필요
- 캐시 지역성 부족: 노드가 메모리 전반에 흩어져 있을 수 있으므로 연결 리스트는 CPU 캐시를 효율적으로 활용 못할 수가 있음
- 장점:
- 노드: 연결리스트는 노드로 구성되며 각 노드는 아래에 2가지 구성 요소를 포함한다. 리스트에서 첫번째 노드는 헤드(head)라고 하고, 마지막 노드는 테일(tail)이라고 한다. 테일노드는 nil을 가리켜 리스트의 끝을 나타낸다.
// 스위프트에서 구현하는 연결 리스트~
class Node<T: Equatable> {
var value: T
var next: Node<T>?
init(value: T) {
self.value = value
}
}
class LinkedList<T: Equatable> {
var head: Node<T>?
// 리스트 끝에 노드 추가
func append(value: T) {
let newNode = Node(value: value)
if head == nil {
head = newNode
return
}
var currentNode = head
while currentNode?.next != nil {
currentNode = currentNode?.next
}
currentNode?.next = newNode
}
// 특정 위치에 노드 삽입
func insert(value: T, at index: Int) {
let newNode = Node(value: value)
// 리스트가 비어있거나 인덱스가 0인 경우
if head == nil || index == 0 {
newNode.next = head
head = newNode
return
}
var currentNode = head
var currentIndex = 0
// 삽입 위치 이전 노드 찾기
while currentNode != nil && currentIndex < index - 1 {
currentNode = currentNode?.next
currentIndex += 1
}
// 인덱스가 리스트 범위 내에 있는지 확인
if currentNode == nil {
print("인덱스가 리스트 범위를 벗어났습니다.")
return
}
// 새 노드를 현재 노드와 다음 노드 사이에 연결
newNode.next = currentNode?.next
currentNode?.next = newNode
}
// 특정 값을 가진 첫 번째 노드 삭제
func delete(value: T) -> Bool {
// 리스트가 비어있는 경우
if head == nil {
return false
}
// 삭제할 노드가 첫 번째 노드인 경우
if head?.value == value {
head = head?.next
return true
}
// 삭제할 노드의 이전 노드 찾기
var currentNode = head
while currentNode?.next != nil && currentNode?.next?.value != value {
currentNode = currentNode?.next
}
// 값을 찾지 못한 경우
if currentNode?.next == nil {
return false
}
// 노드 삭제 (다음 노드를 건너뛰기)
currentNode?.next = currentNode?.next?.next
return true
}
// 인덱스로 노드 삭제
func deleteAt(index: Int) -> Bool {
// 리스트가 비어있는 경우
if head == nil {
return false
}
// 첫 번째 노드를 삭제하는 경우
if index == 0 {
head = head?.next
return true
}
var currentNode = head
var currentIndex = 0
// 삭제할 노드의 이전 노드 찾기
while currentNode != nil && currentIndex < index - 1 {
currentNode = currentNode?.next
currentIndex += 1
}
// 인덱스가 리스트 범위를 벗어난 경우
if currentNode == nil || currentNode?.next == nil {
return false
}
// 노드 삭제
currentNode?.next = currentNode?.next?.next
return true
}
// 값 검색 (있으면 true, 없으면 false 반환)
func search(value: T) -> Bool {
var currentNode = head
while currentNode != nil {
if currentNode!.value == value {
return true
}
currentNode = currentNode?.next
}
return false
}
// 값의 인덱스 찾기 (없으면 -1 반환)
func indexOf(value: T) -> Int {
var currentNode = head
var index = 0
while currentNode != nil {
if currentNode!.value == value {
return index
}
currentNode = currentNode?.next
index += 1
}
return -1
}
// 모든 노드의 값 출력
func printList() {
var currentNode = head
var values: [T] = []
while currentNode != nil {
values.append(currentNode!.value)
currentNode = currentNode?.next
}
print(values)
}
}
// 사용 예시
// 정수형 연결 리스트 생성
let intList = LinkedList<Int>()
// 1. 노드 추가(append)
intList.append(value: 10)
intList.append(value: 20)
intList.append(value: 30)
print("리스트 초기 상태:")
intList.printList() // 출력: [10, 20, 30]
// 2. 특정 위치에 삽입(insert)
intList.insert(value: 15, at: 1) // 인덱스 1(두 번째 위치)에 15 삽입
print("인덱스 1에 15 삽입 후:")
intList.printList() // 출력: [10, 15, 20, 30]
intList.insert(value: 5, at: 0) // 맨 앞에 삽입
print("맨 앞에 5 삽입 후:")
intList.printList() // 출력: [5, 10, 15, 20, 30]
intList.insert(value: 35, at: 5) // 맨 뒤에 삽입
print("맨 뒤에 35 삽입 후:")
intList.printList() // 출력: [5, 10, 15, 20, 30, 35]
// 범위를 벗어난 인덱스 테스트
intList.insert(value: 40, at: 10) // 출력: "인덱스가 리스트 범위를 벗어났습니다."
// 3. 검색(search)
let found20 = intList.search(value: 20)
print("20이 리스트에 있나요? \\(found20)") // 출력: true
let found25 = intList.search(value: 25)
print("25가 리스트에 있나요? \\(found25)") // 출력: false
// 4. 인덱스 찾기(indexOf)
let indexOf15 = intList.indexOf(value: 15)
print("15의 인덱스: \\(indexOf15)") // 출력: 2
let indexOf40 = intList.indexOf(value: 40)
print("40의 인덱스: \\(indexOf40)") // 출력: -1 (존재하지 않음)
// 5. 값으로 삭제(delete)
let deleted20 = intList.delete(value: 20)
print("20 삭제 성공? \\(deleted20)")
print("20 삭제 후:")
intList.printList() // 출력: [5, 10, 15, 30, 35]
let deleted40 = intList.delete(value: 40)
print("40 삭제 성공? \\(deleted40)") // 출력: false (존재하지 않음)
// 6. 인덱스로 삭제(deleteAt)
let deletedAtZero = intList.deleteAt(index: 0)
print("인덱스 0 삭제 성공? \\(deletedAtZero)")
print("인덱스 0 삭제 후:")
intList.printList() // 출력: [10, 15, 30, 35]
let deletedAt5 = intList.deleteAt(index: 5)
print("인덱스 5 삭제 성공? \\(deletedAt5)") // 출력: false (범위 초과)
// 7. 문자열 연결 리스트 테스트
let stringList = LinkedList<String>()
stringList.append(value: "안녕")
stringList.append(value: "하세요")
stringList.append(value: "스위프트")
print("\\n문자열 리스트:")
stringList.printList() // 출력: ["안녕", "하세요", "스위프트"]
// 문자열 검색
let foundSwift = stringList.search(value: "스위프트")
print("'스위프트'가 리스트에 있나요? \\(foundSwift)") // 출력: true
// 중간 삽입
stringList.insert(value: "반갑습니다", at: 1)
print("'반갑습니다' 삽입 후:")
stringList.printList() // 출력: ["안녕", "반갑습니다", "하세요", "스위프트"]
// 삭제
stringList.delete(value: "하세요")
print("'하세요' 삭제 후:")
stringList.printList() // 출력: ["안녕", "반갑습니다", "스위프트"]
'This is da(大) SWIFT' 카테고리의 다른 글
옆집 스위프트: 1-6) 데이터 구조 - 그래프(Graph) (0) | 2025.03.17 |
---|---|
옆집 스위프트: 1-5) 데이터 구조 - 트리(Tree) (0) | 2025.03.14 |
옆집 스위프트: 1-3) 데이터 구조 - 스택(Stack)과 큐(Queue) (0) | 2025.03.12 |
옆집 스위프트: 1-2) 데이터 구조 - 문자열(String) (0) | 2025.03.11 |
옆집 스위프트: 1-1) 데이터 구조 - 배열(Array) (0) | 2025.03.10 |