[ 자료구조 ] 3. 연결 리스트(Linked List)

  연결 리스트(Linked List)는 포인터를 이용한 선형 구조로서 다양한 종류가 있습니다. 대표적인 것이 선형 리스트, 원형 리스트, 연결 스택, 연결 큐 등이 있습니다. 연결 리스트는 일반적으로 시험 문제로 출제가 될 때 실제 소스코드 구현과 관련한 문제가 출제된다는 점에서 포인터(Pointer)를 활용한 실질적인 구현 방법에 대해서 이해하고 있으셔야 합니다. 다만 이후에 트리(Tree) 구조 등과 관련한 개념에서는 실질적인 구현을 물어보지는 않고 그 동작 원리에 대해서만 자세히 물어본다는 특징이 있습니다.

  사실 연결 리스트는 단일 연결리스트만 확실히 이해해도 다른 것들은 무난하게 넘어가실 수 있습니다. 대표적인 단일 연결 리스트(Singly Linked List)의 예제에 대해서 알아보도록 합시다.

※ 삽입 함수 ※

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

struct Student {

int id; /* 학번 */

int score; /* 학생 성적 */

struct Student *next; 

};

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

  위와 같이 하나의 학생(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;

}

}

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

  처음 보았을 때는 어렵게 느껴질 수 있는데 간단히 생각해보면 다음과 같이 동작하는 겁니다. 연결되어있는 링크의 위치를 반대로 뒤집으려면 총 세 개의 변수가 필요한데 one, two, three 변수를 계속해서 오른쪽으로 이동시켜가며 역으로 연결해주는 거에요.