_[5.1] 연결리스트의 개념

[문교식]

[5.1] 연결리스트의 개념

<<<<<  목 차  >>>>>

연결리스트의 필요성
연결리스트의 구조
연결리스트의 개념도
연결리스트란?

포인터

= = = = = = = = = = = = = 

연결리스트 (Linked List)의 필요성

배열 단원에서 배열의 기본 오퍼레이션을 배웠다.

◎ 배열에서 삽입과 삭제의 경우, 데이터의 이동이 빈번하게 됨을 보았다.

    이러한 데이터의 이동을 획기적으로 줄일 수 있는 자료구조가 연결리스트이다. 

◎ 또한 배열은 물리적으로 연속된 기억공간을 요구한다.

    예를 들면, 정수 1000개를 저장하는 공간이 배열로 선언될 때,

    1000개가 모두 연속된 기억공간을 차지한다.

    그러나 연결리스트는 이러한 제약조건이 불필요하다. 

◎ 연결리스트의 또 다른 특징으로, 레코드 단위로 추가와 삭제가 가능하므로

    필요한 만큼의 메모리 공간을 사용한다.

    그러나 배열의 경우는 실제의 사용여부와 관계없이 프로그램의 실행전에

    배열의 크기가 결정되고, 그 크기가 변하지 않는다.

    따라서 배열은 이러한 메모리의 낭비 요소가 있다.

◎ 프로그램 실행 중에 원래의 배열의 크기 보다 더 많은 공간이 필요하더라도

    배열의 크기를 더 추가할 수는 없다.

    그러나 연결리스트는 필요한 때에 필요한 만큼 레코드를 추가할 수 있기 때문에

    메모리를 효율적으로 사용한다는 장점이 있다.

◎ 단점으로는 레코드 간의 연결을 프로그램에서 직접 담당해야 하는 불편이 있으며,

    이로 인하여 프로그램 오류의 가능성이 높아진다는 단점이 있다.

    그러나 이러한 단점은 약간의 프로그래밍 연습으로 충분히 극복할 수 있다.

◎ 연결리스트는 '리스트'로 줄여서 표현하기도 한다.

[연습문제]  (1) 데이터의 삽입, 삭제가 빈번한 경우, 배열보다 연결리스트가 공간을 더 

효율적으로 사용할 수 있다. (O/X)

   (2) 연결리스트는 연속된 메모리 공간을 사용하는 것이 더 효율적이다. (O/X)

   (3) 연결리스트는 레코드 단위의 삽입과 삭제가 가능하다. (O/X)

   (4) 연결리스트에서 현재 레코드의 다음 레코드를 찾으려면 현재 레코드의 링크

부분을 따라간다. (O/X)

연결리스트의 구조

연결리스트는 구조체 배열과 마찬가지로 레코드 단위로 데이터를 저장한다. 

예를 들면, 부품 데이터는 pname(부품명), uprice(단가), qty(보유수)의

세 개의 필드로 이루어진 레코드의 집합이다.  

배열의 경우 (구조체 배열을 포함하여), 연속된 기억공간을 차지한다.

그러나 연결리스트는 각 레코드에 다음 레코드의 주소를 저장한 링크 필드(link field)가 있다.

 <<<  부품 리스트의 저장 예  >>>   

주소	pname	uprice	qty	다음 레코드의 주소
153	YT998	2410	98	NIL
154	CR218	10700	274	280
………	………	………	………	………
200	AC205	7500	170	201
201	AZ304	2500	7356	303
………	………	………	………	………
280	KO344	3600	76	282
281	TR092	38	336	153
282	OP252	520	178	404
………	………	………	………	………
303	BK175	375	1351	154
………	………	………	………	………
350	RX943	15000	322	281
………	………	………	………	………
………	………	………	………	………
404	RX370	2000	200	350

시작 주소는 200번지이다. 편의상 주소는 레코드 단위로 1씩 증가한다.

시작주소를 가장 먼저 찾는다. 

각 레코드의 끝에는 다음 레코드의 주소 필드가 있다.

마지막 레코드의 링크 필드는 'NIL'이다.

('NULL' 또는 'NIL'은 'empty'의 뜻으로, 연결리스트의 끝을 의미한다; 발음은 /n∧l/, /nil/)

이 주소 필드로 다음 레코드를 찾는다. 이런식으로 레코드를 하나씩 찾아낸다.

[연습문제] 위의 테이블에서

  ⑴ 280번지의 부품명은 무엇인가?  

  ⑵ 280번지의 다음 레코드의 주소는 무엇인가? 

  ⑶ 280번지의 다음 레코드의 부품명은 무엇인가?      

  ⑷ 마지막 레코드의 부품명은 무엇인가?  

레코드를 모두 방문하기

200번지를 찾아가면 [AC205, 7500, 170 : Link=201]; 다음 주소가 201이다.

201번지를 찾아가면 [AZ304, 2500, 7356 : Link=303]; 다음 주소가 303이다.

303번지를 찾아가면 [BK175, 375, 1351 : Link=154]; 다음 주소가 154이다.

