리스트의 소개

리스트(List) 또는 선형 리스트(Linear list)는 우리들이 자료를 정리하는 방법 중의 하나이다.

우리는 일상생활에서 많은 리스트를 사용하고 있고 리스트에는 보통 항목들이 차례대로 정리되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다.

L = (item0, item1, ... )

리스트는 집합하고는 다르다. 집합에는 각 항목 간에 순서의 개념이 없으나 리스트에는 항목들 간에 순서가 있다. ex)한 주일의 요일들, 한글 자음의 모임, 카드 한 벌의 값, 임의의 다항식

이들 리스트를 가지고 할 수 있는 연산들은 무엇이 있을까? 보통 다음과 같은 연산들을 생각할 수 있다.

새로운 항목을 리스트의 임의의 위치에 추가한다.
기존의 항목을 리스트의 임의의 위치에서 삭제한다.
모든 항목들을 삭제한다.
기존의 항목을 대치한다.
리스트가 특정한 항목을 가지고 있는지를 살핀다.
리스트의 특정 위치의 항목을 반환한다.
리스트 안의 항목의 개수를 센다.
리스트가 비었는지, 꽉 찼는지를 체크한다.
리스트 안의 모든 항목을 표시한다.

사람들은 리스트를 사용할 때 보통 항목들의 위치에 대해서는 별로 신경 쓰지 않는다.

그러나 프로그램이 리스트를 사용할 때는 항목의 위치를 사용하는 것이 편리하다.

즉, 첫번째 위치에 있는 항목을 가져온다거나 10번째 위치에 새로운 항목을 저장하는 것이다.

이런 식으로 항목의 위치를 사용하면 더욱 정밀하게 리스트상에서의 연산을 기술할 수 있다.

자, 이제 리스트를 어떻게 구현할 것인지를 생각해보자.

C언어에서는 기본적으로 제공하는 배열을 이용하면 리스트 ADT를 가장 간단하게 구현할 수 있다.

그러나 배열을 가지고 리스트를 구현하면 그 크기가 고정된다. 즉, 크기가 고정된 공책에 리스트의 항목들을 적으면 공책이 가득 찰 수 있듯이 리스트를 배열로 구현하면 넣을 수 있는 항목의 수가 제한된다.

다른 방법으로는 '포인터'를 이용하여 연결 리스트를 만드는 방법이다.

연결 리스트는 필요할 때마다 중간에 속지를 추가해서 사용할 수 있는 바인더 공책과 비슷하다.

연결 리스트는 조금 복잡하지만 크기가 제한되지 않는 유연한 리스트를 구현할 수 있다.

배열로 구현된 리스트

배열은 메모리 안에 순차적으로 공간이 할당된다고 해서 순차적 표현(Sequential representation)이라고도 한다.

배열을 사용하여 리스트 ADT를 구현하게 되면 삽입과 삭제 시에 상당한 오버헤드가 따른다. 그러나 구현이 비교적 간단하고 효율적인 것이 장점이다.

구체적으로 배열을 이용하여 리스트를 구현하는 C코드를 만들어보자.

먼저 1차원 배열이 있어야하고 배열의 이름은 list, 현재 배열에 저장된 자료들의 개수를 나타내는 변수를 length라고 하자.

그리고 배열에 저장되는 항목은 element 타입이라고 가정하자.

1차원 배열 list와 length를 구조체로 묶어서 이 구조체의 타입을 ArrayListType이라고 정의하자.

모든 리스트 연산을 구현하는 함수에는 이 구조체의 포인터가 전달된다.

모든 함수들은 이 포인터를 이용하여 list배열과 length에 접근할 수 있다.

이런 식으로 하면 전역 변수를 사용하지 않아도 되는 큰 장점이 있다.

C프로그래밍에서 오류를 줄이는 한 가지 방법은 전역 변수를 사용하지 않는 것이다.

즉, 함수의 동작에 필요한 변수들은 되도록 매개 변수를 이용하여 전달하는 것이 바람직하다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_LIST_SIZE 100

