선형 리스트와 연결 리스트의 정의 (Kotlin 으로 연결 리스트 구현)
📌 선형 리스트(ArrayList)
선형 리스트란 배열과 같이 연속되는 기억 장소에 저장되는 리스트를 말한다. 선형 리스트는 논리적인 순서와 기억 장소에 저장되는 물리적 순서가 일치한다.
선형 리스트의 장점
- 간단한 자료구조이다.
- 접근 속도가 빠르다.
- 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.
선형 리스트의 단점
- 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
- 즉 삽입과 삭제를 위해서는 자료의 이동이 필요하기 때문에 번거롭다.
- 또한 배열의 크기보다 데이터의 수가 클 경우 데이터를 저장할 수 없는 경우가 생긴다.
📌 연결 리스트(LinkedList)
연결 리스트는 자료들을 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키면서, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
연결 리스트의 장점
- 노드의 삽입, 삭제 작업이 용이하다.
- 기억공간이 연속적으로 놓여 있지 않아도 지정이 가능하다.
- 트리를 표현할 때 적합하다.
연결 리스트의 단점
- 항목 접근이 오래 걸린다. (첫 항목부터 순차적으로 접근하므로 최악의 경우 시간 복잡도 O(n)이 소모된다.
- 물리적으로 인접한 메모리에 위치해 있지 않다. (선형 리스트에 비해 항목들이 물리적으로 인접해있지 않아 접근 시간 단축과 캐싱에 불리하다.)
- 참조 포인터를 위한 메모리 공간이 낭비된다.
📖 Kotlin 코드로 연결 리스트 구현
LinkedList 클래스는 연결 리스트의 전체적인 로직이 구현된 클래스로 내부 클래스인 Node와 여러 가지 기능 메서드 함수를 포함하고 있다.
LinkedList 클래스
class LinkedList constructor(var videoList: ArrayList<Video>){
inner class Node{
var data: Any? = null // 데이터가 저장될 필드
var next: Node? = null // 다음 노드를 가리키는 필드
}
var head: Node? = null
var tail: Node? = null
var size: Int = 0
// 특정 위치의 노드를 찾아내는 함수
fun find(index: Int): Node? {
var node = head
for (i in 0 until index) {
node = node?.next ?: error("invalid node") // 엘비스 표현법
}
return node
}
// data 를 받아서 그 위치 index 를 찾아내는 함수
fun findIndex(data: Any): Int{
var index = 0
var node = head
for (i in 0 until 13){
if (node?.data == data){
index = i // 찾던 id 값을 찾은 경우의 index
break
} else {
node = node?.next
continue
}
}
return index // index 값 리턴
}
fun addFirst(data: Any){
val newNode = Node().apply {
this.data = data
this.next = head // 새로운 노드의 다음 노드로 헤드를 지정
}
head = newNode // 헤드로 새로운 노드를 지정
if(head?.next == null){
tail = head
}
size++
}
fun addLast(data: Any){
if(size == 0){
addFirst(data) // 리스트에 노드가 없다면 addFirst 메서드 실행
} else {
val newNode = Node().apply{
this.data = data
}
tail?.next = newNode // 마지막 노드의 다음 노드로 생성한 노드 지정
tail = newNode // 마지막 노드 갱신
size++
}
}
fun addAt(index: Int, data: Any){
if(index == 0){
addFirst(data)
} else {
val newNode = Node().apply {
this.data = data
}
val node = find(index)!!
val temp = node.next
newNode.next = temp // 집어 넣을 새로운 노드의 다음 노드에 temp
node.next = newNode // 찾은 index 의 다음 노드에 새로운 노드 집어 넣기
if (newNode.next == null){
tail = newNode
}
size++
}
}
fun removeFirst(): Any {
val node = head
head = node?.next
size--
return node?.data ?: error("invalid data")
}
fun removeAt(index: Int): Any {
if (index == 0){
return removeFirst()
} else {
val temp = find(index - 1)
val deletedNode = temp?.next
temp?.next = temp?.next?.next
val returnData = deletedNode?.data ?: error("invalid data")
if(deletedNode == tail){
tail = temp
}
size--
return returnData
}
}
}
대표로 addFirst, addAt, removeAt에 대해 간략히 설명해 보자면
addFirst 메서드는 Any 타입의 데이터를 매개변수로 받아와 헤드로 새로운 노드를 지정하고 만약 헤드의 다음 노드가 없다면 즉 링크드 리스트에 아무것도 없다면 헤드와 테일을 같게 만들어 준다.
addFirst 메서드
fun addFirst(data: Any){
val newNode = Node().apply {
this.data = data
this.next = head // 새로운 노드의 다음 노드로 헤드를 지정
}
head = newNode // 헤드로 새로운 노드를 지정
if(head?.next == null){
tail = head
}
size++
}
addAt 메서드는 Any 타입의 데이터와 Int 타입의 인덱스를 매개변수로 받아와 집어넣은 새로운 노드의 다음 노드를 temp로 지정하고 찾은 index의 다음 노드에 새로운 노드를 집어넣는 방식으로 구현한다.
addAt 메서드
fun addAt(index: Int, data: Any){
if(index == 0){
addFirst(data)
} else {
val newNode = Node().apply {
this.data = data
}
val node = find(index)!!
val temp = node.next
newNode.next = temp // 집어 넣을 새로운 노드의 다음 노드에 temp
node.next = newNode // 찾은 index 의 다음 노드에 새로운 노드 집어 넣기
if (newNode.next == null){
tail = newNode
}
size++
}
}
removeAt 메서드는 만약 노드가 하나밖에 없다면 구현해 놓은 removeFirtst 함수를 실행시키고 그게 아니라면 index - 1 번째 노드를 temp라고 임시 지정하고 난 뒤 삭제할 노드의 앞 노드를 삭제할 노드의 뒤의 노드와 연결시켜 주어 노드가 삭제되더라도 연결 리스트가 유지되도록 한다.
removeAt 메서드
fun removeAt(index: Int): Any {
if (index == 0){
return removeFirst()
} else {
val temp = find(index - 1) // k-1 번째 노드를 temp 의 값으로 지정한다.
val deletedNode = temp?.next
temp?.next = temp?.next?.next // 삭제할 노드의 앞의 노드를 삭제할 노드의 뒤의 노드와 연결시켜 준다.
val returnData = deletedNode?.data ?: error("invalid data")
if(deletedNode == tail){
tail = temp
}
size--
return returnData
}
}
Reference:
https://coding-factory.tistory.com/228
https://bluejake.tistory.com/44
https://2dubbing.tistory.com/53
https://supermemi.tistory.com/67