[C언어] 연결리스트(링크드 리스트) 구현하기

연결리스트(링크드 리스트)는 프로그래밍에서 쓰이는 자료구조 중 하나이다. 메모리 공간인 노드(Node)에 데이터와 포인터를 저장한다. 노드들이 한 줄로 연결되어있는 방식으로 데이터를 저장한다. 연결 리스트는 자료의 추가 삭제가 단 시간에 가능하다는 장점이 있다. 대신, 배열이나 트리에 비해 데이터를 검색하는데 시간이 오래 걸린다는 단점이 있다.

1. addrear() 함수를 이용한 단일 연결 리스트 구현

단일 연결 리스트의 구조

리스트의 마지막에 노드를 추가하는 addrear() 함수를 만들어보자.

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

// 연결 리스트를 구성할 Node 구조체
struct Node {
	int data;			// 노드에 저장할 데이터
	struct Node *next;	// 현재 노드의 다음 노드 포인터
};

struct Node *pStart = NULL;	// 리스트의 첫 노드의 포인터
struct Node *pEnd = NULL;	// 리스트의 마지막 노드의 포인터

void addrear(int val)
{
	struct Node *Current;	// 리스트에 추가할 새 노드 생성
	Current = (struct Node *) malloc(sizeof(struct Node));
	Current->data = val;	// 새 Node data 필드에 val 을 저장
	Current->next = NULL;	// 리스트 마지막에 추가할 노드이므로 다음 노드 없음

	if(pStart == NULL)		// 첫 번째 노드일 경우
		pStart = pEnd = Current;
	else {
		pEnd->next = Current;	// 마지막 노스트 다음에 새로 만든 노드 추가
		pEnd = Current;		// 리스트 마지막에 추가하는 것이므로 pEnd 를 바꿔줌
	}
}

void printlist(struct Node *Current)
{
	// Current 가 가리키는 리스트를 출력한다.
	Current = pStart;
	while (Current != NULL) {
		printf("%d\n", Current->data);
		Current = Current->next;
	}
}

int main(void)
{
	int i;
	for (i = 1; i <= 5; i++) 
		addrear(i);	// 새 노드를 만들어 리스트 뒤에 i를 추가
	printlist(pStart);
	return 0;
}

실행시켜보면, 다음과 같이 출력된다.

1
2
3
4
5

 

2. addfront() 함수를 이용한 연결 리스트 구현

리스트의 맨 앞에 노드를 추가하는 addfront() 함수를 만들어보자.

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

// 연결 리스트를 구성할 Node 구조체
struct Node {
	int data;			// 노드에 저장할 데이터
	struct Node *next;	// 현재 노드의 다음 노드 포인터
};

struct Node *pStart = NULL;	// 리스트의 첫 노드의 포인터
struct Node *pEnd = NULL;	// 리스트의 마지막 노드의 포인터

void addfront(int val)
{
	struct Node *Current;	// 리스트에 추가할 새 노드 생성
	Current = (struct Node *) malloc(sizeof(struct Node));
	Current->data = val;	// data 필드에 val 을 저장

	if(pStart == NULL) {		// 첫 번째 노드일 경우
		Current->next = NULL;	// 다음 노드가 아직 없으므로 NULL 이다.
		pStart = pEnd = Current;
	}		
	else {
		Current->next = pStart;	// 새로 추가한 노드의 다음 노드가 기존의 첫번째 노드
		pStart = Current;	// 첫 번째 노드를 이번에 새로 만든 노드로 바꿔줌
	}
}

void printlist(struct Node *Current)
{
	// Current 가 가리키는 리스트를 출력한다.
	Current = pStart;
	while (Current != NULL) {
		printf("%d\n", Current->data);
		Current = Current->next;
	}
}

int main(void)
{
	int i;
	for (i = 1; i <= 5; i++) 
		addfront(i);	// 새 노드를 만들어 리스트 앞에 추가
	printlist(pStart);
	return 0;
}

 

3. 특정한 data 를 가진 노드 1개만 지우는 delete() 함수 구현

void delete(int val) 
{
	// data 필드값이 val 인 Node 를 1 개 찾아 지운다.
	if (pStart == NULL) 
		return;
    
	if (pStart->data == val) {
		struct Node *Current = pStart;
		free(Current);
		pStart = pStart->next;
        return;
	}
    
	struct Node *p = pStart;
	struct Node *q = p->next;
	while(q != NULL) {
		if (q->data == val) {
			p->next = q->next;
			free(q);
			break;
		}
		p = q;
		q = p->next;
	}
}