typedef int element;
typedef struct {

	int list[MAX_LIST_SIZE];
	int length;

}ArrayListType;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

void init(ArrayListType* L) {
	L->length = 0;
}

int is_empty(ArrayListType* L) {
	return L->length == 0;
}

int is_full(ArrayListType* L) {
	return L->length == MAX_LIST_SIZE;
}

void display(ArrayListType* L) {
	for (int i = 0; i < L->length; i++) {
		printf("%d\n", L->list[i]);
	}
}

먼저 비교적 간단한 함수들인 리스트를 초기화하는 함수인 init함수와 리스트가 비어 있는지를 검사하는 is_empty함수와 가득 찼는지를 검사하는 is_full함수와 리스트의 내용을 출력하는 display 함수를 먼저 구현하였다.

다음으로 리스트 ADT에서 가장 중요한 연산인 삽입과 삭제 함수를 구현해보자.

add함수는 먼저 배열이 가득차지 않았나를 검사하고 삽입 위치가 적합한 범위에 있는지를 검사한다.

다음으로 할 일은 삽입 위치에 있는 자료들을 한 칸씩 뒤로 이동하는 것이다.

여기서 주의할 점은 맨 뒤쪽의 자료부터 한 칸씩 뒤로 이동해야 한다는 것이다. 그렇지 않으면 이동하는 도중에 저장된 자료가 지워지게 된다.

즉, length-1 위치에서 시작하여 position까지의 항목들을 위치 i에서 (i+1)로 한 칸씩 뒤로 이동하여야 한다.

void add(ArrayListType* L, int position, element item) {

	if (!is_full(L) && (position >= 0) && (position<=L->length)) {
		int i;
		for (i = (L->length - 1); i >= position; i--) {
			L->list[i+1] = L->list[i];
		}
		L->list[position] = item;
		L->length++;

	}
}

삭제할 때는 자료를 삭제한 후에 삭체 위치부터 맨 끝까지의 자료를 한 칸씩 앞으로 옮겨야 한다.

이번에는 앞에서 뒤로 이동해야 한다. 즉, position위치에서 시작하여 length-2까지 i+1의 내용을 i로 옮기면 된다.

element delete(ArrayListType* L, int position) {
	//position : 삭제하고자 하는 위치
	//반환 값 : 삭제되는 자료
	int i;
	element item;

	if (position<0 || position>L->length) error("위치 오류");

	item = L->list[position];

	for (i = position; i < (L->length - 1); i++) {
		L->list[i] = L->list[i + 1];
	}

	L->length--;
    
	return item;
}

위의 구현된 연산들을 사용하여 배열로 구현한 리스트를 사용하는 간단한 메인 프로그램을 살펴보면 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_LIST_SIZE 100

typedef int element;
typedef struct {

	int list[MAX_LIST_SIZE];
	int length;

}ArrayListType;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

void init(ArrayListType* L) {
	L->length = 0;
}

int is_empty(ArrayListType* L) {
	return L->length == 0;
}

int is_full(ArrayListType* L) {
	return L->length == MAX_LIST_SIZE;
}

void display(ArrayListType* L) {
	for (int i = 0; i < L->length; i++) {
		printf("%d\n", L->list[i]);
	}
}

void add(ArrayListType* L, int position, element item) {

	if (!is_full(L) && (position >= 0) && (position<=L->length)) {
		int i;
		for (i = (L->length - 1); i >= position; i--) {
			L->list[i+1] = L->list[i];
		}
		L->list[position] = item;
		L->length++;

	}
}

element delete(ArrayListType* L, int position) {
	//position : 삭제하고자 하는 위치
	//반환 값 : 삭제되는 자료
	int i;
	element item;

	if (position<0 || position>=L->length) error("위치 오류");

	item = L->list[position];

	for (i = position; i < (L->length - 1); i++) {
		L->list[i] = L->list[i + 1];
	}

	L->length--;
	return item;
}

