소개
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번째 자리에 위치시켰습니다.
이것이 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를 구현하는 구체적인 방법에 대해서 알아보겠습니다.
