1
00:00:03,400 --> 00:00:06,788
오늘은 연결 리스트에 요소를
추가하는 작업을 살펴보겠습니다

2
00:00:06,788 --> 00:00:12,557
연결 리스트 맨 앞에
추가하는 경우부터 살펴보죠

3
00:00:12,557 --> 00:00:22,403
리스트가 있고, 연결 리스트의
생성자를 호출할 때

4
00:00:22,403 --> 00:00:25,391
가장 먼저 head를
null로 지정합니다

5
00:00:25,391 --> 00:00:27,263
그리고 현재 크기는 0입니다

6
00:00:27,263 --> 00:00:29,510
크기는 우선 넘어가도록 하죠

7
00:00:29,510 --> 00:00:34,424
증가시킬 것인지 감소시킬 것인지만
알면 됩니다

8
00:00:34,424 --> 00:00:39,309
head는 null로 생성됩니다

9
00:00:39,309 --> 00:00:41,659
연결 리스트에
새로운 요소를 추가할 때

10
00:00:41,659 --> 00:00:46,256
노드 클래스 객체를 하나 만들고

11
00:00:46,256 --> 00:00:54,344
이 노드 클래스는 next와 data를
가지고 있습니다

12
00:00:54,344 --> 00:00:57,359
그래서 연결 리스트가 비어있으면

13
00:00:57,359 --> 00:01:08,184
head를 가지고 와서

14
00:01:08,184 --> 00:01:18,423
새로 생성된 노드를 가리키도록
만들면 됩니다

15
00:01:18,423 --> 00:01:22,506
이제 또 다른 노드를 리스트 맨 앞에
새로 추가하도록 합시다

16
00:01:22,506 --> 00:01:28,872
새로운 노드를 만들고

17
00:01:28,872 --> 00:01:35,506
여기 next와 data가 있습니다

18
00:01:35,506 --> 00:01:40,846
여기서 어떻게 하면 될까요?

19
00:01:40,846 --> 00:01:46,816
head를 옮긴 다음에

20
00:01:46,816 --> 00:01:56,264
여기를 가리키도록 만들면

21
00:01:56,264 --> 00:02:05,624
아무것도 A 노드를
가리키지 않기 때문에

22
00:02:05,624 --> 00:02:08,007
가비지 컬렉션이 일어나게 됩니다

23
00:02:08,007 --> 00:02:11,724
더이상 가리켜주는
것이 없어서 말이죠

24
00:02:11,724 --> 00:02:17,356
이런 일이 일어나면 안됩니다

25
00:02:17,356 --> 00:02:25,076
리스트에서 원래 head가
A를 가리키고 있었죠

26
00:02:25,076 --> 00:02:26,655
그래서 여기서
가장 먼저 해야 할 것은

27
00:02:26,655 --> 00:02:35,608
새로운 노드의 next도
A를 가리키게 만드는 것입니다

28
00:02:35,608 --> 00:02:44,143
이제 head를 옮길 수 있죠

29
00:02:44,143 --> 00:02:53,959
head는 B를 가리키고
head.next는 A를 가리킵니다

30
00:02:53,959 --> 00:02:55,792
노드를 또 추가하려면

31
00:02:55,792 --> 00:03:01,943
노드를 생성하고

32
00:03:01,943 --> 00:03:08,541
next가 현재 head를
가리키도록 하고

33
00:03:08,541 --> 00:03:21,092
head 포인터가 다시 새로운 노드를
가리키도록 만들면 됩니다

34
00:03:21,092 --> 00:03:35,541
이렇게 맨 앞에 요소를 추가하면서
이 연결 리스트의 크기를 늘렸습니다

35
00:03:35,541 --> 00:03:38,641
만약 리스트에 요소가 세 개 있고

36
00:03:38,641 --> 00:03:42,409
네 번째 요소를 추가하고 싶으면

37
00:03:42,409 --> 00:03:44,841
몇 개의 요소들을 살펴봐야

38
00:03:44,841 --> 00:03:50,795
추가할 위치를 찾을 수 있을까요?

39
00:03:50,795 --> 00:03:53,899
3은 아닙니다

40
00:03:53,899 --> 00:03:56,429
head는 어디 있는지 알기 때문에

41
00:03:56,429 --> 00:04:00,063
맨 앞에 요소를 추가하려면