int main() {

	ArrayListType list;
	ArrayListType* plist;

	//ArrayListType의 구조체를 정적으로 생성하고 이 구조체를 가리키는 포인터를
	//함수의 매개변수로 전달한다.

	init(&list);
	add(&list, 0, 10);
	add(&list, 0, 20);
	add(&list, 0, 30);
	display(&list);

	//ArrayListType의 구조체를 동적으로 생성하고 이 구조체를 가리키는 포인터를
	//함수의 매개 변수로 전달한다.
	
	plist = (ArrayListType*)malloc(sizeof(ArrayListType));
	init(plist);
	add(plist, 0, 10);
	add(plist, 0, 20);
	add(plist, 0, 30);
	display(plist);

	free(plist);

	return 0;
}

ArrayListType의 구조체는 정적 또는 동적 메모리 할당으로 생성이 가능하고 또한 함수 안에 지역 변수로 선언하거나 함수 외부에서 전역 변수로도 선언이 가능하다.

연결 리스트

배열을 사용하여 리스트를 구현하면 장점과 단점이 있다.

장점은 구현이 간단하다는 것이고 단점은 크기가 고정된다는 것이다.

즉, 동적으로 크기가 늘어나거나 줄어들 수 없기 때문에 만약에 데이터를 추가하고 싶은데 더 이상 남은 공간이 없다면 문제가 발생한다.

물론 더 큰 배열을 만들어서 기존의 배열에 있는 데이터들을 전부 복사하면 되지만 이것은 많은 CPU시간을 낭비한다.

또한 새로운 데이터를 삽입하거나 삭제하기 위해서는 기존의 데이터들을 앞이나 뒤로 이동하여야 한다.

이번 절에서는 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현(Linked representation)에 대하여 배운다.

이 연결된 표현은 '데이터'와 '링크'로 구성되어 있고 링크가 데이터들을 연결하는 역할을 한다.

연결된 표현은 매우 널리 사용되며 리스트의 구현에만 사용되는 것이 아니고 다른 여러 가지의 동적 자료 구조인 스택, 큐, 트리, 그래프 등을 구현하는 데 널리 사용된다.

일단 연결된 표현은 데이터를 한군데 모아두는 것을 포기하는 것이다.

데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.

데이터들의 순서를 유지하기 위하여 앞의 데이터는 뒤의 데이터를 가리키는 줄을 가진다.

앞의 데이터에서 다음 데이터를 찾아가려면 앞의 데이터의 줄을 따라가면 된다.

이런 식으로 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked list)라고 한다.

C프로그램에서는 상자를 연결하는 줄을 포인터(Pointer)로 구현한다.(포인터를 사용하면 하나의 자료에서 다음 자료를 쉽게 가리킬 수 있다.)

연결 리스트에서는 항목을 중간에 삽입할 때 앞뒤에 있는 데이터들을 이동할 필요 없이 줄만 변경시켜주면 된다.

삭제 시에도 마찬가지로 데이터들을 옮길 필요가 없이 그냥 데이터들을 연결하는 줄만 수정하면 된다.

연결 리스트의 또 하나의 장점은 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다는 것이다.

이것은 순차적인 표현 방법인 배열에 비하여 상당한 장점이 된다. 그러나 장점만 있는 것은 아니고 배열에 비하여 상대적으로 구현이 어렵고 오류가 발생하기 쉽다.

하나의 프로그램 안에는 동시에 여러 개의 연결 리스트가 존재할 수 있다.

이럴 경우, 연결 리스트들을 구별하는 것은 맨 첫 번째 데이터이다.

첫 번째 데이터만 알 수 있으면 연결 리스트의 나머지 데이터들은 줄만 따라가면 얻을 수 있다.

연결 리스트의 구조

여기서 말하는 상자를 컴퓨터 용어로 노드(Node)라고 부른다.

연결 리스트는 이들 노드들의 집합이며 이들은 데이터를 저장하고 있고 서로 연결되어 있다.

노드들은 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하면 된다.

