Data Structure (자료구조)

비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

Data Structure (자료구조) 비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

Linked list

소개

Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미합니다. 그래서 이름도 linked list입니다. 그렇게 보면 linked list에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것이라고 할 수 있습니다. 또 연결이 아닌 것은 무엇인가를 생각해보는 것도 의미가 있겠죠.

메모리

연결에 대해서 알아보기에 앞서 컴퓨터가 동작하는 원리에 대해서 조금 살펴보겠습니다. 컴퓨터에는 3가지 중요한 부품이 있습니다. CPU와 메모리(memory) 그리고 스토리지(storage)입니다.

메모리는 아래와 같이 생겼습니다. 보통 RAM이라고 부릅니다.

스토리지는 아래와 같은 것들이 있습니다. HDD와 SSD 입니다.

메모리는 속도가 매우 빠릅니다. 반대로 용량이 작습니다. 그리고 전기를 끄면 데이터가 사라지는 속성을 가지고 있습니다. 반면에 스토리지는 속도가 느립니다. 하지만 용량이 훨씬 크고 전기를 꺼도 데이터가 남아 있습니다. 

이런 이유로 데이터는 기본적으로 스토리지에 저장됩니다. 하지만 스토리지는 매우 느리기 때문에 CPU와 함께 일을 하기에는 속도면에서 부족합니다. 그래서 어떤 프로그램을 실행하면 그 프로그램과 데이터는 메모리로 옮겨집니다. CPU는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 됩니다.

이걸 그림으로 표시하면 아래와 같습니다.

그러므로 실행속도를 결정하는 것은 대체로 메모리입니다. 우리가 데이터 스트럭쳐를 배우는 이유는 메모리의 효율적인 사용이라고 할 수 있습니다.

메모리의 구조

메모리의 구조를 자세히 살펴보는 것은 컴퓨터 구조(computer architecture)라는 학문의 소관입니다. 여기서 이것에 대해서 깊게 이야기하는 것은 의미가 없을 뿐 아니라 해롭습니다. 그래서 우리는 비유를 통해서 메모리에 대해서 감을 잡아봅시다. 메모리는 건물에 비유할 수 있을 것 같습니다. 아래 그림은 배열을 사용하는 것과 linked list를 사용하는 것을 비유해서 보여주고 있습니다. 여러분의 회사가 한 건물의 일부를 임대해서 사용한다고 생각해주세요.

Array List

첫번째 회사는 모든 직원이 한곳에 모여있어야 한다는 철학이 있기 때문에 사무실이 모여있습니다. 배열은 건물을 이런 식으로 사용하는 것과 비슷합니다. 만약 회사가 성장해서 사무실이 좁아지면 더 이상 새로운 직원을 뽑을 수 없습니다. 붙어있는 공간이 없기 때문이죠. 만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아서 전체가 이사해야 합니다.

Linked List

linked list는 한 건물 내에서 한 회사가 임대한 사무실이 서로 떨어져 있습니다. 덕분에 직원이 늘어도 큰 걱정이 없습니다. 건물에서 비어있는 곳 아무데나 임대해서 들어가면 되니까요. 그런데 방문자가 사무실을 찾는 방법이 좀 비효율적입니다. 위의 그림에 있는 방문자가 3번째 사무실을 찾아가려면 우선 첫 번째 화살표의 사무실을 찾아가야 합니다. 이 사무실의 직원에게 다음 사무실이 어딘지 물어봅니다. 그럼 알려주는 사무실로 이동 한 후에 다시 물어봐서 그다음 사무실로 이동합니다.

이렇게 물어물어 사무실을 찾아가야 하는 방식이 linked list입니다. 그래서 linked list에서는 몇 번째 엘리먼트를 찾는 것이 느립니다.

반면에 array list는 엘리먼트가 같은 곳에 모여있습니다. 만약에 3번째 자리로 가고 싶다면 한번에 3번째 방으로 갈 수 있습니다. 찾고자 하는 사무실이 몇 번째에 있는지 알고 있다면 ArrayList는 매우 빠릅니다.

연결

linked list의 이름에 왜 연결을 의미하는 링크가 사용되었는지 짐작할 수 있겠지요? 배열과는 다르게 linked list는 그 위치가 흩어져 있기 때문에 서로 연결되어 있어야 합니다. 바로 그런 점에서 연결이라는 이름을 갖게 된 것입니다. linked list는 다양한 데이터 스트럭쳐에서 광범위하게 사용되는 개념이기 때문에 잘 이해하셔야 합니다. 아직은 개념이 모호하겠지만 연결에 대한 개념은 수업이 심화될수록 점점 더 분명해질 것입니다.

용어를 정리해봅시다. array list에서는 엘리먼트라는 이름을 사용했지만 linked list와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부릅니다. 이런 용어들은 연결성이 강조된 표현이라고 생각하시면 됩니다. 여기서도 엘리먼트, 노드, 버텍스를 혼용해서 사용하도록 하겠습니다.

구조

