단순 연결 리스트(Simple Linked List)

.가장 단순하면서 가장 많이 쓰이기도 하는 형태

 

.정보를 저장하는 노드와 바로 다음 노드를 가리키는 링크 하나로 구성

 

.재배열(rearrangement)이 용이

 

----------------------------------------------------------------------------------------

 

.연결 리스트의 입구 : head

   - 일반적으로 전역 변수로 선언되어 모듈 내의 어떤 부분에서도 접근 가능하도록 개방되어 있고, 소멸되지 않는다.

 

.연결리스트의 마지막 노드 : tail

   - 마지막 노드임을 표시 (방법1 : 자기자신을 가리킴 , 방법2 : NULL 값)

----------------------------------------------------------------------------------------

 

단순 연결리스트의 노드 정의

 

struct _node

{

      int key;

      struct _node *next;

}

 

 _node구조체의 정의 내부에 다시 _node의 포인터가 들어가 있다. 이같은 구조체 정의를

 재귀적인 정의(recursive definition)라고 한다.

   - 포인터라는 것은 어떤 형의 데이터를 가리키든지 그 자체의 크기는 변함이 없기 때문이다.

   - 포인터가 정수를 가리킨다든지, 실수를 가리킨다든지, 아니면 더 큰 구조체를 가리킨다고 해서 포인터 자체의 크기가 변하는 것은 아니다(즉, sizeof(포인터)가 변하는 것은 아니다)

      포인터는 가리키는 데이터형과는 상관 없이 단지 주소를 저장할 뿐이기 때문이다.

----------------------------------------------------------------------------------------

 

단순 연결리스트 노드 정의의 개선

 

_node 구조체를 정의할 때 앞에 계속 struct를 붙인다는 것은 정말로 귀찮은 일이다.

C++에서는 단지 태그명(tag name)만을 쓰는 것으로 변수를 정의할 수 있다.

 

C에서는 typedef를 이용하면 구조체의 정의를 쉽게 할 수 있다.

 

 

typedef strcut _node

{

      int key;

      struct _node *next;

} node;

 

 

위의 typedef문의 뜻은 strcut _node와 같은 구조체를 node라는 데이터형으로 정의한다.

 

그러므로, 다음과 같이 변수를 정의할 수 있다.

 

node *LinkedList;