일반적인 노드는 데이터 필드(Data field)와 링크 필드(Link field)로 구성되어 있다.

데이터 필드에는 우리가 저장하고 싶은 데이터가 들어가고 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다.

이 포인터를 이용하여 다음 노드로 건너갈 수 있다.

연결 리스트에서는 첫 번째 노드를 알아야만이 전체의 노드에 접근할 수 있다.

따라서 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것은 헤드 포인터(Head pointer)라고 한다.

그리고 연결 리스트의 마지막 노드의 링크 필드는 NULL로 설정되는데 이는 더 이상 연결된 노드가 없다는 것을 의미한다.

연결 리스트에서 노드들은 메모리상의 어떤 곳에나 위치할 수 있다.

즉 노드들의 저장위치 순서가 리스트상의 순서와 동일하지 않을 수 있다는 특징을 가지고 있다.

연결 리스트를 사용하면 연속적인 기억 공간이 없어도 데이터를 저장하는 것이 가능하고 미리 기억 공간을 확보할 필요도 없다.

즉, 필요할 때마다 노드를 동적으로 생성하여 연결하면 된다.

그러나 이러한 장점만 있는 것은 아니고 단점도 있다. 첫째로 링크 필드를 위한 추가 공간이 필요하게 되고 둘째로 연산의 구현이나 사용 방법이 배열에 비해 복잡해진다.

따라서 프로그래밍 오류가 발생할 가능성도 많아진다.

연결 리스트에는 다음과 같은 3가지의 연결 리스트가 있다.

1. 단순 연결 리스트(Singly linked list) : 하나의 방향으로만 연결되어 있음
2. 원형 연결 리스트(Circular linked list) : 단순 연결 리스트와 같으나 맨 마지막 노드의 링크 값이 첫 번째 노드를 가리킴
3. 이중 연결 리스트(Doubly linked list) : 각 노드마다 링크 필드가 2개씩 존재, 각각의 노드는 앞에 있는 노드를 가리키는 링크와 다음에 있는 링크를 가리키는 링크를 함께 가지고 있다.

지금부터 이 3가지의 연결 리스트를 차례대로 알아보자.

단순 연결 리스트

단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있다.

마지막 노드의 링크 필드 값은 NULL이 된다.

먼저 단순 연결 리스트에서의 삽입, 삭제 연산에 대하여 추상적으로 살펴본 다음, C언어를 이용하여 구현하여보자.

가장 일반적인 경우의 삽입은 중간에 삽입하는 경우이다.

1. 먼저 삽입하고자 하는 노드인 new 노드가 after 노드를 가리키게 해야 한다.

2. before 노드의 링크 필드에 after 노드의 주소가 들어 있으므로 before 노드의 링크를 new 노드의 링크로 복사하면 된다.

3. 그리고 before 의 링크가 new를 가리키게 한다.

삭제하는 경우에도 마찬가지이다.

1. before 노드의 링크가 after 노드를 가리키도록 변경하면 된다.

2. after 노드의 주소가 removed 노드의 링크에 있으므로 removed 노드의 링크를 before 노드의 링크로 복사하면 된다.

단순 연결 리스트의 구현

연결 리스트에서 노드는 C언어의 구조체를 이용하여 정의된다.

구조체 안에는 데이터를 저장하는 데이터 필드와 포인터인 링크 필드가 존재한다.

데이터 필드는 element 타입의 데이터를 저장하고 있다.

링크 필드는 현재 정의되고 있는 구조체를 가리키는 포인터로 정의된다.

typedef int element;
typedef struct ListNode{

	element data;
	struct ListNode* link;

}ListNode;

노드의 구조가 구조체를 이용하여 정의되었지만 아직 노드는 정의되지 않았음에 주의하여야 한다.

구조체 ListNode는 노드를 만들기 위한 '설계도'에 해당된다.

일반적으로는 연결 리스트에서는 필요한 때마다 동적 메모리 할당을 이용하여 노드를 동적으로 생성한다.

