순서리스트의 연결표현(1)

연결리스트에서는 첫 번째 노드를 제외한 모든 노드들은 항상 그 직전노드의 링크를 통해 접근된다.

 

일반적으로 연결리스트의 노드 추가함수를 설계할 때는 insertLinkedList(L, current, x)와 같이 추가원소의 직전노드를 나타내는 노드포인터 변수 current를 형식인수로 정의해서 추가노드를 current 노드의 다음으로 추가하고, 삭제함수를 정의할 때도 위의 deleteLinkedlist(L, current)와 같이 삭제할 노드의 직전노드를 나타내는 노드포인터 변수 current를 형식인수로 정의해서 current 노드의 다음 노드를 삭제한다.

 

추가노드나 삭제노드의 직전노드를 형식인수로 정의하지 않으면, 함수 내부에서 그 직전노드를 탐색해서 처리해야 하는데, 이것은 그만큼 함수의 코드를 복잡하게 한다.

 

따라서 연결리스트에서 노드 추가와 삭제함수를 정의할 때는 함수 밖에서 미리 추가할 노드나 삭제할 노드의 직전노드를 탐색하여 알고 있는 것으로 가정해서 간결한 함수 코드의 작성을 도모한다.

 

C에서 연결리스트의 구현은 노드 메모리를 확보하는 방법에 따라 토인터와 동적 변수를 이용하는 방법과 배열을 이용하는 방법으로 구분할 수 있다.

 

그리고 노드의 링크들을 구성하는 방법에 따라 단순연결리스트(singly linked list)와 이중연결리스트(doubly linked list)로 구분할 수 있다.

 

단순연결리스트는 각 노드가 직후노드에 대한 링크만을 포함하고, 이중연결리스트는 각 노드가 각각 직전노드(논리적으로 바로 직전 순서의 노드)와 직후노드에 대한 두 개의 링크를 포함한다.

 

포인터와 동적변수를 이용해서 구현하는 방법은 연결리스트의 개념을 직관적으로 나타내기 때문에 우리가 연결리스트를 이해하는데 유용하다.

 

3.3.1 단순연결리스트

단순연결리스트는 각 노드가 직후노드에 대한 링크만을 포함하는 것으로, 특별한 언급이 없다면 연결리스트는 단순연결리스트를 의미한다.

일반적으로 C 프로그래밍에서 연결리스트의 링크를 포인터 변수로 정의하면 노드 메모리는 동적변수로 생성해서 관리해야 한다.

 

추가연산을 수행할 때는 추가 노드를 동적변수로 생성해서 사용하고, 삭제 연산을 수행할 때 삭제 노드의 메모리를 해제 한다.

 

공집합인 연결리스트의 생성

연결리스트를 구현하기 위해서는 먼저 노드 구조와 첫 번째 노드에 대한 포인터 변수(예를 들면, first)를 정의해야 한다. 노드 구조는 자기 참조 구조체로 정의한다.

 

그리고 첫 번째 노드포인터 first는 노드의 링크 필드와 같은 노드 포인터형으로, 처음 연결리스트를 생성하면 공집합이므로 NULL로 초기화 된다. 다음은 노드 구조를 정의하고, 공집합인 연결리스트 first를 생성하는 C 코드의 작성 예이다.

 

/* 노드구조 정의 */ Typedef struct node {    int data;    struct node *link; } listNode; listNode *first;   /* 첫 번째 노드에 대한 링크변수 */ First = NULL;   /* 공집합인 연결리스트 생성 */

연결리스트의 추가 연산

연결리스트에서 새로운 노드를 추가하려면 그 직전 노드를 알고 있어야 한다.

이것은 추가노드를 그 직전노드의 링크에 연결해야 하기 때문인데, 추가노드를 연결리스트의 첫 번째 노드로 추가하는 경우에는 직전노드가 없게 된다.

 

그리고 배열을 이용했던 순차리스트에서와는 달리 연결리스트에서는 새로운 노드를 추가하려면, 추가 노드를 위한 노드메모리를 미리 준비해 둔 노드포인터 변수를 이용해서 동적변수로 생성해서 확보해야 한다.

 

추가원소의 노드메모리(동적변수) 생성을 위해 미리 준비한 노드포인터 변수를 temp라고 하고, 추가원소의 직전 노드를 나타내는 노드포인터 변수를 current 라고 하면, 연결리스트에서 새로운 원소의 추가는 current 변수가 NULL이 아닌 경우와 NULL인 경우로 구분해서 고려할 수 있다.

 

(1) current 변수가 NULL 이 아닌 경우

이 경우는 추가원소의 직전노드인 current 노드(노드포인터 current가 나타내는 노드)가 존재하는 경우로, 추가노드는 current 노드의 직후노드로 추가된다.

 

C 프로그래밍에서 추가원소를 위한 노드메모리는 노드포인터 변수 temp와 동적메모리 할당함수 malloc()를 이용해서 동적변수로 생성한다.

 

따라서 추가원소 x를 연결리스트의 어떤 current 노드의 직후노드로 추가하려면, 먼저 추가원소를 위한 노드메모리를 생성한 후, 순차적으로 current 노드의 후속노드(current 노드의 링크가 나타내는 노드)를 temp 노드의 링크에 연결하고, current 노드의 링크에는 추가노드인 temp 노드를 연결하면 된다.