1.리스트

링크드 리스트

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode{
    ElementType Data;
    struct tagNode* NextNode;
}Node;

/* 함수 원형 선언 */
Node* SLL_CreateNode(ElementType NewData);
void SLL_DestroyNode(Node* Node);
void SLL_AppendNode(Node** Head, Node* NewNode);
void SLL_InsertAfter(Node* Current, Node* NewNode);
void SLL_InsertNewHead(Node**, Node* NewHead);
void SLL_RemoveNode(Node** Head, Node* Remove);
Node* SLL_GetNodeAt(Node* Head, int Location);
int SLL_GetNodeCount(Node* Head);

#endif

#include "LinkedList.h"

/* 노드 생성 */
Node* SLL_CreateNode(ElementType NewData){
    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = NewData; // 데이터 저장
    NewNode->NextNode = NULL; // 다음 노드에 대한 포인터는 NULL로 초기화한다.

    return NewNode; // 노드의 주소를 반환한다.
}

/* 노드 소멸*/
void SLL_DestroyNode(Node* Node){
    free(Node);
}

/* 노드 추가 */
void SLL_AppendNode(Node** Head, Node* NewNode){
    /* 헤드 노드가 NULL 이라면 새로운 노드가 Head */
    if((*Head) == NULL){
        *Head = NewNode;
    }
    else{
        /* 테일을 찾아 NewNode를 연결한다. */
        Node* Tail = (*Head);
        while(Tail->NextNode != NULL){
            Tail = Tail->NextNode;
        }

        Tail->NextNode = NewNode;
    }
}

/* 노드 삽입 */
void SLL_InsertAfter(Node* Current, Node* NewNode){
    NewNode->NextNode = Current->NextNode;
    Current->NextNode = NewNode;
}

void SLL_InsertNewHead(Node** Head, Node* NewHead){
    if(*Head == NULL){
        (*Head) = NewHead;
    }
    else{
        NewHead->NextNode = (*Head);
        (*Head) = NewHead;
    }
}

/* 노드 제거 */
void SLL_RemoveNode(Node** Head, Node* Remove){
    if(*Head == Remove){
        *Head = Remove->NextNode;
    }
    else{
        Node* Current = *Head;
        while(Current != NULL && Current->NextNode != Remove){
            Current = Current->NextNode;
        }

        if(Current != NULL)
            Current->NextNode = Remove->NextNode;
    }
}

/* 노드 탐색 */
Node* SLL_GetNodeAt(Node* Head, int Location){
    Node* Current = Head;

    while(Current != NULL && (--Location) >= 0){
        Current = Current->NextNode;
    }

    return Current;
}

/* 노드 수 세기 */
int SLL_GetNodeCount(Node* Head){
    int Count = 0;
    Node* Current = Head;

    while(Current != NULL){
        Current = Current->NextNode;
        Count++;
    }

    return Count;
}

#include "LinkedList.h"

int main(){
    int i = 0;
    int Count = 0;
    Node* List = NULL;
    Node* Current = NULL;
    Node* NewNode = NULL;

    /* 노드 5개 추가 */
    for(i = 0; i < 5; i++){
        NewNode = SLL_CreateNode(i);
        SLL_AppendNode(&List, NewNode);
    }

    NewNode = SLL_CreateNode(-1);
    SLL_InsertNewHead(&List, NewNode);

    NewNode = SLL_CreateNode(-2);
    SLL_InsertNewHead(&List, NewNode);

    /* 리스트 출력 */
    Count = SLL_GetNodeCount(List);
    for(i = 0; i < Count; i++){
        Current = SLL_GetNodeAt(List, i);
        printf("List[%d] : %d\n", i, Current->Data);
    }

    /* 리스트의 세 번째 노드 뒤에 새 노드 삽입 */
    printf("\nInserting 3000 After [2] ...\n");

    Current = SLL_GetNodeAt(List, 2);
    NewNode = SLL_CreateNode(3000);

    SLL_InsertAfter(Current, NewNode);

    /* 리스트 출력 */
    Count = SLL_GetNodeCount(List);
    for(i = 0; i < Count; i++){
        Current = SLL_GetNodeAt(List, i);
        printf("List[%d] : %d\n", i, Current->Data);
    }

    /* 모든 노드를 메모리에서 제거 */
    printf("\nDestroying List...\n");

    for(i = 0; i < Count; i++){
        Current = SLL_GetNodeAt(List, 0);

        if(Current != NULL){
            SLL_RemoveNode(&List, Current);
            SLL_DestroyNode(Current);
        }
    }

    return 0;
}

 