42
00:04:00,063 --> 00:04:05,296
새로운 노드를 여기 만들고

43
00:04:05,296 --> 00:04:07,051
포인터를 설정해준 다음에

44
00:04:07,051 --> 00:04:09,955
head 포인터를
이 노드로 옮기면 됩니다

45
00:04:09,955 --> 00:04:14,772
새로운 요소를 추가하기 위해
이 뒷부분을 살펴볼 필요가 없었습니다

46
00:04:14,772 --> 00:04:21,672
연결 리스트의 맨 앞에 추가하는
작업의 시간 복잡도는 어떻게 될까요?

47
00:04:21,672 --> 00:04:23,889
정확히 1입니다

48
00:04:23,889 --> 00:04:29,104
이제 맨 앞에 추가하기 위한 코드를
살펴보겠습니다

49
00:04:29,104 --> 00:04:38,255
이 메소드는 타입 E의 객체를 받습니다

50
00:04:38,255 --> 00:04:41,517
가장 먼저 새로운 노드를 만들어야 합니다

51
00:04:41,517 --> 00:04:44,572
다른 작업을 하기 전에
꼭 만들어야 합니다

52
00:04:44,572 --> 00:04:49,462
코드는 이렇게 생겼습니다

53
00:04:49,462 --> 00:04:52,538
소문자로 node라고 합시다

54
00:04:52,538 --> 00:05:02,132
새로운 노드로 지정합시다

55
00:05:02,132 --> 00:05:04,115
객체가 무엇이든 상관 없습니다

56
00:05:04,115 --> 00:05:05,982
이 객체를 추가하라고 들어왔기 때문에

57
00:05:05,982 --> 00:05:10,049
그대로 Node 클래스로
넘기면 됩니다

58
00:05:10,049 --> 00:05:13,214
Node 클래스는 이 객체를
data에 저장하고

59
00:05:13,214 --> 00:05:21,931
next는 null을 가리키게 합니다

60
00:05:21,931 --> 00:05:24,198
여기서 순서는 중요합니다

61
00:05:24,198 --> 00:05:27,031
처음에는 새로운 노드를 가지고

62
00:05:27,031 --> 00:05:33,264
node.next 가 리스트의
첫 노드를 가리키도록 합니다

63
00:05:33,264 --> 00:05:39,864
여기 head와 이미 만들었던 노드가 있고

64
00:05:39,864 --> 00:05:46,081
노드에 data와 next가 들어있습니다

65
00:05:46,081 --> 00:05:48,914
이 노드를 찾기 위해

66
00:05:48,914 --> 00:05:53,222
head를 이용하면 됩니다

67
00:05:53,222 --> 00:05:55,947
head는 항상 리스트의 첫 노드를
가리키기 때문입니다

68
00:05:55,947 --> 00:06:06,983
이것은 새로운 노드입니다

69
00:06:06,983 --> 00:06:11,100
이제 node.next는

70
00:06:11,100 --> 00:06:14,477
head가 가리키는 노드를
가리키게 만들면 됩니다

71
00:06:14,477 --> 00:06:18,127
head가 가리키는 곳과
메모리상 같은 위치입니다

72
00:06:18,127 --> 00:06:25,242
그래서 node.next에 head를 저장합니다

73
00:06:25,242 --> 00:06:47,060
그리고 head 포인터가
새로운 노드를 가리키도록 하면 됩니다

74
00:06:47,060 --> 00:06:51,227
지금까지 타입이 E인 객체들만
추가하고 있었습니다

75
00:06:51,227 --> 00:06:55,393
이 E는 무엇인지 중요하지 않습니다

76
00:06:55,393 --> 00:06:57,689
이 E를 Node 클래스에 넣고

77
00:06:57,689 --> 00:07:03,299
그 내부 클래스에서 처리를 합니다

78
00:07:03,299 --> 00:07:06,211
여기서 또 중요한 부분은

79
00:07:06,211 --> 00:07:09,907
이 두 줄의 순서를 꼭 기켜야 합니다

80
00:07:09,907 --> 00:07:11,938
그렇지 않으면

81
00:07:11,938 --> 00:07:14,718
이 두 줄의 순서를 바꾸게 되면

82
00:07:14,718 --> 00:07:21,589
head가 원래 있던 노드를
가리키고 있었다가

