![[Algorithm] Kotlin LinkedList 개념 및 구현 - 지정한 위치에 node 추가하기, node 제거하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FnU0T9%2FbtraGb5GlDU%2FySvxgY5dHF8EqTkIWbbSt1%2Fimg.png)
목차
LinkedList 개념
LinkedList는 각 Node들이 다음 Node에 연결돼있는 리스트입니다.
LinkedList에는 두 가지가 있습니다.
1. Singly Linked List: 다음 node에 한 방향으로 연결된 리스트입니다.
2. Doubly LinkedList: 다음 node와 연결된 동시에 다음 Node와 그전 Node와도 쌍방향으로 연결된 Node입니다.
LinkedList에 특징으로는 Index값이 없습니다. 즉 자리 값이 없습니다. 이 뜻은 n번째 element를 접근하려 할 때 head자리부터 n번째 자리까지 반복하여 접근해야 합니다.
LinkedList의 구성
LinkedList: LinkedList는 아래와 같이 데이터끼리 연결돼있는 리스트를 의미합니다.
head: Linked list에 가장 앞부분을 head라 부릅니다.
Node: 그리고 아래와 같이 A, B, C, D 각 데이터를 node라 부릅니다.
Pointer: LinkedList의 특징으로는 Pointer(화살표)로 데이터끼리의 연결(link)을 나타냅니다.
위는
코드로 Node를 만들어보겠습니다.
data class Node<T>(var value: T, var next: Node<T>? = null){
override fun toString(): String {
return if(next !=null){
"$value -> ${next.toString()}"
} else {
"$value"
}
}
}Node class에는 2가지 가들어값니다. value값과 next 값입니다. 만약 next가 비어있다면 null로 처리합니다.
이제 만든 Node를 함수로 연결해보겠습니다.
fun main() {
"creating and linking nodes" example{
val node1 = Node(value = 1)
val node2 = Node(value = 2)
val node3 = Node(value = 3)
node1.next = node2
node2.next = node3
println(node1)
}
}
1-> 2-> 3 으로 연결됩니다.
우리가 자주 쓰는 ArrayList와 다른 점은 무엇이고 LinkedList만의 특징은 무엇일까요?
LinkedList 장점
1. ArrayList는 사이즈가 정해져 있습니다.
2. ArrayList에 새로운 element를 넣으려 할 때보다, LinkedList에서 새로운 element를 넣으려 할 때 더 효율적입니다.
- 예를 들면 arrayList a = [1, 2, 4, 5] 있다고 합시다.
- 우리는 2와 4 사이에 3을 넣으려 하려면 3이 들어갈 공간을 만들고 3 뒤에 숫자들을 다 옮겨야 합니다.
LinkedList 단점
1. ArrayList처럼 Random access가 불가능합니다. 특정 element를 접근할 때 처음 노드부터 접근해야 합니다.
2. Linked List안에 element들은 다음에 들어올 element를 가리킬 pointer를 위한 빈 메모리를 요구합니다. pointer에 역할은 위에 이미지처럼 A 다음 B element가 온다고 pointer가 알려주게 됩니다.
LinkedList 만들기
예시로 LinkedList class가 만들어지는 과정을 확인해보겠습니다.
internal class LinkedList {
1.
var head : Node? = null // LinkedList의 head입니다.
internal class Node
(var data: Int) {
var next: Node? = null
}
2.
companion object {
/*LinkedList를 만들어보겠습니다.*/
@JvmStatic
fun main(args: Array<String>) {
/* 빈 LinkedList를 먼저 만들어주겠습니다. */
val llist = LinkedList()
//head를 1로 해주고
llist.head = Node(1)
//Node들을 val에 넣어주었습니다.
val second = Node(2)
val third = Node(3)
/* 이제 각 linkedList들의 node를 연결해보겠습니다.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | null | | 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.head!!.next =
second // 첫번쨰 node를 2번쨰 node와 연결
/* 위와코드와같이 llist.head의 다음을 second 노드로 설정해주면 아래와같이 연결됩니다.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
second.next =
third // 두번째 노드를 3번째 노드와 연결
/* second는 third와 연결해주겠습니다.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | o-------->| 3 | null |
+----+------+ +----+------+ +----+------+ */
}
}
}
1. LinkedList에는 기본적으로 head와 next가 들어가야 합니다. 클래스에서 먼저 head와 next의 틀을 만들어줘야 합니다. 아직은 아무 값도 지정되지 않았기 때문에 아래 코드를 확인해보시면 Head와 next는 null로 처리되어있습니다.
2. companion object안에 main문을 구현해서, 구현했던 LinkedList에 값을 넣어주는 모습입니다.
LinkedList Node 추가하기
새로운 Node를 추가하는 3가지 상황을 다뤄보겠습니다.
3 - 1 맨 앞에 추가하기
3 - 2 정해진 위치에 추가하기
3 - 3 맨뒤에 추가하기
맨 앞에 추가하기(push)
맨 앞에 추가하는 push fun을 LinkedList class안에 구현해 보겠습니다.
맨 앞에 E라는 node를 추가하려면 head node인 A앞에서 A가 E를 향하게 배치한 후, E를 head node로 바꿔주면 됩니다.
fun push(new_data: Int) {
/* 1 & 2: 새로운 Node를 val로 지정해줍니다. */
val new_node = Node(new_data) //위에서 만들었던 Node 클래스를 불러온후 value에 new_data가 들어옵니다.
/* 3. new_node를 에 다음 올 node를 head로 지정해줍니다.*/
new_node.next = head
/* 4. new_node를 head Node로 지정해줍니다. */
head = new_node
}
정해진 위치에 추가하기(insert)
이것 또한 LinkedList class안에 들어가게 됩니다.
fun insertAfter(prev_node: Node, new_data: Int) {
/* 1. node가 빈값인지 확인 */
if (prev_node == null) {
println("The given previous node cannot be null")
return
}
/* 2. Node를 배치해줍니다. &
3. new_node에 node date를 넣어줍니다. */
val new_node = Node(new_data)
/* 4. new_node에 다음Node를 prev_node에 다음Node로 지정 */
new_node.next = prev_node.next
/* 5. prev_node에 다음node는 new_node
prev_node -> new_node-> prev_node.next*/
prev_node.next = new_node
}
위에 다이어그램과 연결해보면 prev_node는 B new_node는 E prev_node.next는 C가 됩니다.
맨뒤에 추가하기(append)
fun append(new_data: Int) {
val new_node = Node(new_data)
/* 4. linkedlist가 null이라면 new_node를 head로 지정합니다. */
if (head == null) {
head = Node(new_data)
return
}
/* 4. new_node의 다음값이 null이되야합니다.
왜냐하면 newNode가 마지막값으로 지정 할것이기때문입니다. */
new_node.next = null
/* 5. last의 시작 값을 head로 합니다. linkedlist가 끝에 다라면 null을 리턴하기때문에
null이 나오기직전 수에 next 값을 last로 해야합니다. */
var last = head
while (last!!.next != null)
last = last.next
/* 6. 현재 마지막 node의 next값을 new_node로 해주면
현재 마지막node -> new_node-> null 순서로 바뀝니다.*/
last.next = new_node
return
}
LinkedList Node 삭제
node를 지울때 3가지 방법이 있습니다.
1. pop: 가장앞에있는 Node지우기
2. RemoveLast: 가장 마지막에 있는 Node 지우기
3. RemoveAfter: 선택한 값 지우기
LinkedList Node 삭제 예제를 위해 새로운 LinkedList를 만들어보겠습니다.
//Node Class입니다.
//Node가만들어지면 Value값과 next값이 디폴트로 지정됩니다.
data class Node<T>(var value T, var next:Node<T>? = null){
override fun toString():String{
return if(next!=null){
"$value -> ${next.toString()}"
} else{
"$value"
}
}
}
//LinkedList 입니다.
class LinkedList<T>{
//Linkedlist가 만들어지면 head tail이 만들어집니다.
private var head: Node<T>? = null
private var tail: Node<T>? = null
private var size = 0
//이번엔 사이즈를 같이 기록하여보겠습니다.
fun isEmpty():Boolean{
return size == 0
}
override fun toString():String{
if(isEmpty()){
return "Empty List"
}else{
return head.toString
}
}
}
가장 앞에 있는 Node지우기(pop)
pop에 해당하는 함수를 만들어보겠습니다.
fun pop():T? {
//empty가 아닐때
if(!isEmpty()) size--
val result = head?.value
//head값을 현재 head에서 head next로 바꿔줌으로써 맨앞에 값을 지웁니다.
//만들어줬던 Linkedlist에서 next를 호출하면 다음 Node가 나옵니다.
head = head?.next
//empty라면 tail은 null이됩니다.
if(isEmpty()) {
tail = null
}
return result
}
linkedlist를 만들어서 pop 함수를 만들어 보겠습니다.
"pop" example{
val list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
println("pop 실행전 리스트: $list")
val poppedValue = list.pop()
println("pop 실행후 리스트: $list")
println("pop 적용된 값: $poppedValue")
}
위와 같은 함수를 실행시키고 println값을 보겠습니다.
--Example of pop --
실행전 리스트: 1 -> 2 -> 3
실행후 리스트: 2 -> 3
pop 적용된값: 1
가장 마지막에 있는 Node 지우기 (RemoveLast)
마지막 Node를 지우는 RemoveLast 함수를 만들어 보겠습니다.
fun removeLast(): T? {
//1
val head = head ?: return null
//2
if(head.next == null) return pop()
//3
size--
//4
var prev = head
var current = head
var next = current.next
while(next != null){
prev = current
current = next
next = current.next
}
//5
prev.next = null
tail = prev
return current.value
}
위에 코멘트한 숫자대로 설명해보겠습니다.
1. head가 null이면 지울 것이 아무것도 없기 때문에 null을 리턴합니다.
2. head.next가 null이면 리스트가 하나의 node만 가지고 있다는 의미입니다. 그러므로 위에서 사용해준 pop function을 사용하는 것과 같습니다. 왜냐하면 가장 앞에 값(즉 head)을 지워주면 같은 결과가 나오기 때문입니다.
3. 1 2단계를 통과하면 우리는 이제 list에 있는 node를 지울 수 있음을 확인할 수 있기 때문에, size 값을 업데이트해줍니다. (하나 지울 것이기 때문에 size -1을 합니다.)
4. 4번은 앞에서부터 current.next값이 null이 될때까지 자리를 뒤로 하나씩 옮겨가며 반복합니다. 그러면 마지막 node에 도착합니다.
5. 마지막 node에 도착하면 마지막 node는 지워져야하기때문에 마지막 node의 전의 node인 prev를 이용해여, prev.next = null로, prev의 다음 값을 null로 만들어줍니다. 마지막으로 tail을 prev로 업데이트해줍니다.
이제 위 함수를 실행해보겠습니다.
"removing the last node" example {
val list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
println("마지막 node 지우기 전 $list")
val removedValue = list.removeLast()
println("마지막 node 지운 후: $list")
println("지운 값: $list")
}
위 코드를 실행한 결과입니다.
특정위치 node 지우기(removeAfter)
마지막으로 다룰 것은 특정 위치에 있는 node를 지우는 방법입니다. 위에서 node를 특정 위치에 추가하는 insert와 비슷합니다. 먼저 지울 node에 직전 위치에 node를 찾고 지울 node와 지워질 node의 연결을 끊어야 합니다.
removeAfter함수를 만들어보겠습니다.
//1
fun removeAfter(node: Node<T>): T? {
val result = node.next?.value
//2
if(node.next == tail) {
tail = node
}
//3
if(node.next != null){
size--
}
//4
node.next = node.next?.next
return result
}
1. 전에 만들었던 함수와 다르게 node값을 인자로 받습니다.
2. 인자로 받은 다음 값이 tail이면, 지워질 값이 tail이기 때문에, 인자로 받은 node가 tail이 되어야 합니다.
3. 위 단계를 통과했다면, 가운데에 있는 node를 지운 다는 걸 알 수 있기 때문에, size 값을 업데이트해줍니다.
4. node의 다음값이 지워지기 때문에 현 node와 node.next를 링크를 끊어주면서, node.next자리에 node.next.next값이 와야 합니다.
위 코드를 실행시켜보겠습니다.
"removing a node after a particular node" example{
val list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
println("특정위치 node지우기 전: $list")
val index = 1
val node = list.nodeAt(index -1)!!
val removedValue = list.removeAfter(node)
println("특정위치 node지운 후")
println("지운 값: $removedValue")
}
결과입니다
--Example of removing a node after a particualr node--
특정위치 node 지우기 전: 1 -> 2 -> 3
특정위치 node 지운 후: 1 -> 3
지운 값 : 2
다음 편에서는 알고리즘 문제로 가장 자주 활용되는 LinkedList 예제 3가지를 다뤄보겠습니다.
[알고리즘] Kotlin LinkedList 활용 예제 - LinkedList 뒤집기, LinkedList 합치기, LinkedList 가운데 값 찾기
목차 이 포스트에서는 LinkedList로 가장 자주 활용되는 3가지 타입에 문제를 다뤄보겠습니다. LinkedList 뒤집기 아래 그림과 같이 LeetCode에 예제를 통해 LinkedList를 뒤집어 보겠습니다. 해설 - Reverse Li
underdog11.tistory.com