gcc -o Test_LinkedList Test_LinkedList.c LinkedList.c

 

더블 링크드 리스트

#pragma once
#ifndef DOUBLE_LINKEDLIST_H
#define DOUBLE_LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;

	struct tagNode* PrevNode;
	struct tagNode* NextNode;
} Node;


/* 함수 원형 선언 */

Node* DLL_CreateNode(ElementType NewData);
void DLL_DestroyNode(Node* Node);
void DLL_AppendNode(Node** Head, Node* NewNode);
void DLL_InsertAfter(Node** Current, Node* NewNode);
void DLL_RemoveNode(Node** Head, Node* Remove);
Node* DLL_GetNodeAt(Node* Head, int Location);
int DLL_GetNodeCount(Node* Head);

#endif

#include "DoubleLinkedList.h"

/* 노드 생성 */

Node* DLL_CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node)); // 동적 할당

	NewNode->Data = NewData;
	NewNode->PrevNode = NULL;
	NewNode->NextNode = NULL;

	return NewNode;
}

/* 노드 소멸 */
void DLL_DestroyNode(Node* Node) {
	free(Node);
}

void DLL_AppendNode(Node** Head, Node* NewNode) {
	/* 헤드 노드가 NULL 이라면 NewNode가 Head */
	if ((*Head) == NULL) {
		*Head = NewNode;
	}
	else {
		/* 테일을 찾아 NewNode 를 연결한다. */
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL) {
			Tail = Tail->NextNode;
		}

		Tail->NextNode = NewNode;
		NewNode->PrevNode = Tail;
	}
}

/* 노드 삽입 */
void DLL_InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	if (Current->NextNode != NULL) {
		Current->NextNode->PrevNode = NewNode;
	}
	
	Current->NextNode = NewNode;
}

/* 노드 제거 */
void DLL_RemoveNode(Node** Head, Node* Remove) {
	if (*Head == Remove) {
		*Head = Remove->NextNode;
		
		if ((*Head) != NULL) {
			(*Head)->PrevNode = NULL;
		}

		Remove->NextNode = NULL;
		Remove->PrevNode = NULL;
	}
	else {
		Node* Temp = Remove;

		if (Remove->PrevNode != NULL) {
			Remove->PrevNode->NextNode = Temp->NextNode;
		}

		if (Remove->NextNode != NULL) {
			Remove->NextNode->PrevNode = Temp->PrevNode;
		}

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;

	}
}

/* 노드 탐색 */
Node* DLL_GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL &&  (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

/* 노드 수 세기 */
int DLL_GetNodeCount(Node* Head) {
	unsigned int Count = 0;
	Node* Current = Head;

	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;
	}

	return Count;
}

