C언어 자료구조 List(1) - 리스트(List)란 무엇인가?

오늘은 자료구조 중에서 선형구조 중 하나인 리스트에 대해서 알아보겠습니다. 실제로 저희는 생활하면서 목록을 자주 만듭니다. 오늘 해야 할 일, 마트에서 장 봐야 할 목록, 반에서 학생 리스트, 성적 리스트 등 목록을 만들 일은 정말 많습니다. 이런 자료 형태를 리스트라고 하는데 자료들을 어떻게 리스트 형태로 만드는지에 대해서 배워보겠습니다.

리스트를 c언어로 구현하는 방법에는 두 가지가 있습니다. 첫 번째는 배열을 이용하는 방식이고 두 번째는 연결리스트를 이용하는 방식입니다.
 배열을 이용하여 리스트를 구형하면 일단 간단합니다. 몇 번째 칸에 무슨 정보를 넣는지만 지정해주면 되고 출력도 매우 간단합니다. 하지만 칸과 칸 사이에 만약 삽입하거나 어떠한 정보를 삭제할 수도 있는데 이 과정을 구현하기가 어렵습니다. 또한, 배열은 항목의 개수에 제한이 있습니다. 30개로 지정하면 최대 30개의 정보만 넣을 수 있습니다.
 연결리스트를 이용할 경우 구현이 조금 복잡합니다. 그 이유는 다른 정보와 연결을 해주는 작업도 해야 하기 때문입니다. 항목과 항목을 연결하는 방식이라 삽입과 삭제가 매우 간편합니다. 따라서 크기도 제한적이지 않습니다.

 리스트에서 주로 사용하는 함수들은 다음과 같습니다. add_first는 리스트의 제일 앞의 위치에 요소를 추가하는 함수이고 add는 특정한 pos라는 위치에 추가하고 delete는 삭제하는 함수입니다. is_empty는 리스트가 비었는지 is_full은 리스트가 꽉 찼는지, display는 리스트를 순서대로 출력하는 함수입니다.

 먼저 정수형 리스트 배열을 만들기 위해서 선언하였습니다. element는 정수형이라고 지정하였고 정수형 배열의 크기는 100입니다. length는 리스트의 길이를 파악하기 위해 쓰입니다.
  리스트를 이용하기 위해서는 초기화하여야 합니다. 초기화하는 방법은 길이를 0으로 하면 됩니다. 이 함수에서는 지난 시간에 배운 구조체 포인터를 이용하였습니다. L이라는 리스트의 길이를 0으로 초기화 하였습니다.

 이제 리스트의 상태를 확인해보겠습니다. 
 리스트가 비었는지는 is_empty 함수입니다. 만약 리스트의 길이가 0이라면 비어있으므로 1을 반환하고 아니면 0을 반환합니다.
 리스트가 가득 찼는지는 is_full 함수로 확인합니다. 만약 길이가 리스트의 최대 크기인 100과 같다면 가득 찼으므로 1을 반환하여야 하고 아니면 0을 반환합니다.

 배열로 구성된 리스트에서는 특정한 위치에 항목을 추가하기 위해서는 특정 위치 다음의 항목들은 모두 한 칸 미뤄야 합니다. 그래서 먼저 리스트가 가득 찼는지 확인합니다. 리스트가 가득 찼으면 정보를 추가할 수 없고 배열이기 때문에 위치는 0 이상이어야 하며 위치는 최대 길이보다 작은 위치여야 합니다. 이 조건들을 만족하면 특정 위치 position부터 마지막 항목들의 위치를 1씩 증가시킵니다. 
 position 위치에 목표로 하는 항목을 추가하고 항목이 추가되었으므로 길이를 1씩 늘려줍니다.

 이번에는 리스트를 삭제하는 방법에 대해서 알아보겠습니다. 삭제와 반대로 특정 위치의 항목을 반환하고 다음에 있는 항목들을 한 칸씩 앞으로 당기는 원리입니다. 
 먼저 배열이기 때문에 위치는 0보다 작으면 안 되고 위치는 최대 길이 다음이면 안 됩니다. 그 경우에는 위치가 잘못되었기 때문에 프로그램을 종료합니다.
 사용 가능한 위치일 경우 그 위치의 정보를 item에 일시적으로 저장합니다.
그런 후 위치 다음의 항목들을 반복문으로 모두 위치를 옮겨줍니다. 그리고 전체 길이를 1 감소시킵니다. 마지막으로 item을 반환합니다.
 삽입과 삭제는 원리만 알면 서로 비슷한 방법이라서 어렵지 않습니다.

확실히 배열을 이용할 경우 방법은 매우 간단하지만 다른 항목들의 위치를 모두 바꿔야 하므로 불필요한 작업이 많습니다.

 이제 배열이 아닌 연결을 이용하여 구현한 리스트에 대해서 알아보겠습니다. 이 방법에서는 노드(node)라는 개념이 필요합니다. 노드는 데이터와 주소를 가지고 있는 쌍입니다. 기차를 리스트라고 표현할 때 노드는 한 칸을 의미하고 데이터와 다음 칸과 연결하는 고리인 link를 가지고 있습니다. 즉 데이터와 다른 노드의 주소를 저장하는 장소인 link를 포함하는 한 쌍입니다. 다음 노드의 주소는 포인터를 이용하여 저장합니다.
 
 연결을 이용한 리스트의 장점은 삽입과 삭제가 매우 간편합니다. 특정 부분을 자르고 그 부분에 삽입하거나 특정 위치의 노드를 때네면 삭제할 수 있기 때문입니다. 이러한 특성 때문에 메모리가 연속적이지 않고 크기도 제한이 없습니다. 하지만 삽입과 삭제를 하기 위해서는 노드 관계를 수정하여야 하므로 구현하기가 어렵고 모든 노드마다 주소를 지정해주어야 하므로 오류가 발생할 수 있습니다.

 연결로 구현한 리스트에는 3가지의 종류가 있습니다. 단순 연결리스트, 원형 연결리스트, 이중 연결리스트가 있습니다. 이 3가지 종류의 리스트는 다음 글에서 알아보고 리스트를 이용한 예시를 만들어 보겠습니다.