단순 연결 리스트

단순 연결 리스트에서는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든노드들이 연결되어 있다. 마지막 노드의 링크 필드 값은 NULL 이 된다. 예를 들어서 아래 그림에서는 정수 10, 30, 40 이 단순 연결 리스트에 저장되어 있다. 이제 우리는 단순 연결 리스트에서의 핵심적인 연산인 삽입 연산과 삭제 연산을 추상적으로 학습해 볼 것이다.

먼저 체크해야 할 상황들은

- 노드는 어떻게 정의할 것인가? : 자기 참조 구조체를 이용한다

- 노드는 어떻게 생성할 것인가? : malloc() 을 호출하여 동적 메모리로 생성한다.

- 노드는 어떻게 삭제할 것인가? : free() 를 호출하여 동적 메모리를 해제한다.

 

노드는 자기 참조 구조체를 이용하여 정의된다. 자기 참조 구조체란 자기 자신을 참조하는 포인터를 포함하는 구조체이다. 구조체 안에는 데이터를 저장하는 data 필드와 포인터가 저장되어 있는 link 필드가 존재한다. data 필드는 element 타입의 데이터를 저장하고 있다. link 필드는 ListNode 를 가리키는 포인터로 정의되며 다음 노드의 주소가 저장된다.

typedef int element;

typedef  struct ListNode { //노드 타입을 구조체로 정의한다다
  element data;
  struct ListNode *link;
} ListNode;

위의 코드에서 노드의 구조는 정의하였지만 아직 노드는 생성되지 않았음에 주의하여야 한다. 구조체 ListNode 는 노드를 만들기 위한 설계도에 해당한다. ListNode 를 가지고 실제 구조체를 생성하려면 구조체 변수를 선언해야 한다.

 

단순 연결 리스트는 헤드 포인터만 있으면 모든 노드를 찾을 수 있다. 따라서 다음과 같이 노드를 가리키는 포인터 head 를 정의하면 하나의 단순 연결리스트가 만들어졌다고 볼 수 있다. 현재는 노드가 없으므로 head 의 값은 NULL 이 된다.

ListNode *head = NULL;

어떤 리스트가 공백인지를 검사하려면 헤드 포인터가 NULL 인지를 검사하면 된다.

 

 

일반적으로는 연결 리스트에서는 필요할 대마다 동적 메모리 할당을 이용하여 노드를 동적으로 생성한다. 다음의 코드에서는 malloc() 함수를 이용하여 노드의 크기만큼의 동적 메모리를 할당 받는다. 이 동적 메모리가 하나의 노드가 된다. 동적 메모리의 주소를 헤드 포인터인 head 에 저장한다.

head = (ListNode *)malloc(sizeof(ListNode));

위의 코드까지 실행되면 노드가 하나 생성된다. 아직도 노드에는 아무것도 채워지지 않았다.

다음 절차는 새로 만들어진 노드에 데이터를 저장하고 링크필드를 NULL 로 설정하는 것이다.

head->data = 10;
head->link - NULL; //첫 노드가 생성되었으니 이게 마지막 노드이므로 link field 의 포인터는 NULL

일반적으로 연결 리스트에는 여러 개의 노드가 서로 연결되어 있다. 따라서 동일한 방식으로 두 번째 노드를 동적으로 생성하고 노드에 20을 저장해보자

ListNode *p;
p = (LisNode *)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;

이제 생성된 2개의 노드를 서로 연결해보자. 

head->link = p;

이렇게 하면 첫 번째 노드의 링크가 두 번째 노드를 가리키게 된다. #### 매우 중요

노드를 더 생성하여 붙이고 싶으면 위의 과정을 반복하면 된다.