2021.07.12 - [자료구조] - [자료구조] 연결 리스트-1
2021.07.12 - [자료구조] - [자료구조] 연결리스트-2 (추가/삭제)- 에 이은 내용
이전 포스팅의 Remove에서 마지막 노드를 삭제하기 위해 head부터 마지막 노드까지 순차적으로 이동했다.
나중에 정리하겠지만, 이렇게 삭제를 하게 될 경우 remove시도 시 데이터의 갯수만큼 시간복잡도가 증가하기 때문에 빅오 표기법으로
O(n)의 시간복잡도를 갖게 되는 최악의 알고리즘이 된다.
이를 피하기 위해서 검색알고리즘을 사용하는데 지금 우리는 알고리즘을 추가하여 시간복잡도를 줄이기 보다, Head와 마찬가지로 Tail이라는 마지막 노드를 가리키는 변수를 추가하여 마지막 노드를 삭제해보려 한다. 이때 양방향 연결리스트에 대해서 함께 배워보면 좋을 내용이라 정리해본다.
양방향 연결리스트
양방향 연결리스트는 연결리스트의 단점을 보안한 연결리스트이다.
연결리스트의 노드가 data와 nextAddress로 이뤄졌다면, 양방향 연결리스트의 노드는 이전 노드의 주소(prevAddress)와 data, nextAddress로 구성된다.
노드의 구성변화에 따라서 Node클래스도 prevAddress 변수를 추가해줬다.
근데 setNextNode라는 메서드를 추가해두고 쓰질 않았네. 주석으로 조져준다.
class Node {
var prevAddress: Node?
var data: Int?
var nextAddress: Node?
init(data: Int) {
self.data = data
}
// func setNextNode(_ next: Node) {
// nextAddress = next
// }
func printData() {
print(data ?? "data is nil")
}
}양방향 연결리스트의 노드를 사용하여 연결리스트를 구현하면 노드간 관계도는 아래와 같이 표현할 수 있다.
1. Append
Tail이 생겼으니 Append메서드도 수정해야 한다.
class LinkedList {
var head: Node?
var tail: Node?
func append(value: Int) {
let newNode = Node(data: value)
if head == nil {
head = newNode
tail = newNode //추가
} else {
newNode.prevAddress = tail
tail?.nextAddress = newNode
tail = newNode
}
}
}-> 새로운 데이터(value)를 받으면 노드를 생성하는것 까지는 이전 연결리스트의 append와 동일하지만
tail이 추가됨으로서 반복문을 통해 가장 마지막 노드를 찾는 과정이 생략되었다.
첫 노드가 추가될 때 head 와 tail에 이미 값이 들어가게되는데, head가 존재하게 된 이후로 추가하는 노드는
tail의 값을 조정하면 쉽게 해결된다.
else 블럭안을 살펴보자.
추가될 노드의 prevAddress 를 tail로 넣어주고있다.
그림 3 처럼 이것은 새롭게 추가된 노드에게 "네 앞 노드는 기존에 있던 tail이야" 라고 말해주는 것이다.
다음 라인인 tail?.nextAddress = newNode 는 기존 tail이었던 노드의 다음 노드가 새롭게 추가된 NewNode라고 알려주는것이다.
(그림 4)
마지막 Tail = newNode는 newNode와 tail이 서로 주소가 잘 연결되었으니 tail의 위치를 끝으로 땡겨주는것!
2. Remove
removeLast 역시 더욱 쉽게 변했다. 반복문으로 마지막 노드까지 찾아간 다음 마지막 노드의 이전 노드의 nextAddress를 없애는...
비효율적인 삭제 방법에서 tail의 이전 노드에게 nextAddress를 삭제 시키는 코드로 수정했다.
func removeLast() {
if head?.nextAddress == nil {
head = nil
tail = nil
} else {
tail = tail?.prevAddress
tail?.nextAddress = nil
}
}
참조가 끊긴 0x04노드는 자연스럽게 ARC에 의해 메모리에서 해제된다.
이로서 양방향 연결리스트의 추가 삭제가 완성되었다.
3. Insert (feat: Index)
지금까지 노드를 추가하고 삭제하는 방법에 대해 공부해봤다. 추가/삭제는 리스트의 맨 마지막index에서 이뤄지는 동작이었는데,
이번에는 원하는 위치에 노드를 삽입하는 하는 방법을 알아보자.
원하는 위치에 삽입 하겠다는것은 -> n번째 index에서 삽입을 하겠다 는 것과 같은 말이다.
그렇다면 index를 매개변수로 받는 메서드가 있어야 한다.
func insert(value: Int, at: Int) {
}이런 모습이면 되겠다. 이제 채워보자.
value는 당연히 노드의 data가 되는 값이고 at이 바로 index다.
func insert(value: Int, at: Int) {
var current = head
var currentIndex = 0
while current?.nextAddress != nil,
currentIndex < at {
current = current?.nextAddress
currentIndex += 1
}
let newNode = Node(data: value)
current?.nextAddress?.prevAddress = newNode
newNode.nextAddress = current?.nextAddress
current?.nextAddress = newNode
newNode.prevAddress = current
}반복문은 해당 Index까지 current를 이동시키는 코드이다.
중요한것은 newNode를 생성한 후 부터! 한 줄 한 줄 그림으로 이해해보자.
at은 3 이라고 가정하고,
0x02 노드 앞에는 0x00, 0x01 노드가 존재한다고 가정한다.
새로운 노드를 생성할때의 모습이다.
at의 값이 3이기에 0x00(0번째 인덱스), 0x01(1번째 인덱스), 0x02(2번째 인덱스)
~ 을 지나서 NewNode를 삽입해줘야 한다.
1. 0x02의 nextAddress는 0x03! , 0x03의 prevAddress를 NewNode 로 바꿔준다.
2. 새로운 노드의 nextAddress를 current.nextAddress로
3. current의 nextAddress를 newNode의 주소로
4. newNode의 prevAddress를 current의 주소로
이렇게 삽입까지 만들었다!
지금까지 연결리스트에서 양방향 연결리스트까지 알아봤다.
이렇게 작성한 코드들은 예외적인 상황에 모두 대응이 가능한것은 아니다.
리스트에 노드가 존재하는지 부터~ at으로 받는 index가 전체 노드의 갯수보다 많은지~ 여러가지 예외상황에 대해서 코드를 더 추가해야만 한다.
이번 리스트 공부의 핵심은 삽입/삭제 등의 동작에서 노드의 링크가 어떻게 변화하는지 개념을 이해하는 것이기 때문에
완벽한 자료구조를 작성하고 싶다면 더 세심하게 코드를 살펴야 할 것이다.
리스트 끄읕
'자료구조' 카테고리의 다른 글
| [자료구조] 큐-2 (원형 큐) (0) | 2021.07.25 |
|---|---|
| [자료구조] 큐-1 (0) | 2021.07.18 |
| [자료구조] 연결리스트-2 (추가/삭제) (0) | 2021.07.12 |
| [자료구조] 연결 리스트-1 (0) | 2021.07.12 |
| [자료구조] 배열 (0) | 2021.07.04 |
