자료 구조( Data structure)에 대해서 이야기 하기에 앞서 컴퓨터가 동작하는 원리에 대해서 간단하게 살펴보며, 컴퓨터의 3가지 중요한 부품을 알아보겠습니다.
중앙 처리 장치(CPU - Central Processing Unit)
컴퓨터에서 구성 단위 중 기억, 해석, 연산, 제어라는 4대 기능을 종합하는 장치
메모리(memory) - 주 기억장치
사용자가 자유롭게 내용을 읽고 쓰고 지울 수 있는 '기억장치' 컴퓨터가 켜지는 순간부터 CPU는 연산을 하고 동작에 필요한 모든 내용이 전원이 유지되는 내내 이 기억장치에 저장된다.'주기억장치'로 분류되며 보통 램이 많으면 한번에 많은 일을 할 수 있기에 '책상'에 비유되곤 한다.
스토리지(storage)- HDD와 SSD
메모리는 속도가 매우 빠르지만 용량이 작고 전기를 끄면 데이터가 사라지는 속성(휘발성 메모리)을 가지고 있다.
반면 스토리지는 속도가 느리다 하지만 용량이 훨씬 크고 전기를 꺼도 데이터가 남아(비휘발성 메모리) 있는다.
이런 이유로 데이터는 기본적으로 스토리지에 저장이 된다. 하지만 스토리지는 매우 느리기 때문에 cpu와 함께 일을 하기에는 속도면에서 부족하다. 그래서 어떤 프로그램이 실행하면 그 프로그램과 데이터는 메모리로 옮겨진다.
cpu는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 된다.
그림으로 표시하면 아래와 같다.
그러므로 실행속도를 결정하는 것은 대체로 메모리이다.
우리가 데이터 스트럭쳐를 배우는 이유는 메모리의 효율적인 사용이라고 할 수 있다.
링크드 리스트 ( Linked List )
Linked List는 Array LIst와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미 그래서 이름도 Linked List이다. 그렇다면 우리는 linked list에서 가장 중요한 것은 '연결이 무엇인가' 또 '연결이 아닌 것은 무엇인가' 를 생각해 보는 것이 의미가 있겠습니다.
비유를 통해서 메모리에 대해서 이야기 해보겠습니다.
메모리는 건물에 비유할 수 있습니다. 아래 그림은 배열을 사용하는 것과 linked list를 사용하는 것을 비유해서 보여주고 있습니다. - 건물의 일부를 임대해서 사용한다고 생각해보자.
Array List
첫번째 회사는 모든 직원이 한곳에 모여있어야 한다는 철학이 있기 때문에 사무실에 모여있습니다.
배열은 건물을 이런식으로 사용하는 것과 비슷합니다. 만약 회사가 성장해서 사무실이 좁아지면 더이상
새로운 직원을 뽑을 수 없습니다. 붙어있는 공간이 더이상 없기 때문입니다.
만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아서 전체가 이사를 해야하죠.
자바스크립트의 배열이 아닌 전반적인 프로그래밍 언어를 예로 들고 있습니다.
자바스크립트의 배열은 동적으로 늘리고 줄일 수 있지만 다른 언어들은 정적인 공간을 할당해 놓습니다. 이론적으로 배열은 항상 정적인 크기라는 겁니다.
Linked List
Linked List는 한 건물 내에서 한 회사가 임대한 사무실이 서로 떨어져 있습니다.
덕분에 직원이 늘어도 큰 걱정이 없습니다. 건물에서 비어있는 곳 아무대나 임대해서 들어가면 되겠죠.
그런데 방문자가 사무실을 찾는 방법이 비효율적입니다. 위의 그림에 있는 방문자가 3번째 사무실을 찾아가려면 우선 첫 번째 화살표의 사무실을 찾아가야 합니다. 이 사무실의 직원에게 다음 사무실이 어딘지 물어봅니다.
그럼 알려주는 사무실로 이동 한 후에 다시 물어봐서 그 다음 사무실로 이동을 해야합니다.
이렇게 물어물어 사무실을 찾아가야 하는 방식이 linked list 입니다. 그래서 linked list 에서는 몇 번째 엘리먼트를 찾는 것이 느립니다.
반면 array list 는 엘리먼트가 같은 곳에 모여있기 때문에 만약 3번째 자리로 가고 싶다면 한번에 3번째 방으로 갈 수있습니다. 찾고자 하는 사무실이 몇 번째에 있는지 알고 있다면 array list는 매우 빠릅니다.
link 연결
이제 우리는 linked list의 이름에 왜 연결을 의미하는 링크가 사용되었는지 짐작할 수 있습니다.
배열과는 다르게 linked list는 그 위치가 흩어져 있기 때문에 서로 연결되어 있어야 합니다.
이런 점에서 연결이라는 이름을 갖게 된 것입니다.
linked list는 다양한 자료 구조에서 광범위하게 사용되는 개념이기에 잘 이해할 필요가 있습니다.
정리하자면 array list에서는 엘리먼트라는 이름을 사용했지만 linked list와 같이 연결된 엘리먼트들은 ( node, 마디, 교점의 의미 ) 혹은 버텍스( vertex, 정점, 꼭지점의 의미 ) 라고 부릅니다.
이런 용어들은 연결성이 강조된 표현이라고 생각할 수 있습니다.
linked list의 구조
list는 노드(엘리먼트)들의 모임입니다. 따라서 내부적으로 노드를 가지고 있어야 합니다.
array list의 경우 엘리먼트가 배열의 엘리먼트였습니다. linked list는 배열 대신에 다른 구조를 사용합니다.
노드는 최소한 두가지 정보를 알고 있어야 합니다. 노드의 값과 다음 노드입니다. 각각의 다음 노드를 알고 있기 때문에 하나의 연결된 값의 모임을 만들 수 있는 것입니다. - 밑의 그림이 linked list의 구조를 설명합니다.
위의 그림을 보면 head라는 것이 있습니다. 건물의 비유를 다시 사용하자면 건물에 들어가려면 출입문을 찾아야 합니다. 리스트를 하나의 건물로 비유하자면 출입문에 해당하는 것이 head 입니다.
linked list를 사용하기 위해서는 이 head가 가리키는 첫번째 노드를 찾아야 합니다.
head라는 첫번째 노드 값을 알아야 그 뒤부터 계속 연결을 할 수 있습니다.
데이터의 추가
노드를 첫 번째 위치에 추가해겠습니다.
우선 새로운 노드를 만들어 줍니다.
Vertex temp = new Vertex(input)
새로운 노드의 다음 노드로 첫번째 노드를 가르킵니다.
temp.next = head
새로 만들어진 노드가 첫번째 노드가 되도록 head의 값을 변경합니다.
head = temp위 작업에 대한 전체적인 코드입니다.
//맨 앞에 추가
Vertex temp = new Vertex(input)
temp.next = head
head = temp내용이 길어져 다음 블로그에 작성..
