출처 : 생활코딩(https://opentutorials.org/module/1335/8821)
MEMORY? RAM?
메모리는 속도가 매우 빠릅니다. 반대로 용량이 작습니다. 그리고 전기를 끄면 데이터가 사라지는 속성을 가지고 있습니다. 반면에 스토리지는 속도가 느립니다. 하지만 용량이 훨씬 크고 전기를 꺼도 데이터가 남아 있습니다.
이런 이유로 데이터는 기본적으로 스토리지에 저장됩니다. 하지만 스토리지는 매우 느리기 때문에 CPU와 함께 일을 하기에는 속도면에서 부족합니다. 그래서 어떤 프로그램을 실행하면 그 프로그램과 데이터는 메모리로 옮겨집니다. CPU는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 됩니다.
그러므로 실행속도를 결정하는 것은 대체로 메모리입니다.
우리가 데이터 스트럭쳐를 배우는 이유는 메모리의 효율적인 사용이라고 할 수 있습니다.
메모리의 구조
메모리의 구조를 자세히 살펴보는 것은 컴퓨터 구조(computer architecture)라는 학문의 소관입니다. 여기서 이것에 대해서 깊게 이야기하는 것은 의미가 없을 뿐 아니라 해롭습니다. 그래서 우리는 비유를 통해서 메모리에 대해서 감을 잡아봅시다. 메모리는 건물에 비유할 수 있을 것 같습니다. 아래 그림은 배열을 사용하는 것과 linked list를 사용하는 것을 비유해서 보여주고 있습니다. 여러분의 회사가 한 건물의 일부를 임대해서 사용한다고 생각해주세요.
찾으려는 메모리의 주소만 알면 빠르게 데이터를 가져올 수 있고,
이 때 주소가 어디인지에 상관없이 데이터를 불러오는 속도는 동일한데 이를 Random Access Memory, RAM 이라고 한다.
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 = temp
새로 만들어진 노드가 첫번째 노드가 되도록 head의 값을 변경합니다.
Vertex temp = new Vertex(input) temp.next = head head = temp
위 작업에 대한 전체코드 입니다.
중간부분에 추가
3번째 자리(인덱스 2)에 90을 추가해봅시다.
3번째 자리는 붉은 화살표가 표시된 부분입니다. 즉 6과 23 사이에 90을 위치시키는 것이 우리가 하려는 것입니다. 우선 3번째 자리를 찾아야 합니다.
Vertex temp1 = head
head를 참조해서 첫번째 노드를 찾았습니다.
while (--k!=0) temp1 = temp1.next
23의 자리에 새로운 노드를 위치시키기 위해서는 6을 알고 있어야 합니다. 6의 next로 새로운 노드를 지정해야 하기 때문이죠. 위는 6을 temp1으로 지정하기 위한 반복문입니다.
Vertex temp2 = temp1.next
6의 next를 이용해서 23을 찾아서 temp2로 지정합니다.
Vertex newVertex = new Vertex(input)
값이 90인 새로운 노드를 생성합니다.
temp1.next = newVertex
6의 다음 노드로 새로운 노드를 지정합니다.
newVertex.next = temp2
새로운 노드의 다음 노드로 23번을 지정합니다.
이렇게 해서 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
개인적으로 자료구조에 대해서 아는 바가 없는 편이었는데 역시 이고잉선생님의 강의를 들으니 많은 도움이 되었다. 공부할게 많다는 게 복이라는 생각이 든다! 오늘의 나는 어제보다 발전했다는 자신감을 갖자
