/* 본 게시물은 ' BoostCourse - 자바로 배우는 자료구조 ' 의 내용과 참고자료를 토대로 작성되었습니다. */
/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
참고 자료
[genius-dev] Linked List에 대하여 : https://genius-dev.tistory.com/entry/Kotlin%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC1-%EA%B5%AC%ED%98%84%EA%B3%BC-%ED%95%A8%EA%BB%98
1. Linked List 구조
이번에는 코틀린으로 Linked List를 구현해보자. (LinkedList 에 대한 이론적인 내용은 다음 글(List)을 확인해라.)
class LinkedList<T> {
data class Node<T>(
var data: T?,
var next: Node<T>?
)
private var headNode: Node<T>? = null
// 노드 개수를 세는 변수
private var _currentSize: Int = 0
}연결 리스트의 핵심은 '노드'이다. 노드는 next 라는 포인터(reference) 와 data 를 가진다.
data의 자료형은 T로 형식 매개변수이다. 그리고 next의 타입은 Node이다. 다른 노드를 가르키는 포인터이기 때문이다.
headNode는 리스트의 첫 번째 노드를 가르키는 변수이다.(시작점)
currentSize는 리스트의 크기를 저장하는 변수이다.
노드의 개수를 세는 효율적인 방법
노드의 개수를 직접 세는 방법보다 int 타입인 변수(size)를 만들어 노드의 개수를 세는 방법이 더 효율적이다. 그 이유는 노드의 개수를 직접 셀 경우, 요소가 n개면 n번을 세야 하기 떄문에 시간 복잡도는 O(n)이다. 하지만 크기를 변수로 만들고 리스트에 요소를 추가/삭제 할 때 마다, 변수의 값을 수정하면 리스트의 크기를 바로 알 수 있다. 이 경우 시간 복잡도는 정확히 1이다. 즉, 매번 크기를 구하러 노드를 따라 이동하는 비용보다 변수로 관리해서 구하는 비용이 더 싸다.
2. Linked List 기능
이제 LinkedList의 다양한 메서드를 추가해보자. 우리는 자료구조를 만들 때 고려해야하는 '경계 조건'에 따라 기능들을 구현해보자.
경계 조건
- 자료 구조가 비어있는 경우
- 자료 구조에 단 하나의 요소가 들어있을 때
- 자료 구조의 첫 번째 요소를 제거하거나 추가할 때
- 자료 구조의 마지막 요소를 제거하거나 추가할 때
- 자료 구조의 중간 부분을 처리할 때
추가(삽입)
삽입은 요소(노드)를 어디에 넣을지에 따라 구현 방식이 달라진다. 처음과 끝, 그리고 특정 위치에 삽입하는 경우 총 3가지 경우가 있다. 각각의 경우를 구현해보자.
1. 처음에 삽입
새로운 node를 연결 리스트의 앞 부분에 추가하는 방법은 다음과 같다.
- 새로운 node를 만든다.
- 새로운 node의 next가 현재 head를 가리키도록 한다.
- head 포인터가 새로운 node를 가리키도록 한다.
이 과정을 코드로 구현해보면 다음과 같다.
fun addFirst(data: T){
val newNode = Node(data, headNode)
headNode = newNode
currentSize++
}*데이터를 추가했으므로 currentSize 1 증가
만약 새로 만든 노드가 현재 head 를 가르키기 전에 head 포인터가 새로운 node를 가르킨다면, 기존 node 는 garbage 값이 될 것이다.
2. 끝에 삽입
우선, 임시 포인터를 이용해 새로운 node를 연결 리스트의 뒤 부분에 추가하는 방법을 코드로 구현해보자.
fun addLast(data: T){
val newNode = Node(data, null)
var tmp = headNode
while(tmp?.next != null){
tmp = tmp.next
}
tmp?.next = newNode
currentSize++
}여기서 문제가 발생할 수 있다. 바로 경계 조건 1번에 의해서 만약 headNode 가 null 인 경우 tmp 가 null이라 tmp?.next에서 NPE가 발생할 수 있다. 이 문제를 해결하기 위해서 headNode가 null 인 경우를 처리하는 코드를 작성한다. 코드는 다음과 같다.
fun addLast(data: T){
val newNode = Node(data, null)
//headNode 가 비어있는 경우 즉, 요소가 없는 경우
if (headNode == null){
headNode = newNode
currentSize++
return
}
// tmp 가 null 일 수 없음.
var tmp = headNode
while(tmp?.next != null){
tmp = tmp.next
}
tmp?.next = newNode
currentSize++
}이제, 새로운 노드를 마지막에 추가하는 코드를 완성했다. 이 코드 같은 경우 연결 리스트의 마지막 노드를 찾을 때 리스트의 맨 앞부터 시작해서 마지막 요소까지 살펴보기 떄문에 시간복잡도는 O(n)이다. 이를 개선할 수 있는 방법이 있다. 바로 size와 같은 방법인데, 마지막 노드를 전역 변수로 저장하면 된다. (이 전역 변수를 tail 포인터라 한다. 여기서는 lastNode 라 지칭하겠다.) 마지막 노드(lastNode)의 next 와 마지막 노드(lastNode)에 새로 생성해준 노드를 삽입해준다. 이런 경우 마지막 요소까지 안 가고 바로 마지막 요소에 접근이 가능하기 때문에 시간 복잡도는 O(1) 이 된다. 이를 코드로 구현해보자.
class LinkedList<T> {
...
private var lastNode: Node<T>? = null
fun addLast(data: T){
val newNode = Node(data, null)
//headNode 가 비어있는 경우 즉, 요소가 없는 경우
if (headNode == null){
headNode = newNode
lastNode = newNode
currentSize++
return
}
lastNode?.next = newNode
lastNode = newNode
currentSize++
}
}이렇게 lastNode 라는 전역 변수를 생성한 경우 처음에 값을 넣는 경우도 약간의 코드 수정이 필요하다.
fun addFirst(data: T){
val newNode = Node(data, headNode)
headNode = newNode
if (lastNode == null){ // lastNode가 없을 때 즉, 요소가 아무것도 없을 때
lastNode = headNode
}
currentSize++
}*lastNode == null 대신 headNode == null 로 바꿔도 된다.
lastNode 라는 전역 변수를 고려하여 코드를 작성해야 하지만 코드의 성능은 향상되었다.
3. 특정 위치에 삽입
특정 위치에 삽입하기 위해서는 삽입하는 위치 기준으로 이전/다음 노드가 필요하다. 예를 들어 index가 2인 자리에 추가하고 싶다면 index 1, 2 의 노드가 필요하다. 이전에 있는 노드를 prevNode / 다음에 있는 노드를 nextNode라 하겠다.
먼저, 삽입하는 위치 기준으로 이전/ 다음 노드를 찾는 함수를 구현해보자.
private fun findData(index: Int): Node<T>? {
var currentNode = headNode
repeat(index){
currentNode = currentNode?.next
}
return currentNode
}위 함수를 통해 index - 1 을 파라미터로 주면 이전 노드를 index 를 파라미터로 하면 다음 노드를 얻을 수 있다.
다음으로 특정 위치에 노드를 추가하는 과정은 다음과 같다.
- 새로운 노드의 next에 nextNode를 연결한다.
- prevNode의 next에 새로운 노드를 연결한다.
fun add(data:T, index: Int = currentSize){
//index 범위 체크
if (index > currentSize) throw IndexOutOfBoundsException("out of index")
// 이전/다음 노드 초기화
var prevNode: Node<T>? = null
val nextNode: Node<T>? = findData(index)
// 이전 노드 찾기
if(index != 0){
prevNode = findData(index - 1)
}
//
when {
// 이전 노드가 없으면 -> index = 0
prevNode == null -> addFirst(data)
// 다음 노드가 없으면 -> index = currentSize
nextNode == null -> addLast(data)
// 이전 / 노드 둘 다 있으면 -> 0 < index < currentSize
else -> {
val newNode = Node(data, nextNode)
prevNode.next = newNode
currentSize++
}
}
}add 함수를 통해 특정 위치(처음 , 중간, 끝)에 노드를 추가할 수 있다.
*끝에 삽입하는 것을 default 값으로 설정
삭제
이번에도 추가와 마찬가지로 처음, 끝, 특정위치에 따라 코드를 구현해보자.
1. 처음 값 삭제
fun removeFirst(){
// Empty List
if (headNode == null){
return
}
// headNode == lastNode -> 요소 1개
if (headNode == lastNode){ // or headNode.next == null or currentSize == 1
lastNode = null
headNode = null
}
else {
headNode = headNode?.next
}
currentSize--
}경계조건 1번 / 2번 에 따라 error 가 발생할 수 있으므로 case 에 따라 처리한다.
2. 마지막 값 삭제
fun removeLast(){
//Empty List
if (headNode == null){
return
}
// 요소 1개
if (headNode == lastNode){
return removeFirst()
}
//임시 포인터
var currentNode = headNode
var prevNode: Node<T>? = null
//lastNode 이전 노드 즉 마지막에서 두번째 node
while (currentNode != lastNode){
prevNode = currentNode
currentNode = currentNode.next
}
// currentNode == lastNode
prevNode.next = null
lastNode = prevNode
currentSize--
}3. 특정위치에 값 삭제
fun remove(index: Int){
if (index > currentSize) throw IndexOutOfBoundsException("out of index")
// 이전/다음 노드 초기화
var prevNode: Node<T>? = null
val deleteNode: Node<T>? = findData(index)
// 이전 노드 찾기
if(index != 0){
prevNode = findData(index - 1)
}
//
when {
// 이전 노드가 없으면 -> index = 0
prevNode == null -> removeFirst()
// 다음 노드가 없으면 -> index = currentSize
deleteNode == null -> removeLast()
// 이전 / 노드 둘 다 있으면 -> 0 < index < currentSize
else -> {
prevNode.next = deleteNode.next
deleteNode == null
currentSize--
}
}
}그 외 메서드 구현
1. contains(element: T)
해당 element가 있는지 확인하는 메서드이다.
fun contains(data: Comparable<T>): Boolean{
var currentNode = headNode
while (currentNode != null){
if (data.compareTo(currentNode.data!!) == 0){
return true
}
currentNode = currentNode.next
}
return false
}2. removeElement(element: T)
해당 element를 삭제하는 메서드이다. 해당 element 가 있으면 true 없으면 false 를 반환한다.
fun removeElement(data: Comparable<T>): Boolean{
var currentNode = headNode
var prevNode: Node<T>? = null
while(currentNode != null){
if (data.compareTo(currentNode.data!!) == 0){
prevNode?.next = currentNode.next
currentNode.next = null
currentSize--
return true
}
prevNode = currentNode
currentNode = currentNode.next
}
return false
}3. clear()
리스트를 비우는 메서드이다.
fun clear(){
for (i in 0 until currentSize){
removeFirst()
}
}4. printLinkedList()
LinkedList를 출력해주는 메서드이다.
fun printLinkedList(){
var str = "["
var currentNode = headNode ?: return println("[]")
while (currentNode != lastNode){
str += "${currentNode?.data},"
currentNode = currentNode.next!!
}
str += currentNode.data
println("$str]")
}
Linked List 구현 완료
- 주요 개념 : Node, Comparable
