[자료구조] ep3-2) 이중연결리스트(Double Linked List)

ㅇ이중연결리스트: 노드 간의 링크가 두 개

이중연결리스트의 노드

이중연결리스트의 전체 구조

 

 

 

 

 

활용) 영문자 리스트 ADT

순위는 1부터 시작한다고 가정하며 순위 정보가 유효하지 않으면 화면에 에러 메시지 "invalid position"을 출력하고, 해당 연산을 무시한다

test case

 

 

 

두 가지 방법이 있다

첫 번째 방법: 전역변수 사용 x

- 헤더노드, 트레일러노드, 리스트의 크기에 대한 전역변수 사용 x

 

(전체코드)

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

typedef struct NODE {
	char element;
	struct NODE* prev;
	struct NODE* next;
} NODE;

void add(NODE* head, int rank, char element);
void delete(NODE* head, int rank);
void get(NODE* head, int rank);
void print(NODE* head);
void freeList(NODE* head);

int main() {
	NODE* head = (NODE*)malloc(1 * sizeof(NODE));
	NODE* tail = (NODE*)malloc(1 * sizeof(NODE));
	head->prev = NULL;
	head->next = tail;
	tail->prev = head;
	tail->next = NULL;
	int N;
	char command;
	int rank; // rank
	char element;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf(" %c", &command);
		if (command == 'A') {
			scanf(" %d %c", &rank, &element);
			add(head, rank, element);
		}
		else if (command == 'D') {
			scanf(" %d", &rank);
			delete(head, rank);
		}
		else if (command == 'G') {
			scanf(" %d", &rank);
			get(head, rank);
		}
		else if (command == 'P') {
			print(head);
		}
	}

	freeList(head);
	return 0;
}

void add(NODE* head, int rank, char element) {
	if (rank == 0) {
		printf("invalid position\n");
		return;
	}
	for (int i = 0; i < rank; i++) { // rank 지점까지 이동
		head = head->next;
		if (head == NULL) {
			printf("invalid position\n");
			return;
		}
	}
	NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
	newNode->element = element;
	newNode->next = NULL;
	newNode->prev = NULL;
	// 포인터 왼쪽 교체 작업
	newNode->prev = head->prev;
	(head->prev)->next = newNode;
	// 포인터 오른쪽 교체 작업
	newNode->next = head;
	head->prev = newNode;
}

void delete(NODE* head, int rank) {
	if (rank == 0) {
		printf("invalid position\n");
		return;
	}
	for (int i = 0; i < rank; i++) { // rank 지점까지 이동
		head = head->next;
		if (head->next == NULL) {
			printf("invalid position\n");
			return;
		}
	}
	(head->prev)->next = head->next;
	(head->next)->prev = head->prev;
	free(head);
}

void get(NODE* head, int rank) {
	if (rank == 0) {
		printf("invalid position\n");
		return;
	}
	for (int i = 0; i < rank; i++) { // rank 지점까지 이동
		head = head->next;
		if (head->next == NULL) {
			printf("invalid position\n");
			return;
		}
	}
	printf("%c\n", head->element);
}

void print(NODE* head) {
	head = head->next;
	while (head->next != NULL) {
		printf("%c", head->element);
		head = head->next;
	}
	printf("\n");
}

void freeList(NODE* head) {
    while (head != NULL) {
		NODE* temp = head;
		head = head->next;
		free(temp);
	}
}

/*
5
A 1 S
A 2 t
A 3 r
A 3 a
P

9
A 1 D
A 2 a
A 3 y
D 1
P
G 3
A 1 S
P
G 3
*/

 

 

 

 

 

 

두 번째 방법: 전역변수 사용 o

- 헤더노드, 트레일러노드, 리스트의 크기에 대한 전역변수 사용 o

 

(전체코드)

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

typedef struct NODE {
    char e;
    struct NODE* prev;
    struct NODE* next;
} NODE;

NODE* g_pHeader = NULL; // 리스트의 헤더 노드를 고정으로 가리키는 전역 노드 포인터
NODE* g_pTrailer = NULL; // 리스트의 트레일러 노드를 고정으로 가리키는 전역 노드 포인터
int g_n = 0; // 리스트의 크기를 저장하는 전역 변수