그럼 linked list의 구조를 알아봅시다. 리스트는 노드(엘리먼트)들의 모임입니다. 따라서 내부적으로 노드를 가지고 있어야 합니다. array list의 경우 엘리먼트가 배열의 엘리먼트였습니다. linked list는 배열 대신에 다른 구조를 사용합니다.

노드는 최소한 두 가지 정보를 알고 있어야 합니다. 노드의 값과 다음 노드입니다. 각각의 노드가 다음 노드를 알고 있기 때문에 하나의 연결된 값의 모임을 만들 수 있는 것입니다. 아래 그림은 linked list의 구조를 보여줍니다.

이것을 구현하는 방법은 여러가지입니다. 만약 사용 언어가 C라면 구조체, 자바와 같은 객체지향 언어라면 객체에 데이터 필드와 링크 필드를 만듭니다. 보통 데이터 필드는 value라는 이름의 변수, 링크 필드는 next 변수를 사용합니다. value에는 노드의 값이 저장되고, next에는 다음 노드의 포인터나 참조값을 저장해서 노드와 노드를 연결시키는 방법을 사용합니다.

Head

위의 그림을 보면 head라는 것이 있습니다. 건물의 비유를 다시 사용해보죠. 건물에 들어가려면 출입문을 찾아야 합니다. 리스트를 하나의 건물로 비유하자면 출입문에 해당하는 것이 head입니다. linked list를 사용하기 위해서는 이 head가 가리키는 첫번째 노드를 찾아야 합니다. 취향에 따라서는 first와 같은 이름을 사용하는 경우도 있습니다.

데이터의 추가

시작부분에 추가

노드를 첫 번째 위치에 추가해봅시다.

우선 새로운 노드를 생성합니다.

Vertex temp = new Vertex(input)

새로운 노드의 다음 노드로 첫번째 노드를 가리킵니다.

temp.next = head

새로 만들어진 노드가 첫번째 노드가 되도록 head의 값을 변경합니다.

head = temp

위 작업에 대한 전체코드 입니다.

Vertex temp = new Vertex(input)
temp.next = head
head = temp

중간에 추가

3번째 자리(인덱스 2)에 90을 추가해봅시다.

3번째 자리는 붉은 화살표가 표시된 부분입니다. 즉 6과 23 사이에 90을 위치시키는 것이 우리가 하려는 것입니다. 우선 3번째 자리를 찾아야 합니다.

head를 참조해서 첫번째 노드를 찾았습니다.

Vertex temp1 = head

23의 자리에 새로운 노드를 위치시키기 위해서는 6을 알고 있어야 합니다. 6의 next로 새로운 노드를 지정해야 하기 때문이죠. 아래는 6을 temp1으로 지정하기 위한 반복문입니다.

//현재 k의 값은 2
while (--k!=0)
  temp1 = temp1.next

6의 next를 이용해서 23을 찾아서 temp2로 지정합니다.

Vertex temp2 = temp1.next

값이 90인 새로운 노드를 생성합니다.

Vertex newVertex = new Vertex(input)

6의 다음 노드로 새로운 노드를 지정합니다.

temp1.next = newVertex

새로운 노드의 다음 노드로 23번을 지정합니다.

newVertex.next = temp2

이렇게 해서 90을 3번째 자리에 위치시켰습니다.

위의 그래픽은 알고리즘과 데이터스트럭쳐를 시각화해서 보여주는 서비스인 visualgo.net을 이용했습니다. 본 컨텐츠에서는 visualgo를 폭넓게 사용하기 때문에 이 서비스를 이용해서 공부하시면 큰 도움이 될 것입니다. http://visualgo.net/list.html

이것이 array list와 linked list의 핵심적인 차이점입니다. 배열의 경우는 엘리먼트를 중간에 추가/삭제할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트의 자리 이동이 필요했습니다. 그래서 배열은 추가/삭제가 느립니다. 반대로 linked list의 경우 추가/삭제가 될 엘리먼트의 이전, 이후 노드의 참조값(next)만 변경하면 되기 때문에 속도가 빠릅니다.

아래는 전체코드입니다.

Vertex temp1 = head
while (--k!=0)
  temp1 = temp1.next
Vertex temp2 = temp1.next
Vertex newVertex = new Vertex(input)
temp1.next = newVertex
newVertex.next = temp2

데이터의 제거

데이터를 제거하는 것도 추가하는 것과 비슷합니다. 아래 리스트에서 세번째 노드(인덱스 2)를 제거하는 과정을 알아봅시다.

우선 head를 이용해서 첫번째 노드를 찾습니다.

Vertex cur = head

두번째 노드로 이동합니다.

//k = 2
while (--k!=0)
  cur = cur.next

세번째 노드를 찾았습니다.

Vertex tobedeleted = cur.next

두번째 노드의 next를 23으로 변경합니다. 이제 90을 지워도 됩니다.

cur.next = cur.next.next

90을 삭제해서 메모리에서 제거합니다.

delete tobedeleted

아래는 전체 코드입니다.

Vertex cur = head
while (--k!=0)
  cur = cur.next