다음 코드에서는 임시 포인터 변수 p1을 만들고 malloc 함수를 이용하여 노드의 크기만큼의 메모리를 할당받는다.

이 할당된 메모리가 노드가 되는 것이다.

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

위 코드까지 실행되면 노드가 하나 생성되고 p1이 이를 가리킨다. 아직 노드에는 아무것도 채워지지 않았음을 유의하라.

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

p1->data = 10;
p1->link = NULL;

일반적으로 연결 리스트에는 여러 개의 노드가 서로 연결되어 있다.

따라서 같은 방식으로 두 번째 노드도 역시 동적으로 생성하고, 첫 번째 노드의 링크 필드가 두 번째 노드를 가리키도록 하여 두 개의 노드를 서로 연결하여보자.

ListNode *p2;
p2=(ListNode*)malloc(sizeof(ListNode));
p2->data = 20;
p2->link = NULL;
p1->link = p2;

이하 같은 식으로 원하는 만큼의 노드를 동적으로 생성하여 연결하면 된다.

노드를 더 생성하고 싶으면 이상의 과정을 원하는 만큼 반복하면 된다.

free(p1);
free(p2);

한 가지 주의할 점은 동적 메모리 할당을 이용하였기 때문에 사용이 끝나면 반드시 메모리를 해제해주어야 한다.

삽입 연산

단순 연결 리스트의 경우, 앞의 코드를 이용하면 새로운 노드를 생성하여 리스트의 뒤에 연결시킬 수 있지만 만약에 중간에 삽입하고 싶다면 앞에서 살펴보았던 알고리즘을 사용하여야 될 것이다.

기존의 연결 리스트가 존재하는 경우, 노드의 삽입 때마다 이 함수를 호출하여 사용하는 것이 편리하다.

따라서 일반적인 경우를 위한 삽입 함수를 만들어보자.

먼저 하나의 단순 연결 리스트를 나타내는 데 필요한 최소한의 데이터는 무엇인가를 생각해보자.

우리는 단순 연결 리스트의 경우, 첫 번째 노드를 가리키는 포인터 값만 알고 있으면 연결 리스트 안의 모든 노드에 접근이 가능하다는 것을 알고 있다.

따라서 하나의 단순 연결 리스트는 첫 번째 노드를 가리키는 하나의 포인터만 있으면 충분하다.

보통 이 포인터는 헤드 포인터(Head pointer)라고 불린다.

ListNode* head;

헤드 포인터의 이름은 반드시 head가 되어야 하는 것은 아니고, 헤드 포인터만 있으면 리스트 전체의 노드에 접근할 수 있으므로 하나의 리스트라고 생각할 수도 있다.

따라서 list1, list2 .. 와 같이 이름을 지을 수도 있다.

삽입 연산의 가장 일반적인 경우는 연결 리스트의 중간에 새로운 노드를 삽입하는 경우이다.

삽입하고자 하는 위치의 바로 앞에 있는 노드를 가리키는 포인터를 p라고 하고, 삽입하고자 하는 노드를 가리키는 포인터를 new_node라고 하자.

노드를 삽입하는 함수를 insert_node 함수라고 하면 이 함수는 다음의 3개의 인수를 받는다.

void insert_node(ListNode** phead, ListNode* p,ListNode* new_node)

phead : 헤드 포인터 head에 대한 포인터
p : 삽입될 위치의 선행노드를 가리키는 포인터, 이 노드 다음에 삽입된다.
new_node : 새로운 노드를 가리키는 포인터

여기서 헤드 포인터의 포인터를 전달한 이유는 함수 안에서 헤드 포인터를 변경해야 하기 때문이다.

