C로 만드는 자료구조-List란?

리스트(List)란?

리스트는 가장 단순한 구조를 가지는 기초적인 자료구조이며 스택(Stack), 트리(Tree), 그래프(Graph), 큐(Queue) 등등 다른 자료구조들의 구현에도 사용된다. 

 리스트는 자료를 순서대로 저장하는 자료구조이다. 여기서 순서는 '한 줄'을 의미하며 여러 개의 자료가 일직선으로 서로 연결된(Sequential) '선형구조‘를 의미한다.

예를 들어 아래 파일을 저장하는 프로그램을 생각해보자

파일이 순서대로 저장되어 있음을 볼 수 있다.

 이때 리스트와 배열이 상당히 비슷하다고 생각하는 사람이 있을 것이다. 실제로 매우 비슷하다 하지만 배열과 다르게 원소 중 하나가 제거된다면 그 빈자리를 채워야 하고 또한 중간에 원소를 추가하기 위해서는 뒤에 있는 원소들을 한 칸씩 뒤로 이동시켜야 한다는 것에서 차이점이 있다.

만약 파일 중간에 위치한 '20'을 제거한다면

'20'이 없어진 자리를 채우기 위해 뒤에 있던 자료들이 한칸 씩 앞으로 갔음을 알 수 있다. 만약 그냥 배열이었다면 빈자리가 빈칸으로 남아 있었을 것이다.

리스트의 개념

 앞서 말했듯이 리스트는 자료를 순서대로 저장하는 자료구조이다. 또한 여러개의 자료가 일직선으로 서로 연결되어 있는 선형구조의 특성을 가지고 있다. 이제 다음 4가지 리스트 예에서 이러한 리스트의 정의와 특성을 살펴보자.

1. 문자열

문자열(string)은 문자(character) 자료들을 차례대로 저장한다. 문자열을 문자 리스트라고도 한다.

 위 문자열 'LIST'는 모두 4개의 문자로 구성되어 있고 리스트에 저장되는 자료는 각각의 문자가 된다(‘L', 'I', 'S', 'T'), 그리고(‘L','I','S','T'), 이러한 문자가 순서대로 저장되어 선형구조를 이루고 있음을 알 수 있다..

2. 문자열 리스트

문자열 리스트는 문자열을 차례대로 저장하는 리스트를 말한다.

위 그림을 보면 3가의 문자열이 순서대로 저장되어 있음을 알 수 있다. 이때 문자열 리스트에서는 저장되는 자료가 문자열이기 때문에 저장되는 마지막 문자가 '\0'임을 알아야 한다, '\0'은 NULL을 가리키는 값으로 실제 값이 0(숫자 값)이다. 따라서 2번째 저장된 자료가 없는 것이 아니라 빈 문자열이 저장되어 있음을 알아야 한다.

3. 행렬

우리가 흔히 아는 행렬을 리스트로 저장할 수 있다. 이때 각각의 열이 행의 개수만큼 자료를 가지는 리스트라고 생각하면 된다.

 위 그림과 같이 왼쪽에 기존에 우리가 알고 있는 행렬을 오른쪽과 같이 리스트의 형태로 나타낼 수 있다. 오른쪽의 리스트는 각 열마다 5개의 자료를 저장하고 있는 3개의 리스트를 저장한 리스트이다.

4. 다항식

우리가 잘 알고 있는 다항식도 리스트를 이용하여 저장할 수 있다.
예를 들어 3X^3+2X^2+2를 다음과 같이 저장할 수 있다. 

 위 그림과 같이 다항식을 내림차순으로 정리하여 계수 값을 저장하는 리스트로 포현이 가능하다. 이때 계수가 0인 경우를 꼭 포함해야 함을 주의하자. 계수가 0인 경우를 저장하지 않으면 잘못된 다항식이 저장되기 때문이다. 

추상 자료형

리스트 사용에 필요한 기본 연산을 정리한 리스트의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다.

이름		입력	출력	설명
리스트 생성	crateList()	최대 원소 개수 n	리스트 I	최대 n 개의 원소를 가지는 공백 리스트 I를 생성
리스트 삭제	deleteList()	리스트 I	n/a	리스트의 모든 원소 제거
원소 추가 가능 여부 판단	isFull()	리스트 I	True/False	리스트의 원소 개수가 최대 원소 개수와 같은지를 반환
원소 추가	addElement()	리스트 I, 원소 위치 p, 원소 e	성공/실패	원소 e를 특정 위치p에 추가
원소 제거	removeElement()	리스트 I, 원소 위치 p	성공/실패	리스트의 위치 p에 있는 원소 제거
원소 개수	getListLength()	리스트 I	원소의 개수	리스트의 원소 개수를 반환
원소 반환	getElement()	리스트 I 원소 위치 p	원소	리스트의 위치 p에 있는 원소를 반환

표에서 N/A는 해당 값이 존재하지 않거나 필요하지 않음을 의미한다.(Not available)

추상 자료형 정의를 통해 리스트 사용에 필요한 기본적인 연산들을 살펴보았고 이를 통해 실제로 구현해 볼 것이다.
리스트를 구현할 때 크게 2가지 방법으로 나뉘는데 배열을 이용한 배열 리스트와 포인터를 이용한 연결 리스트로 나뉜다.

배열 리스트와 연결 리스트의 차이점

배열 리스트와 연결 리스트는 둘 다 선형 자료구조라는 공통점이 있지만 저장 방식에서 차이가 있다. 배열 리스트는 최대 저장 개수가 정해진 반면 연결 리스트는 최대 저장 개수 제약이 없다. 또한 연결 리스트는 동적 할당을 이용하기 때문 또한 중간에 원소를 제거해도 앞뒤 자료 사이 연결 포인터만 재설정하면 되기 때문에 상대적으로 간편하다.