[C언어] 연결리스트(링크드리스트) 자료구조 구현

포인터 개념 확립하기

#include <stdio.h>

void add(int *a) {
	*a = *a + 10;
}

void main(void) {
	int a = 0;
	add(&a);
	printf("답은 %d 이다.", a);
};

 

 

#include <stdio.h>
#include <malloc.h>

void change_value(int *p, int *q) {
	*p = 5;
	*q = 10;

	printf("%d %d\n", * p, *q);
}



void main(void) {
	
	int* a;
	int* b;

	a = malloc(sizeof(int));
	b = malloc(sizeof(int));

	*a = 3;
	*b = 7;

	printf("%d %d\n", *a, *b);

	change_value(a, b);


};

3 7
5 10

 

Swap함수

#include <stdio.h>
#include <malloc.h>

void swap(int * x, int * y) {
	int* temp;
	temp = x;
	x = y;
	x = temp;

}



void main(void) {
	
	int* a = 10, *b = 20;

	swap(&a, &b);

	printf("a = %d\nb = %d", a, b);

};

여기서 주목해서 봐야할 부분은 메인함수에서 선언된 a, b변수의 값이 변하지 않았다는 것이다.

함수가 돌아간 순간에만 임시적으로 변수가 변하였을 뿐, 실제 데이터는 변하지 않았다.

 

 

배열의 값을 더하기 함수

#include <stdio.h>

int total_value(int arr[], int n) {

	int i, total = 0;

	for (i = 0; i < n; i++) {
		total = total + arr[i];

		
	}
	return total;
}



void main(void) {
	
	int a[5] = { 2,3,4,3,5 };

	int total = total_value(a, sizeof(a) / sizeof(int));
	
	printf("%d", total);
};

 

 

리스트 초기화

#include <stdio.h>

typedef struct Node
{
	char item; // 노드 데이터
	struct Node* next; // 링크

}nodeType;

void initList(nodeType* headPtr) {
	headPtr = NULL;
}

int isEmpty(nodeType* headPtr) {
	if (headPtr == NULL)
		return 1;
	else return 0;
}

 

 

리스트 크기 및 검색

int getCurrentSize(nodeType* headPtr) {
	nodeType* p;
	int count = 0;

	for (p = headPtr; p != NULL; p->next) { // head포인터에서 시작해서 널값까지, 넥스트 링크로 지속
		count++;
	} return count;
}
char contains(nodeType* headPtr, int pos) {
	nodeType* p = headPtr; // 임시 포인터
	int i;

	for (i = 0; i < pos; p->next) {
		if (p == NULL) return 0;

		return p->item;
	}

 

 

리스트 노드 삽입

void insertNext(nodeType *prevNode, nodeType* newNode) {
	if (newNode != NULL) { // newNode가 값을 가진다면,
		newNode->next = prevNode->next;// 새로운 노드는 이전 노드가 가리키던 노드를 가리키고
		prevNode->next = newNode;// 이전 노드가 가리키던 링크는 새로운 노드를 가리킨다.
	}
	

}

 

 

리스트 노드 삭제

nodeType* removeNext(nodeType* prevNode) {
	nodeType* removed = prevNode->next;
	
	if (removed != NULL) {
		prevNode->next = removed->next;
	}
	
	return removed;
	
}

 아직 메모리 상 값은 남아있다고 볼 수 있다.

 

 

 

리스트 노드출력

void printList(nodeType* headPtr) {
	nodeType* ptr = headPtr;

	for (ptr = headPtr; ptr != NULL; ptr=ptr->next) {
		printf("[%d] ", ptr->item);
	}
	printf("\n");
}

 

 

 

실습 

#include <stdio.h>

typedef struct Node
{
	char item; // 노드 데이터
	struct Node* next; // 링크

}nodeType;

void initList(nodeType* headPtr) {
	headPtr = NULL;
}

int isEmpty(nodeType* headPtr) {
	if (headPtr == NULL)
		return 1;
	else return 0;
}

int getCurrentSize(nodeType* headPtr) {
	nodeType* p;
	int count = 0;

	for (p = headPtr; p != NULL; p->next) { // head포인터에서 시작해서 널값까지, 넥스트 링크로 지속
		count++;
	} return count;
}
char contains(nodeType* headPtr, int pos) {
	nodeType* p = headPtr; // 임시 포인터
	int i;

	for (i = 0; i < pos; p->next) {
		if (p == NULL) return 0;

		return p->item;
	}
}

void insertNext(nodeType *prevNode, nodeType *newNode) {
	if (newNode != NULL) { // newNode가 값을 가진다면,
		newNode->next = prevNode->next;// 새로운 노드는 이전 노드가 가리키던 노드를 가리키고
		prevNode->next = newNode;// 이전 노드가 가리키던 링크는 새로운 노드를 가리킨다.
	}
	

}

nodeType* removeNext(nodeType* prevNode) {
	nodeType* removed = prevNode->next;
	
	if (removed != NULL) {
		prevNode->next = removed->next;
	}
	
	return removed;
	
}

void printList(nodeType* headPtr) {
	nodeType* ptr = headPtr;

	for (ptr = headPtr; ptr != NULL; ptr=ptr->next) {
		printf("[%c] ", ptr->item);
	}
	printf("\n");
}

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


void main() {
	
	nodeType *head, *temp;

	temp = (nodeType*)malloc(sizeof(nodeType));
	temp->item = 'A';
	temp->next = NULL;
	head = temp;


	temp = (nodeType*)malloc(sizeof(nodeType));
	temp->item = 'B';
	temp->next = NULL;
	insertNext(head, temp);

	temp = (nodeType*)malloc(sizeof(nodeType));
	temp->item = 'C';
	temp->next = NULL;
	insertNext(head, temp);

	printf("리스트의 내용을 출력합니다.\n");
	printList(head);
}

리스트의 내용을 출력합니다.
[A] [C] [B]

 

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


void main() {
	
	nodeType *head, *temp;

	temp = (nodeType*)malloc(sizeof(nodeType));
	temp->item = 'A';
	temp->next = NULL;
	head = temp;


	temp = (nodeType*)malloc(sizeof(nodeType));
	temp->item = 'B';
	temp->next = NULL;
	insertNext(head, temp);

	temp = (nodeType*)malloc(sizeof(nodeType));
	temp->item = 'C';
	temp->next = NULL;
	insertNext(head, temp);

	removeNext(head);

	printf("리스트의 내용을 출력합니다.\n");
	printList(head);




}

리스트의 내용을 출력합니다.
[A] [B]