83
00:07:21,589 --> 00:07:26,322
새로운 노드를 가리키게 되는데

84
00:07:26,322 --> 00:07:29,723
원래 있던 노드를 가리키는 것이
이제 없기 때문에

85
00:07:29,723 --> 00:07:36,569
가비지 컬렉션이 일어나게 됩니다

86
00:07:36,569 --> 00:07:37,938
currentSize의 역할은

87
00:07:37,938 --> 00:07:41,276
연결 리스트의 크기를 상수 시간으로
알 수 있도록 합니다

88
00:07:41,276 --> 00:07:45,820
대신 새로운 요소를 추가할 때
이 값을 증가시켜야 하고

89
00:07:45,820 --> 00:07:51,566
제거할 때 감소시켜야 합니다

90
00:07:51,566 --> 00:07:54,314
저번에 봤던
다섯 가지 조건들을 기억하시나요?

91
00:07:54,314 --> 00:08:00,951
첫 번째 주의해야 할 조건이
무엇이었죠?

92
00:08:00,951 --> 00:08:07,248
비어있는 연결 리스트가 있을 때

93
00:08:07,248 --> 00:08:11,867
head 는 null을 가리키죠

94
00:08:11,867 --> 00:08:22,776
이렇게 head가 null을
가리키고 있다는게 중요한가요?

95
00:08:22,776 --> 00:08:30,499
새로운 노드를 만들고

96
00:08:30,499 --> 00:08:33,881
새로운 노드를 만들 때

97
00:08:33,881 --> 00:08:36,732
Node의 생성자에서

98
00:08:36,732 --> 00:08:42,316
node.next를 null로 지정합니다

99
00:08:42,316 --> 00:08:48,542
그래서 next는 null입니다

100
00:08:48,542 --> 00:08:52,058
여기 새로운 노드를 만들고

101
00:08:52,058 --> 00:08:56,991
node.next를 head로 지정하고
head는 null을 가리키기 때문에

102
00:08:56,991 --> 00:09:04,110
node.next도 결국 null을
가리키게 만든것입니다

103
00:09:04,110 --> 00:09:05,517
그리고 head가

104
00:09:05,517 --> 00:09:08,234
새로운 노드를 가리키도록 만들면서

105
00:09:08,234 --> 00:09:13,134
이 관계를 없애기 때문에
문제는 없습니다

106
00:09:13,134 --> 00:09:22,550
연결 리스트의 맨 앞에 추가하는
작업은 비어있을 때도 상관 없습니다

107
00:09:22,550 --> 00:09:24,230
이제 한 개의 요소를 가진
리스트가 되버렸습니다

108
00:09:24,230 --> 00:09:25,362
이 사실이 중요한가요?

109
00:09:25,362 --> 00:09:33,082
요소가 한 개일 때
주의해야 할 점이 있을까요?

110
00:09:33,082 --> 00:09:35,748
한 개의 요소를 가진 리스트에
추가를 할 때

111
00:09:35,748 --> 00:09:40,448
새로운 노드를 만들고

112
00:09:40,448 --> 00:09:45,265
node.next는 head이고

113
00:09:45,265 --> 00:09:49,165
head는 new node가 됩니다

114
00:09:49,165 --> 00:09:58,531
그래서 요소가 한 개만 있을 때
따로 주의 할 점은 없죠

115
00:09:58,531 --> 00:10:02,098
이렇게 다섯 가시 조건들을 한 번씩
살펴봐야 합니다

116
00:10:02,098 --> 00:10:03,466
리스트 중간에
추가하는 경우에 대해서는

117
00:10:03,466 --> 00:10:06,152
이 메소드는 맨 앞에만 추가하기 때문에
고려할 필요가 없죠

118
00:10:06,152 --> 00:10:12,604
addFirst 메소드이기 때문에
리스트의 맨 앞만 살펴보는 것입니다

119
00:10:12,604 --> 00:10:14,237
맨 뒤에 추가하는
경우에 대해서도 마찬가지로

120
00:10:14,237 --> 00:10:16,204
앞에만 추가하는 메소드이기 때문에
주의할 필요가 없습니다

121
00:10:16,204 --> 00:10:20,670
이렇게 이 메소드는 다섯 가지 경우에서
문제가 없다는 것을 확인했습니다