Return to Video

LinkedList 4 addFirst()

  • 0:03 - 0:07
    오늘은 연결 리스트에 요소를
    추가하는 작업을 살펴보겠습니다
  • 0:07 - 0:13
    연결 리스트 맨 앞에
    추가하는 경우부터 살펴보죠
  • 0:13 - 0:22
    리스트가 있고, 연결 리스트의
    생성자를 호출할 때
  • 0:22 - 0:25
    가장 먼저 head를
    null로 지정합니다
  • 0:25 - 0:27
    그리고 현재 크기는 0입니다
  • 0:27 - 0:30
    크기는 우선 넘어가도록 하죠
  • 0:30 - 0:34
    증가시킬 것인지 감소시킬 것인지만
    알면 됩니다
  • 0:34 - 0:39
    head는 null로 생성됩니다
  • 0:39 - 0:42
    연결 리스트에
    새로운 요소를 추가할 때
  • 0:42 - 0:46
    노드 클래스 객체를 하나 만들고
  • 0:46 - 0:54
    이 노드 클래스는 next와 data를
    가지고 있습니다
  • 0:54 - 0:57
    그래서 연결 리스트가 비어있으면
  • 0:57 - 1:08
    head를 가지고 와서
  • 1:08 - 1:18
    새로 생성된 노드를 가리키도록
    만들면 됩니다
  • 1:18 - 1:23
    이제 또 다른 노드를 리스트 맨 앞에
    새로 추가하도록 합시다
  • 1:23 - 1:29
    새로운 노드를 만들고
  • 1:29 - 1:36
    여기 next와 data가 있습니다
  • 1:36 - 1:41
    여기서 어떻게 하면 될까요?
  • 1:41 - 1:47
    head를 옮긴 다음에
  • 1:47 - 1:56
    여기를 가리키도록 만들면
  • 1:56 - 2:06
    아무것도 A 노드를
    가리키지 않기 때문에
  • 2:06 - 2:08
    가비지 컬렉션이 일어나게 됩니다
  • 2:08 - 2:12
    더이상 가리켜주는
    것이 없어서 말이죠
  • 2:12 - 2:17
    이런 일이 일어나면 안됩니다
  • 2:17 - 2:25
    리스트에서 원래 head가
    A를 가리키고 있었죠
  • 2:25 - 2:27
    그래서 여기서
    가장 먼저 해야 할 것은
  • 2:27 - 2:36
    새로운 노드의 next도
    A를 가리키게 만드는 것입니다
  • 2:36 - 2:44
    이제 head를 옮길 수 있죠
  • 2:44 - 2:54
    head는 B를 가리키고
    head.next는 A를 가리킵니다
  • 2:54 - 2:56
    노드를 또 추가하려면
  • 2:56 - 3:02
    노드를 생성하고
  • 3:02 - 3:09
    next가 현재 head를
    가리키도록 하고
  • 3:09 - 3:21
    head 포인터가 다시 새로운 노드를
    가리키도록 만들면 됩니다
  • 3:21 - 3:36
    이렇게 맨 앞에 요소를 추가하면서
    이 연결 리스트의 크기를 늘렸습니다
  • 3:36 - 3:39
    만약 리스트에 요소가 세 개 있고
  • 3:39 - 3:42
    네 번째 요소를 추가하고 싶으면
  • 3:42 - 3:45
    몇 개의 요소들을 살펴봐야
  • 3:45 - 3:51
    추가할 위치를 찾을 수 있을까요?
  • 3:51 - 3:54
    3은 아닙니다
  • 3:54 - 3:56
    head는 어디 있는지 알기 때문에
  • 3:56 - 4:00
    맨 앞에 요소를 추가하려면
  • 4:00 - 4:05
    새로운 노드를 여기 만들고
  • 4:05 - 4:07
    포인터를 설정해준 다음에
  • 4:07 - 4:10
    head 포인터를
    이 노드로 옮기면 됩니다
  • 4:10 - 4:15
    새로운 요소를 추가하기 위해
    이 뒷부분을 살펴볼 필요가 없었습니다
  • 4:15 - 4:22
    연결 리스트의 맨 앞에 추가하는
    작업의 시간 복잡도는 어떻게 될까요?
  • 4:22 - 4:24
    정확히 1입니다
  • 4:24 - 4:29
    이제 맨 앞에 추가하기 위한 코드를
    살펴보겠습니다
  • 4:29 - 4:38
    이 메소드는 타입 E의 객체를 받습니다
  • 4:38 - 4:42
    가장 먼저 새로운 노드를 만들어야 합니다
  • 4:42 - 4:45
    다른 작업을 하기 전에
    꼭 만들어야 합니다
  • 4:45 - 4:49
    코드는 이렇게 생겼습니다
  • 4:49 - 4:53
    소문자로 node라고 합시다
  • 4:53 - 5:02
    새로운 노드로 지정합시다
  • 5:02 - 5:04
    객체가 무엇이든 상관 없습니다
  • 5:04 - 5:06
    이 객체를 추가하라고 들어왔기 때문에
  • 5:06 - 5:10
    그대로 Node 클래스로
    넘기면 됩니다
  • 5:10 - 5:13
    Node 클래스는 이 객체를
    data에 저장하고
  • 5:13 - 5:22
    next는 null을 가리키게 합니다
  • 5:22 - 5:24
    여기서 순서는 중요합니다
  • 5:24 - 5:27
    처음에는 새로운 노드를 가지고
  • 5:27 - 5:33
    node.next 가 리스트의
    첫 노드를 가리키도록 합니다
  • 5:33 - 5:40
    여기 head와 이미 만들었던 노드가 있고
  • 5:40 - 5:46
    노드에 data와 next가 들어있습니다
  • 5:46 - 5:49
    이 노드를 찾기 위해
  • 5:49 - 5:53
    head를 이용하면 됩니다
  • 5:53 - 5:56
    head는 항상 리스트의 첫 노드를
    가리키기 때문입니다
  • 5:56 - 6:07
    이것은 새로운 노드입니다
  • 6:07 - 6:11
    이제 node.next는
  • 6:11 - 6:14
    head가 가리키는 노드를
    가리키게 만들면 됩니다
  • 6:14 - 6:18
    head가 가리키는 곳과
    메모리상 같은 위치입니다
  • 6:18 - 6:25
    그래서 node.next에 head를 저장합니다
  • 6:25 - 6:47
    그리고 head 포인터가
    새로운 노드를 가리키도록 하면 됩니다
  • 6:47 - 6:51
    지금까지 타입이 E인 객체들만
    추가하고 있었습니다
  • 6:51 - 6:55
    이 E는 무엇인지 중요하지 않습니다
  • 6:55 - 6:58
    이 E를 Node 클래스에 넣고
  • 6:58 - 7:03
    그 내부 클래스에서 처리를 합니다
  • 7:03 - 7:06
    여기서 또 중요한 부분은
  • 7:06 - 7:10
    이 두 줄의 순서를 꼭 기켜야 합니다
  • 7:10 - 7:12
    그렇지 않으면
  • 7:12 - 7:15
    이 두 줄의 순서를 바꾸게 되면
  • 7:15 - 7:22
    head가 원래 있던 노드를
    가리키고 있었다가
  • 7:22 - 7:26
    새로운 노드를 가리키게 되는데
  • 7:26 - 7:30
    원래 있던 노드를 가리키는 것이
    이제 없기 때문에
  • 7:30 - 7:37
    가비지 컬렉션이 일어나게 됩니다
  • 7:37 - 7:38
    currentSize의 역할은
  • 7:38 - 7:41
    연결 리스트의 크기를 상수 시간으로
    알 수 있도록 합니다
  • 7:41 - 7:46
    대신 새로운 요소를 추가할 때
    이 값을 증가시켜야 하고
  • 7:46 - 7:52
    제거할 때 감소시켜야 합니다
  • 7:52 - 7:54
    저번에 봤던
    다섯 가지 조건들을 기억하시나요?
  • 7:54 - 8:01
    첫 번째 주의해야 할 조건이
    무엇이었죠?
  • 8:01 - 8:07
    비어있는 연결 리스트가 있을 때
  • 8:07 - 8:12
    head 는 null을 가리키죠
  • 8:12 - 8:23
    이렇게 head가 null을
    가리키고 있다는게 중요한가요?
  • 8:23 - 8:30
    새로운 노드를 만들고
  • 8:30 - 8:34
    새로운 노드를 만들 때
  • 8:34 - 8:37
    Node의 생성자에서
  • 8:37 - 8:42
    node.next를 null로 지정합니다
  • 8:42 - 8:49
    그래서 next는 null입니다
  • 8:49 - 8:52
    여기 새로운 노드를 만들고
  • 8:52 - 8:57
    node.next를 head로 지정하고
    head는 null을 가리키기 때문에
  • 8:57 - 9:04
    node.next도 결국 null을
    가리키게 만든것입니다
  • 9:04 - 9:06
    그리고 head가
  • 9:06 - 9:08
    새로운 노드를 가리키도록 만들면서
  • 9:08 - 9:13
    이 관계를 없애기 때문에
    문제는 없습니다
  • 9:13 - 9:23
    연결 리스트의 맨 앞에 추가하는
    작업은 비어있을 때도 상관 없습니다
  • 9:23 - 9:24
    이제 한 개의 요소를 가진
    리스트가 되버렸습니다
  • 9:24 - 9:25
    이 사실이 중요한가요?
  • 9:25 - 9:33
    요소가 한 개일 때
    주의해야 할 점이 있을까요?
  • 9:33 - 9:36
    한 개의 요소를 가진 리스트에
    추가를 할 때
  • 9:36 - 9:40
    새로운 노드를 만들고
  • 9:40 - 9:45
    node.next는 head이고
  • 9:45 - 9:49
    head는 new node가 됩니다
  • 9:49 - 9:59
    그래서 요소가 한 개만 있을 때
    따로 주의 할 점은 없죠
  • 9:59 - 10:02
    이렇게 다섯 가시 조건들을 한 번씩
    살펴봐야 합니다
  • 10:02 - 10:03
    리스트 중간에
    추가하는 경우에 대해서는
  • 10:03 - 10:06
    이 메소드는 맨 앞에만 추가하기 때문에
    고려할 필요가 없죠
  • 10:06 - 10:13
    addFirst 메소드이기 때문에
    리스트의 맨 앞만 살펴보는 것입니다
  • 10:13 - 10:14
    맨 뒤에 추가하는
    경우에 대해서도 마찬가지로
  • 10:14 - 10:16
    앞에만 추가하는 메소드이기 때문에
    주의할 필요가 없습니다
  • 10:16 - 10:21
    이렇게 이 메소드는 다섯 가지 경우에서
    문제가 없다는 것을 확인했습니다
Title:
LinkedList 4 addFirst()
Description:
more » « less
Video Language:
English
Duration:
10:24

Korean subtitles

Revisions

Our website uses cookies for analysis purposes.