Vertex tobedeleted = cur.next
cur.next = cur.next.next
delete tobedeleted

인덱스를 이용한 데이터 조회

인덱스를 이용해서 데이터를 조회할 때 linked list는 head가 가리키는 노드부터 시작해서 순차적으로 노드를 찾아가는 과정을 거쳐야 합니다. 만약 찾고자 하는 엘리먼트가 가장 끝에 있다면 모든 노드를 탐색해야 합니다.

반면에 array를 이용해서 리스트를 구현하면 인덱스를 이용해서 해당 엘리먼트에 바로 접근 할 수 있기 때문에 매우 빠릅니다. 그 이유는 컴퓨터의 내부적인 메커니즘 때문이기 때문에 여기서 설명하지는 않겠습니다.

trade off

트래이드 오프는 어떤 특성이 좋아지면 다른 특성이 나뻐지는 상황을 의미합니다. array list와 linked list는 트레이드 오프의 좋은 사례라고 할 수 있습니다. 우리가 데이터 스트럭쳐를 배우는 이유 중의 하나는 이러한 트레이드 오프를 이해하기 위해서입니다. 장점과 단점의 미묘한 균형을 이해할 수 있어야 올바른 선택을 할 수 있기 때문입니다. 이러한 내용을 종합해서 보여주는 그림은 아래와 같습니다.

이후 수업에서는 linked list를 구현하는 구체적인 방법에 대해서 알아보겠습니다.

댓글

댓글 본문
  1. 코딩이취미다
    장점이 있으면 단점도 존재한다
    어느것이 좋으냐가 아니라, 어떤 상황에서 어떤 자료구조가 합리적인가 가 중요한것
  2. ChristianProgrammer
    감사합니다
  3. 허정인
    최고입니다.....
  4. Jeon Hyunwoo
    이보다 더 적절한 설명은 본적이 없는거같네요
  5. Radix
    글쓴이는 아니지만, 실제 데이터가 연속되어 할당되는게 보장되지 않습니다.
    저 건물그림에서 '떨어져있다'라는것은 우리가 사용하는 데이터 관점에서만 떨어져 있는것이지 건물주인 입장에서는 빈틈없이 다 채워져있습니다.
    이와같이 OS입장에서는 공간을 낭비하는게 아니라 Linked List의 경우는 적재적소에 데이터를 할당하는 것입니다.
    우연히 Linked List 자료형이 연속된 메모리 공간에 존재 할수도 있지만, 다음 실행시에는 이것을 보장하지 못합니다.
    대화보기
    • 바울
      궁금한게 있습니다.
      arrayList와 LinkedList를 회사그림을 통해 설명해주셨는데요,
      arrayList는 모든 element가 다닥다닥 붙어있고, LinkedList는 띄엄띄엄 떨어져있는 것 같이 그림으로 표현해주셨는데요,

      실제 링크드 리스트를 구현할떄는 중간중간에 빈 부분이 필요없는데, 떨어져 있다고 하면 공간이낭비되는 것같이 느껴지는데,

      저렇게 표현하신 것이 n번째 노드를 방문하려면 1번부터 n-1번까지 노드를 방문해야되니까 느리다는 표현을 하기 위해서 하신건지, 아니면 진짜 그림처럼 공간이 낭비되는 건가요?
    • 성공할 프로그래머
      눈물 나올뻔했습니다. 코드 구현한거 진짜 이해가 안됬는데. 영상보고 3분만에 이해했어요 ㅠㅠ 시각자료가 갑인듯요.. 글로보면 도통 모르겠던데
    • pisteuo
      안녕하세요 많이 배우고 갑니다.
      개인 정리용 블로그에 개념정리겸 정리해서 보관하려고 합니다.
      감사합니다 ^^
      http://pisteuo.hol.es/wp/
    • 빛과소금
      k 는 항상 2로 고정인가요? 따로 k 의 값이 특정한 값으로 설정되어 있지 않아보이는데 제가 놓치고 있는 부분이 있나요? 그리고 linked list 로 데이터를 추가/삭제할때 시간이 빠르다고 하셨는데 저렇게 k의 값을 주어서 loop 으로 반복해서 찾아가면 시간이 많이 걸리는것처럼 보여서요... k의 값도 모르는경우에도 그렇고..
    • Buzz
      자바가 포인터를 지원하지 않는다고 하지만, 명시적으로 지원하지 않을뿐 Vertex의 내부에서 링크드 리스트의 노드 위치를 저장하기 위한 방법으로 사용되고 있기는 하군요.
    • 블랙빈디
      질문입니다!
      '중간에 추가하기' 쪽에서
      temp2를 따로 선언해서 (새로운 노드).next 값을 지정해주잖아요?
      그걸 그냥

      (새로운 노드).next = temp.next
      temp.next = (새로운 노드)

      이렇게 temp를 하나만 이용해서 추가해줘도 문제가 없나요?
    버전 관리
    egoing@gmail.com
    현재 버전
    선택 버전
    graphittie 자세히 보기