삽입 알고리즘은 다음의 3가지 경우로 나누어 생각하여야 한다.

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	if (*phead == NULL) { //공백 리스트인 경우
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) { //p가 NULL이면 첫 번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else { //p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}

1. head가 NULL인 경우 : head가 NULL이면 현재 삽입하려는 노드가 첫 번째 노드가 된다. 따라서 head의 값만 변경하면 된다.
2. p가 NULL인 경우 : 선행 노드 p가 NULL값일 때는 리스트의 맨 앞에 삽입한다. 먼저 new_node의 link가 head와 같은 값을 갖도록 하고 다음에 head가 new_node를 가리키도록 한다.
3. head와 p가 NULL이 아닌 경우 : 가장 일반적인 경우다. new_node의 link에 p->link 값을 복사한 다음, p->link가 new_node를 가리키도록 한다.

삭제 연산

노드를 삭제하는 함수를 remove_node 함수라고 하면 이 함수는 다음의 3개의 인수를 받는다.

void remove_node(ListNode** phead,ListNode* p,ListNode* removed)

phead : 헤드 포인터 head의 포인터
p : 삭제될 노드의 선행 노드를 가리키는 포인터
removed : 삭제될 노드를 가리키는 포인터

p가 NULL인지 아닌지에 따라 삭제 알고리즘도 다음의 2가지의 경우로 나누어 생각하여야 한다.

void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	if (p == NULL) {
		*phead = (*phead)->link;
	}
	else {
		p->link = removed->link;
	}

	free(removed);
}

1. p가 NULL인 경우 : 연결 리스트의 첫 번째 노드를 삭제한다. 헤드 포인터를 변경하고 removed 노드가 차지하고 있는 공간을 시스템에 반환한다.
2. p가 NULL이 아닌 경우 : 먼저 removed 앞의 노드인 p의 링크가 removed 다음의 노드를 가리키도록 변경하면 된다. 추가 작업으로는 removed 노드가 차지하고 있는 공간을 시스템에 반환하며 된다.

방문 연산

연결 리스트에 존재하는 노드들을 순차적으로 방문하는 알고리즘을 만들어보자.

방문 연산은 반복 루프를 사용하는 반복 알고리즘과 순환 기법을 모두 사용할 수 있다.

먼저 반복 알고리즘을 살펴보자. 함수의 매개 변수는 리스트의 첫 번째 노드를 가리키는 포인터가 된다.

노드의 링크 값이 NULL이 아니면 계속 링크를 따라가면서 노드를 방문한다.

링크 값이 NULL이면 연결 리스트의 끝에 도달한 것이므로 반복을 중단한다.

방문 연산은 연결 리스트에서 가장 기본이 되는 연산이므로 그 개념을 확실하게 이해해야 한다.

void display(ListNode* head) {
	ListNode* p = head;
	while (p != NULL) {
		printf("%d->", p->data);
		p = p->link;
	}
	printf("\n");
}

방문 연산을 순환적으로 만들어보면 다음과 같다. 매개 변수 p가 NULL이 아니면 p의 데이터를 출력하고, p->link값을 매개변수로 하여 현재 함수를 순환 호출한다.

void display_recur(ListNode* head) {
	ListNode* p = head;
	if (p != NULL) {
		printf("%d->", p->data);
		display_recur(p->link);
	}
}

순환 호출은 반복적인 방법보다 보통 실행 시간이 더 걸리므로 일반적인 경우에는 반복적인 방법을 사용하기 바란다.

탐색 연산

리스트의 원소 값을 탐색하는 연산도 아주 기본적인 연산이다.

먼저 포인터p가 첫 번째 노드를 가리키도록 한 다음, 순서대로 링크를 따라가면서 노드의 데이터와 비교하면 된다.

ListNode* search(ListNode* head, int x) {
	ListNode* p;
	p = head;
	while (p != NULL) {
		if (p->data == x) return p; //탐색 성공
		p = p->link;
	}
	return p; //탐색 실패일 경우 NULL반환
}

역시 링크 값이 NULL이면 연결 리스트의 끝에 도달한 것이므로 탐색을 중단한다. 반환 값은 탐색 값을 가지고 있는 노드를 가리키는 포인터이다.

두 개의 리스트 L1과 L2를 하나로 만드는 연산

