[Data Structure] Singly Linked List (1)

 Linked List. 혹은 연결 리스트라고 불리는 것은 가장 기본적인 자료구조 형태이며, 일반적으로는 데이터를 저장한 단위 메모리가 연결되어 있는 형태를 나타낸다. 이 연결방식에 따라 Singly Linked List와 Doubly Linked List로 나눠지는데, 이번 포스트에서 소개하는 Singly Linked List(단위 연결 리스트)는 리스트를 구성하는 각 요소들이 서로 다음 요소를 가리키는 어떤 정보를 하나씩 가지고 있는 연결리스트를 의미한다. C에서 뭔가를 가리킨다는 것은 보통 그 정보가 담겨있는 주소를 가리키는 것이므로 각 요소가 가지고 있는 정보는 바로 다음 요소를 가리키는 포인터가 될 것이다. 그림으로 표현하면 다음과 같다.

 이게 3개의 요소가 서로 연결된 단일 연결리스트의 예시이며, 각 요소는 그 다음 요소를 가리키는 포인터(Next)와 자기 자신이 담은 정보(Data)를 가지고 있다. 이때 정보의 형태는 다양하다. 간단하게 정수형태를 가질수도 있고, 혹은 character형 배열을 담아 사용자가 입력한 문자열들을 저장할 수도 있다.

 물론 위의 그림은 연결된 세 개의 요소를 간단하게 표현한 것이지만, 몇가지 규칙이 있다. 마냥 요소의 갯수가 무한정일 수는 없고, 뭔가 끝맺음이 필요한데, 이때는 보통 다음을 가리키는 포인터값을 NULL로 처리함으로써 해당 요소가 마지막임을 알려준다. (물론 진짜 NULL을 참조하면 안되므로, 실제 코드상에서는 NULL값에 대한 예외처리가 필요하다.) 또한 어떤 요소가 가장 처음인지를 알려주는 개체가 반드시 필요하다. 보통 위에서 소개한 대로 따라가자면 head node가 필요하다는 것이다.

 사실 Singly Linked List가 가장 기본적으로 만들수 있는 자료구조이기 때문에 C에서 기본적으로 제공되는 Array(배열)과 비교가 된다.

 - 배열은 정해진 크기의 메모리 영역만 할당받는데 비해 연결리스트는 사용자가 원하는 한, 메모리 영역이 충분하면 얼마든지 생성하고 값을 저장할 수 있다. 이말을 다시 표현하자면 다음과 같다. 우선 배열을 선언할 때는 반드시 배열의 크기를 명시해줘야 하기 때문에, 이미 compile time에서 그 크기가 결정난다. 반면, 연결 리스트의 경우에는 malloc을 통해서 사용자가 원하는 만큼 데이터를 할당받고 값을 저장할 수 있다.

 - 메모리 사용 관점에서 보면 배열의 경우는 사용하지 않는 공간이라도 이미 할당받은 영역을 점유하고 있기 때문에 비효율적인데 반해, 연결리스트는 포인터를 통해서 데이터를 가지고 있는 요소에 대해서만 값을 유지하기 때문에 배열에 비해서 조금더 효율적이라고 하겠다. 추가로 필요하지 않는 데이터에 대해서도 delete를 시킬 수 있기 때문에 그 이점은 높다.

 - 데이터를 중간에 넣고 빼는 과정에 있어서도 차이가 있다. 배열의 경우, 데이터 중간에 새로운 데이터를 넣기 위해서는 뭔가 임의의 공간을 지정해서 요소들간의 이동을 시켜야 하지만, 연결리스트의 경우는 앞에서 소개했다시피 다음 요소를 가리키는 포인터가 있기 때문에 배열처럼 데이터를 일일이 옮길 필요 없이 포인터만 수정해서 데이터를 넣고 뺄 수 있다.

 - 지금까지 본것만 가지고 보면 연결리스트가 가지는 장점이 크지만, 데이터에 접근하는 속도로 따지면 배열이 더 좋다. 앞에서 소개한 바와 같이 배열은 정해진 영역을 연속적으로 할당받아 데이터를 저장하기 때문에 해당 데이터의 index값만 알면, 그 영역에 대해서 데이터를 읽고 쓸수 있다. 반면, 연결리스트에는 그런 index라는 개념이 없기 때문에 처음부터 Next가 가리키는 다음 요소의 데이터를 읽어야 해당 데이터가 있는지 없는지 유무를 알 수 있다. 가령 연결리스트의 제일 마지막에 원하는 데이터가 있다고 가정하면 그 연결리스트의 크기만큼 데이터를 찾아야 한다. 이때문에 데이터에 접근하는 속도가 느리다고 볼 수 있다.