DS07 - 순차 자료구조와 선형 리스트의 이해

순차, 연결 자료구조                        

 자료는 구조화 하는 방법에 따라 리스트(List), 스택(Stack), 큐(Queue), 데크(Deque), 트리(Tree), 그래프(Graph) 등으로 나눌 수 있다. 이러한 자료구조 유형은 프로그램으로 구현하는 방식에 따라 순차 자료구조와 연결 자료구조로 나눌 수 있다. 순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식이다. 따라서 순차 자료구조는 논리적인 순서와 물리적인 순서가 항상 일치해야 한다. C 프로그래밍에서 순차 자료구조는 배열을 통해 구현하고, 연결 자료구조의 경우 포인터를 이용하여 구현한다.

구분	순차 자료구조	연결 자료구조
메모리 저장 방식	메모리의 저장 시작 위치부터 빈자리 없이 자료를 순서 대로 연속하여 저장한다. 논리적인 순서와 물리적인 순서가 일치하는 구현 방식이다.	메모리에 저장된 물리적 위치나 물리적 순서와 상관없이 링크에 의해 논리적인 순서를 표현하는 구현 방식 이다.
연산 특징	삽입,삭제 연산을 해도 빈자리 없이 자료가    순서대로 연속하여 저장된다. 변경된 논리적인  순서와 저장된 물리적인 순서가 일치한다.	삽입, 삭제 연산을 하여 논리적인 순서가 변경되어도, 링크 정보만 변경되고 물리적인 순서는   변경되지 않는다.
프로그램 기법	배열을 이용한 구현	포인터를 이용한 구현

선형 리스트의 표현                         

 자료의 특징(추상 자료형)과 주로 사용할 연산(알고리즘)에 따라 최적의 형태로 자료를 구조화해야 하는데, 자료를 구조화하는 가장 기본적인 방법은 나열하는 것이다. 아래의 표는 이름, 과일, 악기를 나열하여 나타낸 표이다. 이렇게 자료를 나열하여 나타낸 목록을 리스트(List)라고 한다.

이름	과일	나이
일지매	사과	23
홍길동	레몬	25
이순신	포도	35

  이때 원소들을 순서대로 나열한 리스트를 선형 리스트(Linear List)또는 순서 리스트(Ordered List)라고 한다.

리스트는 아래와 같은 방법으로 표현한다.

리스트 이름 = (원소 1, 원소 2, 원소 3 ... , 원소 n) 과일 = (사과, 레몬, 포도)

원소가 하나도 없는 공백리스트의 경우 다음과 같이 표현한다.

리스트 이름 = ()

  선형 리스트는 메모리에 저장하는 구현 방식에 따라 순차 방식으로 구현하는 선형 순차 리스트(Linear Sequential List)와 연결 방식으로 구현하는 선형 연결 리스트(Linear Linked List)로 나뉜다.

일반적으로 선형 순차리스트를 '선형 리스트'라고 하고 선형 연결리스트는 '연결 리스트'라고 한다.

선형 리스트(선형 순차 리스트)는 원소들이 나열된 논리적인 순서와 메모리에 저장되는 물리적인 순서가 일치하는 순차 자료구조 방식(배열)으로 구현한다. 선형 리스트는 원소를 논리적인 순서대로 메모리에 연속하여 저장한다.

다음은 위의 나이 리스트가 메모리에 저장된 방식을 나타낸 그림이다.

나이	메모리 주소	값
23	0xab384620	23
25	0xab384624	25
35	0xab384628	35

  나이 항목은 정수형(Interger Type)의 자료형이기 때문에 4 byte의 크기를 가진다. 따라서 메모리 주소는 4 byte씩 증가하게 되고 메모리에는 '나이' 항목에 저장된 순서인 (23, 25, 35)의 순서대로 값이 저장되게 된다.

이처럼 선형 리스트는 리스트의 논리적인 순서와 메모리에 저장된 물리적인 순서가 일치한다.

선형 리스트의 이러한 성질 덕분에 우리는 시작 위치와 원소의 크기를 알고 있다면 특정 원소의 메모리 상의 위치를 손쉽게 찾을 수 있다.

시작 위치가 A이고 원소의 크기가 B인 선형 리스트에서 n번째 원소의 위치는 A +(n-1)B로 나타낼 수 있다.

선형 리스트의 원소 삽입                  

 선형 리스트는 논리적 순서와 물리적 순서가 일치해야 한다. 즉, 원소의 추가가 일어나려면 추가될 원소를 위한 자리가 존재해야 하고, 이러한 자리를 만들기 위해 추가될 원소의 뒤에 위치할 원소들은 모두 뒤로 이동해야 한다.

다음은 선형 리스트의 원소 삽입의 예이다.

삽입 전	1	2	4	5	6	7	8	9
삽입 중	1	2		4	5	6	7	8	9
삽입 후	1	2	3	4	5	6	7	8	9

정수형 원소를 가진 리스트는 (1, 2, 4, 5, 6, 7, 8, 9)로 이루어져 있고, 원소 2와 4 사이에 원소 3을 삽입하려 한다면, 원소 2와 4 사이에 원소 3이 들어갈 자리를 먼저 마련한 후 원소를 삽입하게 된다. 이는 논리적 구조 뿐만 아니라 물리적 구조에도 해당되는 사항이다.

이를 공식화 하면 원소가 n개인 선형 리스트에서 k번 자리에 원소를 삽입하려면 k번 원소부터 마지막 원소인 (n-1)원소까지 총 (n-1)-k+1개의 원소를 옮겨야 한다. 따라서 이동 횟수는 (n-1)-k+1 = (마지막 원소의 인덱스 - 삽입할 자리의 인덱스 +1)이 된다.

선형 리스트의 원소 삭제                  

 선형 리스트에서 원소를 삭제하면 그 자리는 빈공간이 된다. 선형 리스트는 원소를 논리 순서와 같은 순서로 메모리에 연속하여 저장해야 하는 순차 자료구조 이므로 중간에 빈자리가 없어야 한다. 따라서 원소를 삭세한 위치 뒤에 있는 원소를 모두 한 자리씩 앞으로 옮겨야 한다.

다음은 선형리스트의 원소 삭제의 예이다

삭제 전	1	2	3	4	5	6	7	8	9
삭제 중	1	2		4	5	6	7	8	9
삭제 후	1	2	4	5	6	7	8	9

정수형 원소를 가진 리스트는 (1, 2, 3, 4, 5, 6, 7, 8, 9)로 이루어져 있고, 원소 3을 삭제하려 한다면, 원소 3이 있던 자리는 빈 자리가 된다. 논리적인 순서에서는 빈 자리가 존재하지 않기 때문에 물리적이 순서도 빈자리가 존재해서는 안된다. 빈자리를 채우기 위해 3 이후의 원소인 (4,5,6,7,8,9)를 한칸 씩 앞당겨 빈 자리를 채우게 된다.

이를 공식화 하면 원소가 n개인 선형 리스트에서 k번 자리에 원소를 삭제하려면 (k+1)번 원소부터 마지막 n번 원소까지, 즉 n-(k+1)+1개의 원소를 모두 한자리씩 앞으로 옮겨야 한다. 필요한 이동 횟수는 n-(k+1)+1이 되어

n-k(마지막 원소의 인덱스 - 삭제한 원소의 인덱스)가 된다.