🙋♂️ LinkedList란?
Linked List란 말 그대로 연결된 리스트를 의미한다.
리스트는 각 Node로 구성되어있으며, Node에는 데이터를 저장하는 필드와 다음 노드를 가리키는 Pointer로 구성되어 있다. 이러한 구조를 가진 자료구조를 Linked List라고 한다.
Linked List에는 가장 처음을 가리키는 Head와 가장 마지막 노드를 가리키는 Tail 포인터를 가지고 있다.
🤷♂️ Array List와 Linked List의 차이점
ArrayList
index기반의 자료구조로index를 통해서 요소에 접근이 가능하여 검색 속도가 빠르다.
(O(1)의 시간 복잡도를 가진다.)하지만 삽입, 삭제시 내부적으로 배열을 복사하는 방식이기 때문에 느리다.
(O(N)의 시간 복잡도를 가진다.)내부 구조가 배열로 이루어져있어 포인터가 필요없다.(연속된 메모리안에 저장)
Linked List
검색할Node를 찾기 위해서는 순차적으로 탐색해야 하기 때문에 느리다.
(O(N)의 시간 복잡도를 가진다.)삽입, 삭제시 이전
Node와 다음Node를 참조하는 상태만 변경하면 되기 때문에 빠르다.
(O(1)의 시간 복잡도를 가진다.)
ArrayList와 LinkedList는 서로 다른 장점을 가지고 있다.
이러한 특징을 살려 어떠한 자료구조를 선택할 것인지 결정하면 된다.
👌LinkedList 내부적으로 알아보기
먼저 아래와 같이 LinkedList를 구현한 Class를 만들자
public class LinkedList {
// LinkedList의 head, tail 포인터
private Node head;
private Node tail;
// LinkedList 생성자
public LinkedList(int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
}
class Node { <- inner class로 선언했지만 따로 분리하고 싶다면 분리해도 좋다.
int value;
Node next;
// 생성자
Node(int value) {
this.value = value;
}
}
}위와 같이 LinkedList를 생성할 수 있도록 필수적인 요소들을 선언하였다.
이렇게 하면 LinkedList의 자료구조를 생성자를 통해 생성할 수 있다.
하지만 현재 head, tail이 어떤 Node인지 알 수 없기 때문에 이 포인터들을 반환하는 메서드를 만들어서 편의성을 높여보자.
... LinkedList 구현부...
public Node getHead() {
return head;
}
public Node getTail() {
return tail;
}이제 생성자를 통해서 만들어진 LinkedList의 head, tail의 Node가 무엇인지 알 수 있게 되었다. 이제 아래에서는 LinkedList를 가지고 풀어본 문제 몇가지를 정리하려고 한다.
👓LinkedList의 중간 노드 찾기
아까 위에서 ArrayList와 LinkedList의 차이점을 설명할 때, LinkedList는 원하는 Node를 찾기 위해서 순차적으로 접근해야 한다고 말했다.
그럼 중간 Node를 찾기 위해서는 어떻게 해야할까?
물론 중간 Node를 찾기 위해서는 LinkedList를 순차적으로 탐색을 하여야한다.
나의 경우는 LinkedList의 길이가 짝수인지 홀수인지 먼저 확인 하고 짝수인 경우에는 중간 Node중 두 번째를 반환하였다.
구현한 코드는 아래와 같이 구현하였다.
public Node findMiddleNode() {
// 현재 LinkedList가 비어있는지 확인을 먼저 하자
if(head == null || tail == null) {
return null;
}
int length = 0; <- LinkedList의 길이를 담아주자
Node tempNode = head;
while(tempNode != null) {
length++;
tempNode = tempNode.next; <-- 임시 포인터를 하나씩 이동 시켜주자
}
boolean flag = length % 2 == 0 ? true : false; <- 길이를 2로 나누어 나머지가 0이면 짝수 아니면 홀수다.
Node pre = head;
Node temp = head;
if(flag) { <-- 짝수일때 처리
for(int i = 0; i < length / 2; i++) { <-- 중간 노드까지 temp 포인터를 이동
temp = temp.next;
pre = temp;
}
} else {
for(int i = 0; i < length / 2 + 1; i++) {
temp = temp.next;
pre = temp;
}
}
return temp;
}여기서 조금 햇갈리는 부분이 있을 수 있는데 왜 짝수일때 반복문의 반복 횟수가
length / 2인지 모를 수 있다. 처음 length를 구할때 1이 아닌 0으로 시작 했기 때문인데 구현해보고 나니 이것저것 고칠게 많아 보이긴 한다.
🔗LinkedList에 Loop가 있는지 확인
LinkedList에 루프가 존재하는지 확인하는 문제다.
루프가 존재한다고 하는 의미는 LinkedList의 tail 포인터가 null이 아닌 다른 Node를 가리키고 있다는 것이다.
이 문제를 풀기 위해서는 두개의 임시 포인터가 필요하다.
두 임시 포인터인 Node가 반복하며 순차적으로 이동하면서 한개의 포인터는 1개씩, 다른 한개의 포인터는 2개씩 이동하면서 두개의 포인터가 같을때 루프가 있다고 판단할 수 있다.
루프를 확인하는 코드는 아래와 같이 구현했다.
public boolean hasLoop() {
// 임시 포인터
Node slow = head; <-- 1단계씩 이동
Node fast = head; <-- 2단계씩 이동
while(fast != null && fast.next != null) { <-- fast가 null이거나 fast.next가 null이면 루프가 없는거다.
// 포인터 이동
slow = slow.next;
fast = fast.next.next;
// 두 포인터가 같으면 루프가 존재함
if(slow == fast) {
return true;
}
}
return false; <-- 존재하지 않으면
}🔬LinkedList의 끝에서 K번째 노드 찾기
LinkedList의 끝에서 k번째의 Node를 반환하는 메서드를 구현하였다.
만약 LinkedList에 k개 미만의 노드가 있는 경우는 null을 반환하였다.
public Node findKthFromEnd(int k) {
// 리스트가 비어있는지 확인
if(head == null) {
return null;
}
Node fast = head;
Node slow = head;
// fast 포인터를 k번 만큼 이동시킴
for(int i = 0; i < k; i++) {
if(fast == null) { // fast가 null이면 k가 리스트 범위 초과
return null;
}
fast = fast.next;
}
while(fast != null) { // fast를 리스트 끝까지 이동
fast = fast.next;
slow = slow.next; // slow가 결국 끝에서 k번째 도달한다.
}
return slow; // 그대로 slow 반환
}🪚목록 분할하기
매개 변수x를 기준으로 리스트를 분할해야하는 문제다.
만약 LinkedList가 3 -> 8 -> 5 -> 10 -> 2 -> 1 일때 매개변수 x가 5라면
5보다 작은 값: 3, 2, 1
5보다 크거나 같은 값: 8, 5, 10
결과로는 3 -> 2 -> 1 -> 8 -> 5 -> 10 과 같이 리스트를 수정해야한다.
만약 리스트가 비어있을 경우에는 리스트에는 아무런 수정이 없어야한다.
구현한 코드는 아래와 같이 구현하였다.
public void partitionList(int x) {
// 리스트가 비어있는지 확인
if(head == null || length == 0) {
return;
}
// 더미 노드 생성
Node dummy1 = new Node(0);
Node dummy2 = new Node(0);
// 포인터용 노드 생성
Node prev1 = dummy1;
Node prev2 = dummy2;
Node current = head;
while(current != null) { // 리스트 끝까지 탐색
if(current.value < x) { <-- current의 값이 x보다 작은 경우 처리
prev1.next = current;
prev1 = prev1.next;
} else { <-- current의 값이 x보다 큰 경우 처리
prev2.next = current;
prev2 = prev2.next;
}
current = current.next; <-- current 포인터를 다음 노드로 이동
}
prev2.next = null; // tail 부분이 됨 (루프 방지)
prev1.next = dummy2.next; // 첫째 목록과 둘째 목록 연결
head = dummy1.next; // 정렬된 노드의 head로 재 설정
}🔦LinkedList내 중복 제거
일부 값이 중복된 LinkedList에서 모든 중복된 값을 제거하는 문제다.
문제를 보고 중복된 value를 가지지 않는 자료구조인 Set을 이용하면 되겠다고 생각했다.
문제를 풀고보니 Set을 이용하지 않고 중첩 반복문을 이용해 푸는 방법도 있지만
Set을 이용하는 것이 가독성 면에서 더 좋고 깔끔한 것 같다.
public void removeDuplicate() {
// 리스트가 비어있는지 확인
if(head == null) {
return;
}
Set<Integer> seen = new HashSet<>();
// 포인터 노드 생성
Node current = head;
Node prev = null;
while(current != null) { <-- 리스트 끝까지 탐색
// Set에 저장된 값과 current.value를 비교해서 값이 중복되면 set에 저장하지 않음
if(seen.contains(current.value)) {
prev.next = current.next; <-- 중복된 값 제거(링크를 없앰)
} else { // 중복되는 값이 아니면
seen.add(current.value); <-- set에 저장
prev.next = current; <-- prev 노드를 1단계 이동
}
current = current.next;
}
}⛓️2진수에서 10진수로 변환
각 Node에 2진수를 가진 LinkedList가 존재하는데 이 값들을 10진수로 변환 하여, int형으로 반환하는 문제다.
2진수를 10진수로 변환하기 위해선 2에 특정 거듭 제곱을 하면 10진수로 변환할 수 있다.
자바에서는 Math.pow를 사용해서 거듭 제곱을 쉽게 할 수 있다.
먼저 Math.pow의 사용법을 알아보자면 아래와 같다.
// Math.pow(밑, 지수) = 밑^지수
double result = Math.pow(2, 10);
result------
1024하지만 문제에서는 특정 거듭제곱에 대한 설명이 나와있는데 그 설명은 아래와 같다.
- 가장 오른쪽 숫자는 2^0으로 곱해진다.
- 왼쪽 다음 숫자는 2^1로 곱해진다.
- 그 다음 숫자는 2^2로 곱해진다.
이 점을 유념하고 문제를 풀어야한다. 구현한 코드는 아래와 같다.
public int binaryToDecimal() {
// 리스트가 비어있는지 확인
if(head == null || length == 0) {
return 0;
}
// 포인터용 노드와 10진수로 변환한 값을 담을 변수 선언
Node current = head;
int deciamlValue = 0;
for(int i = 0; i < length; i++) { <-- 리스트를 끝까지 탐색
// 길이가 3이라고 했을때 첫 반복시 3 - 1 - 0 = 2이다.
// 그럼 첫 노드에 2^2 로 연산된다.
// 그 다음 반복인 경우는 3 - 1 - 1 = 1 이므로
// 그 다음 노드에는 2^1 로 연산이 된다.
decimal += current.value * Math.pow(2, length - 1 - i);
current = current.next; // 포인터를 이동
}
return decimal; <-- 10진수로 변환된 값을 반환
}⚙️구간을 역순으로 변경
LinkedList의 특정 구간을 역순으로 변경하는 문제이다.
LinkedList의 특성상 index가 존재하지 않기 때문에 골치아팠던 문제다.
매개변수로 들어온 시작구간, 끝구간을 받아 LinkedList를 순회하면서 역순으로 수정하였다.
역순으로 변경하는것은 크게 어렵지 않았으나, 포인터를 가지고 어떻게 구간을 정할까 그게 문제였다.
먼저 구현한 코드는 아래와 같다.
public void reverseBetween(int start, int end) {
// 리스트가 비어있는지 확인
if(head == null || length == 0) {
return;
}
// 더미 노드를 만들고 첫번째 노드에는 0 그 다음 노드에는 head를 넣음.
Node dummy = new Node(0);
dummy.next = head;
Node prev = dummy;
// prev를 start 위치까지 이동시킴(반복이 끝나면 prev는 start 바로 이전을 가리킴)
for(int i = 0; i < start; i++) {
if(prev == null) { <-- prev가 null이라는 소리는 start가 리스트 범위를 넘어감
return;
}
prev = prev.next; <-- prev 포인터 이동
}
Node startNode = prev.next; <-- prev가 start바로 이전이니 startNode를 구할 수 있음
Node then = startNode.next; <-- 역순 변환 과정에서 이동할 노드를 가지고 있자.
// end - start 만큼만 반복해야 그 구간만큼만 반복됨
for(int i = 0; i < end - start; i++) {
// 역순으로 바꿈
startNode.next = then.next;
then.next = prev.next;
prev.next = then;
then = startNode.next;
}
head = dummy.next; <-- head를 재설정 해줌
}😕 마무리...
결론
LinkedList는 단순히 값과 다음 노드를 가리키는 포인터를 가진 자료구조인것이 전부라고 생각했는데 이를 탐색하고 원하는 값을 가져오기 위해서는 포인터를 잘 활용할줄 알아야한다고 생각한다. 물론 자바에서는 편리하게 제공해주고 있지만 자료구조에 대해서 더 알고자 한다면 직접 구현해보는 것도 나쁘지 않아 보인다.
