0x04강
Last updated -
2025년 06월 19일
Edit Source
4강에서는 연결리스트가 무엇인지 알아보고 구현하는 시간을 가진다.
생각 정리
- 연결리스트는 N이 크고, 원소들을 돌아다니면서 이동하다가 삭제나 삽입이 필요한 상황에 떠올리기
- iterator는 다음 인덱스를 가리키고 있음 !
- {1, 2, 3} LinkedList가 있다고 하면 인덱스는 0, 1, 2
- iterator는 3을 가리키고 있음. 디버깅 해보면 확인 가능
# 정의와 성질
연결리스트 : 원소들을 저장할 때, 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조
- 배열과는 다르게 원소들이 이곳 저곳에 흩어져있음
- 원소들 사이에 순서가 정해져있어서, 배열과 연결 리스트는 선형 자료구조이다.
- 트리, 그래프, 해시 같은 것이 비선형 자료구조이다.
# 기능과 구현
- 임의의 위치에 있는 원소로 가기 위해, 첫 번째부터 순차적으로 방문해야 함
- k번째 원소를 보기 위해 $O(k)$ 시간이 필요
- 전체에 N개의 원소가 있다고 하면 평균적으로 $\frac{2}{N}$ 시간이 걸릴테니 $O(N)$이라고 생각
- 추가하고 싶은 위치의 주소를 알고 있을 때만 $O(1)$
임의의 위치에 있는 원소를 확인/변경하는게 $O(N)$인 자료구조를 어디에 써먹을까?
- 메모장과 같은 텍스트 에디터
- 커서를 옮기고, 글자를 지우는 것과 같은 연산을 생각해보자
- 커서가 가리키는 위치에 글자를 추가하거나 지우는 명령을 계속 수행해야 함
- 배열 : 임의의 위치에 글자를 추가하는 것이 비효율적
- 연결리스트 : $O(1)$로 처리할 수 있어서 효율적
# 손코딩 문제 (면접)
Q1. 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때, 해당 List의 길이를 효율적으로 구하는 방법
A. 시작점을 따로 저장해뒀다가 동일한 노드가 나올 때까지 계속 다음 노드로 이동, 공간복잡도 O(1), 시간복잡도 O(N)
Q2. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법
A. 공간복잡도 O(1), 시간복잡도 O(A+B)
- 두 시작점 각각에 대해 끝까지 진행시켜 각각의 길이 구하기
- 다시 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시키기
- 두 시작점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진
Q3. 주어진 연결 리스트 안에 사이클이 있는지 판단
A. Floyd’s cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)
- 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발
- 사이클이 있는 경우 반드시 만나게 됨
- 사이클이 없는 경우 만나지 못하고 연결리스트 끝에 도달하게 됨
# BOJ 1406 (sol)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] input = br.readLine().toCharArray();
int commandCount = Integer.parseInt(br.readLine());
LinkedList<Character> linkedList = new LinkedList<>();
for (char alphabet : input) {
linkedList.add(alphabet);
}
ListIterator<Character> listIterator = linkedList.listIterator(linkedList.size());
for (int i = 0; i < commandCount; i++) {
String commandLine = br.readLine();
char commandType = commandLine.charAt(0);
switch (commandType) {
case 'L':
if (listIterator.hasPrevious()) {
listIterator.previous();
}
break;
case 'D':
if (listIterator.hasNext()) {
listIterator.next();
}
break;
case 'B':
if (listIterator.hasPrevious()) {
listIterator.previous();
listIterator.remove();
}
break;
case 'P':
listIterator.add(commandLine.charAt(2));
break;
}
}
StringBuilder sb = new StringBuilder();
for (Character character : linkedList) {
sb.append(character);
}
System.out.println(sb.toString());
}
}
|
# BOJ 5397 (sol)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
while (n-- > 0) {
List<Character> password = new LinkedList<>();
ListIterator<Character> listIterator = password.listIterator();
String input = br.readLine();
for (int i = 0; i < input.length(); i++) {
char current = input.charAt(i);
switch (current) {
case '<':
if (listIterator.hasPrevious()) {
listIterator.previous();
}
break;
case '>':
if (listIterator.hasNext()) {
listIterator.next();
}
break;
case '-':
if (listIterator.hasPrevious()) {
listIterator.previous();
listIterator.remove();
}
break;
default:
listIterator.add(current);
}
}
for (char c : password) {
sb.append(c);
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
|
# BOJ 1158 (sol)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
sb.append("<");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
List<Integer> nums = new LinkedList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
List<Integer> result = new LinkedList<>();
int currentIndex = 0;
while (!nums.isEmpty()) {
currentIndex = (currentIndex + k - 1) % nums.size();
if (nums.size() > 1) {
sb.append(nums.remove(currentIndex));
sb.append(", ");
} else {
sb.append(nums.remove(currentIndex));
}
}
sb.append(">");
System.out.println(sb.toString());
}
}
|