int main() {
	int i = 0;
	int Count = 0;
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	/* 노드 5개 추가 */
	for (int i = 0; i < 5; ++i) {
		NewNode = DLL_CreateNode(i);
		DLL_AppendNode(&List, NewNode);
	}

	/* 리스트 출력 */
	Count = DLL_GetNodeCount(List);
	for (int i = 0; i < Count; ++i) {
		Current = DLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	/* 리스트의 세 번째 칸 뒤에 노드 삽입 */
	printf("\nInserting 3000 After [2]...\n\n");

	NewNode = DLL_CreateNode(3000);
	Current = DLL_GetNodeAt(List, 2);
	DLL_InsertAfter(Current, NewNode);

	/* 리스트 출력 */
	Count = DLL_GetNodeCount(List);
	for (int i = 0; i < Count; ++i) {
		Current = DLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	/* 모든 노드를 메모리에서 제거 */
	printf("\nDestroying List...\n");
	Count = DLL_GetNodeCount(List);

	for (int i = 0; i < Count; ++i) {
		Current = DLL_GetNodeAt(List, 0);

		if (Current != NULL) {
			DLL_RemoveNode(&List, Current);
			DLL_DestroyNode(Current);
		}
	}

	return 0;
}

 

환형 더블 링크드 리스트

#pragma once
#ifndef CIRCULAR_DOUBLE_LINKEDLIST_H
#define CIRCULAR_DOUBLE_LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;
	struct tagNode* PrevNode;
	struct tagNode* NextNode;
} Node;


/* 함수 원형 선언 */
Node* CDLL_CreateNode(ElementType NewData);
void CDLL_DestroyNode(Node* Node);
void CDLL_AppendNode(Node** Head, Node* NewNode);
void CDLL_InsertAfter(Node* Current, Node* NewNode);
void CDLL_RemoveNode(Node** Head, Node* Remove);
Node* CDLL_GetNodeAt(Node* Head, int Location);
int CDLL_GetNodeCount(Node* Head);

#endif

#include "CircularDoubleLinkedList.h"

Node* CDLL_CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	if (NewNode != NULL) { // malloc 함수가 동적할당에 실패하였을 경우 예외처리
		NewNode->Data = NewData;
		NewNode->PrevNode = NULL;
		NewNode->NextNode = NULL;
	}

	return NewNode;
}

void CDLL_DestroyNode(Node* Node) {
	free(Node);
}

void CDLL_AppendNode(Node** Head, Node* NewNode) {
	/* 헤드 노드가 NULL 이라면 새로운 노드가 Head */
	if ((*Head) == NULL) {
		*Head = NewNode;
		(*Head)->NextNode = *Head;
		(*Head)->PrevNode = *Head;
	}
	else {
		/* 테일과 헤드 사이에 NewNode를 삽입한다. */
		Node* Tail = (*Head)->PrevNode;

		Tail->NextNode->PrevNode = NewNode;
		Tail->NextNode = NewNode;

		NewNode->NextNode = (*Head);
		NewNode->PrevNode = Tail;
	}
		
}

void CDLL_InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	Current->NextNode->PrevNode = NewNode;
	Current->NextNode = NewNode;
}

void CDLL_RemoveNode(Node** Head, Node* Remove) {
	if ((*Head) == Remove) {
		(*Head)->NextNode->PrevNode = Remove->PrevNode;
		(*Head)->PrevNode->NextNode = Remove->NextNode;

		*Head = Remove->NextNode;

		Remove->NextNode = NULL;
		Remove->PrevNode = NULL;
	}
}

/* 노드 탐색 */
Node* CDLL_GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

int CDLL_GetNodeCount(Node* Head) {
	unsigned int Count = 0;
	Node* Current = Head;

	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;

		if (Current == Head)
			break;
	}

	return Count;
}



int main() {
	int i = 0;
	int Count = 0;
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	/* 노드 5개 추가 */
	for (i = 0; i < 5; ++i) {
		NewNode = CDLL_CreateNode(i);
		CDLL_AppendNode(&List, NewNode);
	}

	/* 리스트 출력 */
	Count = CDLL_GetNodeCount(List);
	for (i = 0; i < Count; ++i) {
		Current = CDLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	/* 리스트의 세 번째 칸 뒤에 노드 삽입 */
	printf("\nInserting 3000 After [2]...\n\n");

	Current = CDLL_GetNodeAt(List, 2);
	NewNode = CDLL_CreateNode(3000);
	CDLL_InsertAfter(Current, NewNode);

	/* 리스트 출력 */
	Count = CDLL_GetNodeCount(List);
	for (i = 0; i < Count * 2; ++i) {
		if (i == 0)
			Current = List;
		else
			Current = Current->NextNode;

		printf("List[%d] : %d\n", i, Current->Data);
	}

	/* 모든 노드를 메모리에서 제거 */
	printf("\nDestroying List...\n");

	Count = CDLL_GetNodeCount(List);

	for (i = 0; i < Count; ++i) {
		Current = CDLL_GetNodeAt(List, 0);

		if (Current != NULL) {
			CDLL_RemoveNode(&List, Current);
			CDLL_DestroyNode(Current);
		}
	}

	return 0;
}

Reference

뇌를 자극하는 알고리즘 1장. 리스트