154번지를 찾아가면 [CR218, 10700, 274 : Link=280]; 다음 주소가 280이다.

……………………………………………………………………………………………………………

이렇게 찾아가면 이 리스트의 마지막 레코드인 [YT998, 2410, 98 : Link=NIL]을 만난다. 

이 레코드의 링크 필드가 NIL이므로 이 레코드가 마지막 레코드가 된다.

[연습문제] 위의 리스트에서 '부품명'을 순서대로 출력하시오.  (시작주소는 150번지) 

연결리스트의 개념도

레코드에 저장된 주소는 시스템에서 관리하는 부분이고 사용자는 알 필요가 없다.

주소란 그 내용을 찾아가기 위한 수단이므로 프로그래머는 실제의 주소값을 알 필요는 없다.

아래 그림은 링크를 화살표로 표시한 개념도이다.

 <<<  부품 리스트  >>>

각 레코드의 첫째 필드는 pname(부품명), 둘째 필드는 uprice(단가),

셋째 필드는 qty(보유수)를 나타낸다.

다음 레코드의 주소를 저장하는 필드를 next라 하자.

next라는 필드는 다른 필드처럼 데이터를 담고 있는 것이 아니라 주소를 저장하고 있다.

이와 같이 주소를 저장하는 필드를 링크 필드(link field), 또는 포인터(pointer)라 한다.

맨 끝 레코드에 NIL 또는 사선으로 표시한다.

[연습문제] 1) 연결리스트의 개념도에서 링크(link)는 무엇으로 표현하는가? 

    2) 다음 레코드의 주소를 저장하는 필드를 '링크 필드' 또는 무엇이라 하는가?

    3) 마지막 레코드의 다음 레코드는 존재하지 않는다.

   마지막 레코드임을 나타내기 위해 링크 필드를 어떻게 표현하는가?

연결리스트란?

이와 같이 레코드의 연결을 통하여 자료를 저장하는 자료형태를

연결리스트(linked list)라 한다. 또는, 간단히, 리스트라고도 한다.
연결리스트에서는 레코드 대신 노드(node)라는 용어를 사용한다.

각 노드에는 하나 이상의 데이터 필드와

다른 노드와의 연결을 위한 하나 이상의 링크 필드가 있다.

즉, 연결리스트란 노드들이 연결된 자료구조를 말한다.

한 연결리스트 안의 모든 노드는 동일한 구조(형식)를 갖는다. 

[연습문제] 1) 연결리스트는 리스트가 연결된 상태를 말한다.

   따라서 리스트와 연결리스트는 다르다. (O/X)

    2) 연결리스트에서 '레코드'를 무엇이라고 부르는가?   

    3) 연결리스트에서 노드의 구성요소 두 가지는 무엇인가?

[연습문제] 아래의 테이블은 메모리 안에 저장된 연결리스트의 내용이다. 

              리스트의 시작주소는 150번지이다.

              이 리스트의 '고객번호'를 순서대로 출력하시오.

                       <<<  고객 리스트의 저장 예  >>>

주소	고객번호	구매수량	입금액	링크 (다음 노드의 주소)
145	K0339	400	2000	146
146	P0021	380	1500	175
………	………	………	………	………
150	K2317	530	3230	145
………	………	………	………	………
155	R3024	670	800	NIL
156	R3320	806	1000	155
………	………	………	………	………
175	P8803	280	1300	177
176	………	………	………	………
177	R9002	1200	2000	156

포인터 

위에서 '링크 필드'는 다음 노드의 주소를 갖고 있음을 이해하였다.

주소를 갖고 있다는 것은 어떤 기억장소(또는 메모리)를 찾아 갈 수 있다는 뜻이다.

기억장소는 정수를 저장할 수도 있고 (정수형; integer type),  

실수를 저장할 수도 있고 (실수형; floating point type),  

문자를 저장할 수도 있고 (문자형; character type),

그  외, 여러 형태의 데이터를 저장할 수 있다.

정수형 변수의 예; int  age;  // 변수 age는 정수값을 저장한다

실수형 변수의 예; float  height;  // 변수 height는 실수값을 저장한다

문자형 변수의 예; char  smoking;  // 변수 smoking은 문자값을 저장한다

문자열 변수의 예; char  name[30];  // 변수 name은 문자열을 저장한다

데이터 형식과 데이터의 예; 

    변수명                          데이터

age	16
height	158.4
smoking	'N'
name	"John"

이와 같은 변수의 저장 상황을 아래와 같이 개념도로 표현한다.

  (DS-arr-변수저장개념도-01)

(데이터가 아니라, 데이터를 저장한) 주소를 저장하는 기억장소를 포인터(pointer)라고 한다.

그런데, 그 주소에 저장된 데이터의 형식에 따라 다음과 같은 형식의 포인터로 분류한다;

정수형 포인터; 포인터가 갖고 있는 주소에 정수값을 저장한다. 

실수형 포인터; 포인터가 갖고 있는 주소에 실수값을 저장한다. 

문자(열) 포인터; 포인터가 갖고 있는 주소에 문자(열)를 저장한다. 

구조체 포인터; 포인터가 갖고 있는 주소에 구조체를 저장한다. 

