위와 같이 하나의 학생(Student)이라는 노드를 정의해봅시다. 이를 단일 연결리스트로 표현하면 다음과 같은 형태가 될 것입니다.

  삽입 함수는 매우 기본적인 로직을 따릅니다. 단순히 자신이 들어갈 위치까지 계속해서 넘어가다가 들어갈 위치를 찾으면 비로소 그 때 들어가면 됩니다. 기본적으로 사용자 정보들은 학번을 기준으로 오름차순으로 정렬되고, 동일한 학번은 입력되지 않는다고 했을 때 삽입(Insert) 함수는 다음과 같이 작성될 수 있습니다.

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

void insert(struct Student **head, int id, int score) {

struct Student *prevptr; // 삽입하려는 위치의 직전 노드 

struct Student *ptr; // 삽입하려는 위치의 노드

struct Student *element; // 삽입하려는 노드

element->id = id;

element->score = score;

element->next = NULL;

// 리스트가 비어있는 경우 

if((*head) == NULL) {

(*head) = element;

return;

} 

// 리스트가 비어있지 않은 경우 

prevptr = NULL;

ptr = (*head);

while(ptr != NULL) {

// 들어갈 위치를 찾지 못한 경우 

if(ptr->id < id) {

prevptr = ptr;

ptr = ptr->next;

}

// 들어갈 위치를 찾은 경우 

else {

// 첫 번째 원소로 들어가는 경우 

if(prevptr == NULL) (*head) = element;

// 첫 번째 원소로 들어가지 않는 경우 

else prevptr->next = element;

element->next = ptr;

return;

}

}

// 마지막 원소로 들어가는 경우

ptr->next = element; 

}

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

※ 역체인 ※

  역체인(Reverse Chain)은 연결리스트를 뒤집는 함수입니다. 만약 1부터 4까지 데이터가 노드로 연결이 되어있다면 다음과 같이 4부터 1까지 데이터가 노드로 연결이 되도록 바꾸는 과정이 역체인 과정이라고 할 수 있습니다.

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

typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer next;

};

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

  위와 같이 노드가 선언이 되어있다고 했을 때 역체인 함수는 다음과 같이 구현할 수 있습니다.

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

void reverse(NodePointer *head) {

NodePointer one, two, three;

int cout = 0;

two = NULL;

one = three = *head;

while(three != NULL) {

three = three->next;

// 실질적으로 역체인이 수행되는 라인 

two->next = one; 

one = two;

two = three;

}

}