두 개의 리스트를 합치려면 먼저 첫 번째 리스트의 맨 끝으로 간 다음, 마지막 노드의 링크가 두 번째 리스트의 맨 처음 노드를 가리키도록 변경하면 된다.

주의할 점은 head1이나 head2가 NULL인 경우를 반드시 처리해줘야 한다.

ListNode* concat(ListNode* head1, ListNode* head2) {
	ListNode* p;
	if (head1 == NULL) return head2;
	else if (head2 == NULL) return head1;

	else {
		p = head1;
		while (p->link != NULL) {
			p = p->link;
		}
		p->link = head2;
		return head1;
	}
}

리스트를 역순으로 만드는 연산

이 함수에서는 세 개의 포인터 p,q,r 포인터를 사용하여 연결 리스트를 순회하면서 링크의 방향을 역순으로 바꾸면 된다.

새로운 연결 리스트를 만들지 않고 이와 같이 3개의 포인터를 사용하여 현재의 연결 리스트 안에서 문제를 해결하는 기법은 상당히 흥미롭다.

다만 주의할 점은 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아놓아야 한다.

p는 아직 처리되지 않는 노드, q는 현재 역순으로 만들 노드, r은 이미 역순으로 변경된 노드를 가리킨다.

r은 q, q는 p를 차례로 따라간다.

ListNode* reverse(ListNode* head) {
	ListNode* p, * q, * r;
	p = head;
	q = NULL;
	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}

	return q;
}

전체 프로그램

#include <stdio.h>

typedef int element;
typedef struct ListNode{

	element data;
	struct ListNode* link;

}ListNode;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	if (*phead == NULL) { //공백 리스트인 경우
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) { //p가 NULL이면 첫 번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else { //p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}

void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	if (p == NULL) {
		*phead = (*phead)->link;
	}
	else {
		p->link = removed->link;
	}

	free(removed);
}

void display(ListNode* head) {
	ListNode* p = head;
	while (p != NULL) {
		printf("%d->", p->data);
		p = p->link;
	}
	printf("\n");
}

void display_recur(ListNode* head) {
	ListNode* p = head;
	if (p != NULL) {
		printf("%d->", p->data);
		display_recur(p->link);
	}
}

ListNode* search(ListNode* head, int x) {
	ListNode* p;
	p = head;
	while (p != NULL) {
		if (p->data == x) return p; //탐색 성공
		p = p->link;
	}
	return p; //탐색 실패일 경우 NULL반환
}

ListNode* concat(ListNode* head1, ListNode* head2) {
	ListNode* p;
	if (head1 == NULL) return head2;
	else if (head2 == NULL) return head1;

	else {
		p = head1;
		while (p->link != NULL) {
			p = p->link;
		}
		p->link = head2;
		return head1;
	}
}

ListNode* reverse(ListNode* head) {
	ListNode* p, * q, * r;
	p = head;
	q = NULL;
	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}

	return q;
}

ListNode* create_node(element data, ListNode* link) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(ListNode));
	if (new_node == NULL) error("메모리 할당 에러");
	new_node->data = data;
	new_node->link = link;

	return new_node;
}


int main() {
	ListNode* list1 = NULL, * list2 = NULL;
	ListNode* p;

	//list1 = 30->20->10

	insert_node(&list1, NULL, create_node(10, NULL));
	insert_node(&list1, NULL, create_node(20, NULL));
	insert_node(&list1, NULL, create_node(30, NULL));

	display(list1);

	//list1 = 20->10

	remove_node(&list1, NULL, list1);
	display(list1);

	//list2 = 80->70->60

	insert_node(&list2, NULL, create_node(60, NULL));
	insert_node(&list2, NULL, create_node(70, NULL));
	insert_node(&list2, NULL, create_node(80, NULL));

	display(list2);

	//list1 = list1 + list2

	list1 = concat(list1, list2);

	display(list1);

	//list1을 역순으로

	list1 = reverse(list1);

	display(list1);

	//list1에서 20 탐색
	p = search(list1, 20);
	printf("탐색성공 : %d\n", p->data);

	return 0;
}