포인터의 선언;  포인터 변수는 그 앞에 '*'('indirection operator'(간접값 연산자))를 붙인다.

     정수형 포인터의 예; int *year;  // year는 포인터인데, 정수값을 포인팅한다

    

       (DS-ptr-01-year)

       ; year가 갖고 있는 주소를 따라가면 정수값 2010을 얻는다.

     주소가 구체적으로 무엇인지를 표시할 필요는 없다.

     이와 같이, 주소를 간단히 화살표로 나타내는 개념도로 표현할 수 있다.

     실수형 포인터의 예; float *weight;  // weight는 포인터인데, 실수값을 포인팅한다

     

       (DS-ptr-02-weight)

       ; weight가 갖고 있는 주소를 따라가면 실수값 35.2를 얻는다.

     문자형 포인터의 예; char *RHneg;  // RHneg는 포인터인데, 문자값을 포인팅한다.

     

      (DS-ptr-03-RHneg) 

 ; RHneg가 갖고 있는 주소를 따라가면 문자값 'Y'를 얻는다.

      구조체 포인터의 예; struct Customer_struct *custA;  // custA는 구조체를 포인팅한다

     

       (DS-ptr-04-custA)

  ; *custA가 갖고 있는 주소를 따라가면 구조체 레코드 [John, 2546-9696, 1700]를 얻는다.

  포인터가 아닌 변수는 메모리에서 그 변수의 값을 직접 읽거나 쓸 수 있다.

  포인터형 변수는 그 값을 읽거나 쓰려면, 그 변수의 값을 주소로 하여

  그 주소를 찾아가서 그 주소의 내용을 읽거나 쓸 수 있다.

  포인터형 변수는 메모리를 2회 찾아간다.

  이것이 포인터형 변수는 메모리를 한번만 찾아가는 비 포인터 변수와의 다른점이다.

  이런 이유로 포인터형 변수를 'indirection(간접)'이라고 부른다.

  번거롭게 느끼겠지만, 그만한 이득이 있으니까 포인터 변수를 사용하게 된다.  

  특히, 포인터를 사용하면 메모리의 관리를 효율적으로 할 수 있다.

  포인터가 아니면 구현할 수 없는 고급의 자료구조들도 있다.

  다음 단원에서 포인터가 연결리스트에서 어떻게 활용되는지를 설명한다.

  (많은 학습자들이 포인터라는 산을 넘지못하고 좌절한다. 차근차근 읽고 또 읽으면 누구나 이해할 수 있다.

    그러나 포인터를 이해하면 얻을 수 있는 이득이 대단히 많다.

    포인터를 익숙하게 느낄때까지 위와 같은 개념도를 그려 보는 것이 아주 유용하다.)

[예제]  아래와 같이 변수가 선언되었을 때, 그 값이 무엇인가?
                 int   xVal, *yVal;
          xVal은 메모리 120번지에 저장되어 있다.
          yVal은 메모리 150번지에 저장되어 있다.
         

주소	내용
35	150
………	………
77	120
………	………
120	35
………	………
133	77
………	………
150	133
………	………

  ⑴ xVal의 값은?  (답; xVal은 120번지에 저장되어 있고,                   

                            120번지의 내용은 35이다. 따라서 xVal=35 )
  ⑵ *yVal의 값은? (답; *yVal은 포인터 변수이다.                                      
                             yVal은 150번지에 있고, 메모리 150에는 133이 들어있다.
                             이 133을 주소로 하여 한번 더 메모리를 찾는다.           
                             133번지에 77이 들어있다. 따라서 *yVal의 값은 77이다   )

[연습문제]  위의 예제에서 *xVal과 *yVal의 각각에 대하여,
               그 값이 저장된 상황을 개념도로 표현하자.  

심볼 테이블

프로그램에서 변수(또는 식별자)를 사용한다. 

프로그램에서 변수에 값을 넣기도 하고, 읽기도 한다.

이들 변수들은 메모리에 저장되어 있는데,

메모리 안에 있는 내용들은 모두 고유한 메모리 주소를 갖고 있고,

그 주소를 통하여 값을 읽거나 쓴다.

그렇다면 어떤 메카니즘으로 이것이 가능할까?

변수와 그 내용에 대한 정보를 담는 '심볼테이블(Symbol Table)'이 있다.

심볼테이블은 어느 한 프로그램이 사용하는

모든 식별자(identifier; 변수명, 함수명 등과 같은 이름)에 대한

메모리의 저장 정보를 유지하고 있다.

심볼테이블을 이용하여 식별자의 값을 읽거나 쓸 수 있다.

이러한 심볼테이블을 만들고 관리하는 일을

컴파일러(compiler)(프로그램을 실행하는 소프트웨어)가 한다.

[예]  아래와 같이 변수가 선언되었고, 
                 int   xVal, *yVal;
          xVal은 메모리 120번지에 저장되어 있다.
          yVal은 메모리 150번지에 저장되어 있다.

이 정보를 컴파일러는 아래와 같이 심볼테이블을 만든다.

변수명	주소
xVal	120
yVal	150
.....................	.....................

//