void add(int r, int e);
void delete(int r);
NODE* get(int r);
void print();
void freeList();

int main() {
    // 리스트 및 헤더 노드와 트레일러 노드 초기화
    g_pHeader = (NODE*)malloc(1 * sizeof(NODE));
    g_pTrailer = (NODE*)malloc(1 * sizeof(NODE));
    // 헤더와 트레일러 노드를 연결
    g_pHeader->prev = NULL;
    g_pHeader->next = g_pTrailer;
    g_pTrailer->prev = g_pHeader;
    g_pTrailer->next = NULL;
    int N;
    char cmd;
    int r;
    char e;

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf(" %c", &cmd);
        if (cmd == 'A') {
            scanf(" %d %c", &r, &e);
            add(r, e);
        }
        else if (cmd == 'D') {
            scanf(" %d", &r);
            delete(r); // 해당 위치의 노드를 삭제하고 반환
        }
        else if (cmd == 'G') {
            scanf(" %d", &r);
            NODE* result = get(r); // 해당 위치의 노드를 반환
            if (result != NULL) {
                printf("%c\n", result->e); // 반환된 노드의 문자 데이터 출력
            }
        }
        else if (cmd == 'P') {
            print();
        }
    }

    freeList();
    return 0;
}

void add(int r, int e) { // 노드를 특정 위치에 추가
    if (r < 1 || r > g_n + 1) { // 예외처리 - 유효하지 않은 위치
        printf("invalid position\n");
        return;
    }

    // 새로운 노드를 생성하고 할당 후에 문자 데이터를 저장
    NODE* newNode = (NODE*)malloc(sizeof(NODE));
    newNode->e = e;

    NODE* temp = g_pHeader;
    for (int i = 0; i < r; i++) { // r번째 위치까지 이동
        temp = temp->next;
    }

    // 교체 작업 1: 왼쪽
    newNode->prev = temp->prev;
    (temp->prev)->next = newNode;
    // 교체 작업 2: 오른쪽
    newNode->next = temp;
    temp->prev = newNode;

    g_n++; // 리스트 크기++
}

void delete(int r) { // 특정 위치의 노드를 삭제하고 반환
    if (r < 1 || r > g_n) { // 예외처리 - 유효하지 않은 위치
        printf("invalid position\n");
        return NULL;
    }

    NODE* targetNode = g_pHeader;
    for (int i = 0; i < r; i++) { // r번째 노드까지 이동
        targetNode = targetNode->next;
    }

    // 삭제할 노드의 이전 노드와 다음 노드를 연결
    (targetNode->prev)->next = targetNode->next;
    (targetNode->next)->prev = targetNode->prev;
    /*
    NODE* prevNode = targetNode->prev;
    prevNode->next = targetNode->next;
    targetNode->next->prev = prevNode;
    */
    g_n--; // 리스트 크기--

    free(targetNode); // 삭제된 노드 할당 해제
    return;
}

NODE* get(int r) { // 특정 위치의 노드를 반환
    if (r < 1 || r > g_n) { // 예외처리 - 유효하지 않은 위치
        printf("invalid position\n");
        return NULL;
    }

    NODE* targetNode = g_pHeader;
    for (int i = 0; i < r; i++) {
        targetNode = targetNode->next;
    }

    return targetNode; // 해당 위치의 노드를 반환
}

void print() { // 리스트의 모든 노드를 출력
    NODE* cur = g_pHeader->next;
    while (cur->next != NULL) { // 트레일러까지 반복
        printf("%c", cur->e);
        cur = cur->next;
    }
    printf("\n");
}

void freeList() {
    while (g_pHeader != NULL) {
        NODE* temp = g_pHeader;
        g_pHeader = g_pHeader->next;
        free(temp);
    }
    g_pHeader = NULL;
}

/*
5
A 1 S
A 2 t
A 3 r
A 3 a
P

9
A 1 D
A 2 a
A 3 y
D 1
P
G 3
A 1 S
P
G 3
*/

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)