자료구조 - 순차 자료구조 ( 선형 리스트 ) & 연결 자료구조

* 리스트(List) 란 ?

자료를 나열한 목록을 말한다. (일반적으로 아래와 같은 표의 형태)

이름	주소	출석번호	이메일
kim	seoul	99	abc@naver.com
you	tokyo	77	test@naver,com
lee	busan	33	as@daum.net

 

*선형 리스트(Linear List)란 ?

이러한 형태의 리스트를, 컴퓨터에서는 선형 리스트(Linear List)로 표현한다. 선형 리스트의 핵심은 선처럼 연결된 리스트이기 때문에 "순서"가 중요하다.

EX )  중국집 = (짜장면 ,탕수육 , 꿔바로우 ........ )

리스트가 공백일 경우도 허용된다. 그때는 빈 괄호인 () 로 표현하면 된다.

이러한 자료형인 리스트는 순서가 중요하다. 따라서 메모리에 저장될때도 같은 순서로 저장된다.
(물리적 순서 = 논리적 순서)

 

 

 

* 선형 리스트 -  원소의 위치

원소의 위치는 다음과 같이 계산할 수 있다.

저장이 시작된 위치를 a, 원소의 길이를 l 라고 했을때,

i 번째 원소의 위치 = a + ( i - 1 ) * l , 즉, 첫번째 원소부터 계산해보면 a , a +l , a + 2l .......... a+(i-1)*l이 된다.

 

*선형 리스트 - 원소의 삽입 / 삭제

원소는 논리적 순서대로 저장되어있다. 이러한 원소들 사이에 새로운 원소를 삽입하려면 원소를 삽입할 자리가 있어야한다. 따라서, 삽입할 위치 뒤에 저장된 원소들을 한자리씩 이동시켜야한다. 그리고 공백이 생기면, 그 자리에 새로운 원소를 삽입한다.

새로운 원소를 삽입할 때의 자리이동 횟수 = n - k + 1 = 마지막 원소의 자릿값 - 삽입할 자리의 인덱스 + 1

반대로 원소의 삭제의 경우도 마찬가지로 자리이동이 있어야 한다. 중간에 빈 공백을 메꾸기 위해서 뒤에있던 원소들을 삭제된 원소쪽으로 한칸씩 당겨줘야한다. 

원소 삭제시 자리이동 횟수 =  n - k = 마지막 인덱스 - 삭제된 인덱스

 

*2차원 배열의 물리적 저장 방법

 

*행 우선 순서 방법(row major order) - C 컴파일러의 방식

 

행번호를 기준으로  저장하는 방법.  (왼쪽에서 오른쪽으로 책읽을때와 같은 순서대로)

이름	주소	출석번호	이메일
kim	seoul	99	abc@naver.com
you	tokyo	77	test@naver,com

즉, 위 표의 2차원 리스트를 행 우선 방법으로 나열해보면

메모리 저장 순서 =>  {kim, seoul , 99, abc@naver.com , you, tokyo, 77, test@naver.com} 

               3차원 리스트부터는 행 우선 순서 방법이 "면 우선순서 방법"으로 명칭이 바뀐다. 알아만 놓자

 

 

 

*열 우선 순서 방법(column major order)

열번호를 기준으로 저장하는 방법. (위에서 아래로)

메모리 저장 순서 => (kim , you , seoul, tokyo , 99,77 , abc@naver.com , test@naver.com)

 

---

*연결 자료구조 (Linked Data Structure)

순차 자료구조는 물리적 순서 = 논리적 순서 이기 때문에, 삽입 및 삭제시에 원소들의 위치를 이동시켜야만 했다. 이는 필요한 작업 이외의 추가적인 작업과 시간이 소요되므로 순차 자료구조의 비효율성이라고 할 수 있다.

연결 자료구조는 물리적 순서 != 논리적 순서이다. 따라서 물리적 순서를 맞추기위해 오버헤드(추가적 작업 및 시간소요)가 발생하지 않으며, 크기 변경이 유연하고 더 효율적인 메모리사용이 가능하다.

 

 

 

*연결 리스트의 종류

• 단순 연결 리스트
• 원형 연결 리스트
• 이중 연결 리스트
• 이중 원형 연결 리스트

 

연결리스트는 <원소, 주소>의 구조를 갖는다.

원소는 Data field라고 하며 원소의 값을 저장한다. 주소는 link field라고 하며 다음 노드의 주소를 저장한다. (C에서는 포인터 변수를 사용하여 주소값을 저장)

 

요일을 순차 선형 리스트와 연결 리스트로 표현하면 차이점을 볼 수 있다.

 

*순차 리스트

순차 선형 리스트에서의 요일

 

*연결 리스트

연결 리스트 이름을 포인터 변수 라고 말한다. 포인터 변수는 리스트의 첫번째 노드를 가리키는 동시에, 연결된 리스트 전체를 의미한다. 그리고 리스트의 마지막 노드의 link field에는 이 원소가 끝임을 알리기 위해서 null을 저장한다. 따라서 공백 연결 리스트에는 null이 들어가있다.

 

* 단순 연결리스트(singly linked list) 의 삽입/삭제

*삽입

week = { <월,200> <금,300> <일,null> }  "월"과 "금"사이에 "수"를 삽입하는 경우를 예로들면

1. 공백노드를 하나 만들고, 포인터가 이 노드를 가리키게한다.

2. data field에 "수"라는 값을 저장한다. (수의 위치는 150이라고 해보자)

3. <수>의 link feild에 200을 가리키도록 저장한다. 200은 "금"의 위치이다.  - <수,200>

4. 다음으로는 월의 link feild를 "수"를 가르키도록 바꿔준다.

week = { <월,150> <수,200> <금,300> <일,null> } 이 된다.

 

 

*삭제

삭제의 경우에도 비슷한다. 원소를 삭제하고 순서를 맞추기 위해 삭제한 원소 바로앞 노드의 link field값을 조정하게 된다.

 

 

 

 

*원형 연결 리스트 (circular linked list)

단순 연결 리스트에서는 마지막 노드가 끝을 알리기 위해 null을 가리켰다. 원형 연결 리스트에서는 마지막 노드가 첫 번째 노드를 가르키기 때문에 계속 원을 돌듯이 순회하게 된다.

 

*공백 리스트일 경우에는 자기자신이 처음이자 끝이므로, 포인터(리스트이름)은 노드 A를 가르키고, A는 자기 자신을 가르키게 구성된다.

*원형 연결 리스트의 삽입

마지막 노드 - 첫 번째 노드의 연결부위만 제외하면 단순 연결리스트에서의 삽입과 같다.