๊ฐœ์ธ ๊ณต๋ถ€ ๊ณผ์ •์„ ๊ธฐ๋กํ•ฉ๋‹ˆ๋‹ค.

๐Ÿš€ What I Will Learn

  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ํ•„์š”์„ฑ๊ณผ ์‚ฌ์šฉ์— ๋Œ€ํ•ด ํ•™์Šตํ•œ๋‹ค
  • C์–ธ์–ด๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ตฌํ˜„ํ•ด๋ณธ๋‹คโ€ฆ



์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)

1๏ธโƒฃ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ํ•„์š”์„ฑ

  1. ์ผ๋ฐ˜์ ์œผ๋กœ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฐ์ดํ„ฐ๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ์ €์žฅํ•˜๊ณ , ๋‚˜์—ดํ•  ์ˆ˜ ์žˆ์ง€๋งŒ
  2. ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ, ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์ด ๋ถˆํ•„์š”ํ•˜๊ฒŒ ๋‚ญ๋น„๋  ์ˆ˜ ์žˆ๋“œ๋ฏ€๋กœ
  3. ์ด๋•Œ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋กœ ๋Œ€์ฒดํ•  ์ˆ˜ ์žˆ๋‹ค


โœ”๏ธ ๋ฐฐ์—ด ๊ธฐ๋ฐ˜ ๋ฆฌ์ŠคํŠธ๋ž€?

  1. ๋ฐ์ดํ„ฐ๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ์ €์žฅ, ์ฒ˜๋ฆฌํ•  ๋•Œ๋Š” ๋ฐฐ์—ด ๊ธฐ๋ฐ˜์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉ


#include <stdio.h>
#define INF 10000

int arr[INF];

int count = 0;
void addBack(int data) {
	arr[count] = data;
	count++;
}

void addFirst(int data) {
	for (int i = count; i >= 1; i--) {
		arr[i] = arr[i - 1];
	}
	arr[0] = data;
	count++;
}

void show() {
for (int i = 0; i < count; i++) {
    printf("%d ", arr[i]);
  }
}

int main(void) {
	addFirst(4);
    	addFirst(5);
        addFirst(1);
        addBack(7);
        addBack(6);
        addBack(8);
        show();
        system("pause");
        return 0;
}

๊ทธ๋ ‡๋‹ค๋ฉด?! ํŠน์ •ํ•œ ์œ„์น˜์˜ ์›์†Œ๋ฅผ ์‚ญ์ œํ•˜๋Š” ํ•จ์ˆ˜๋Š” ์–ด๋–ป๊ฒŒ ๋งŒ๋“ค ์ˆ˜ ์žˆ์„๊นŒ?

// ํŠน์ •ํ•œ index๋ฅผ ๋ฐ›์•„์„œ ํ•ด๋‹น index ์œ„์น˜์˜ ๋’ท ์›์†Œ๋ฅผ ์•ž์œผ๋กœ ๋‹น๊ธฐ๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„
void removeAt(int index) {
	for (int i = index; i < count - 1; i++) {
		arr[i] = arr[i + 1];
	}
	count--;
}

โœ”๏ธ ๋ฐฐ์—ด ๊ธฐ๋ฐ˜ ๋ฆฌ์ŠคํŠธ์˜ ํŠน์ง•

  • ๋ฐฐ์—ด๋กœ ๋งŒ๋“ค์—ˆ์œผ๋ฏ€๋กœ ํŠน์ •ํ•œ ์œ„์น˜์˜ ์›์†Œ์— ์ฆ‰์‹œ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์žฅ์ 
    • index๋ฅผ ํ™œ์šฉ
  • ๋ฐ์ดํ„ฐ๊ฐ€ ๋“ค์–ด๊ฐˆ ๊ณต๊ฐ„์„ ๋ฏธ๋ฆฌ ๋ฉ”๋ชจ๋ฆฌ์— ํ• ๋‹นํ•œ๋‹ค๋Š” ๋‹จ์ 
    • #define INF 10000
  • ์›ํ•˜๋Š” ์œ„์น˜๋กœ์˜ ์‚ฝ์ž… ๋˜๋Š” ์‚ญ์ œ๊ฐ€ ๋น„ํšจ์œจ์ 
    • for๋ฌธ์œผ๋กœ ์•ž์œผ๋กœ ๋‹น๊ธฐ๊ฑฐ๋‚˜ ๋’ค๋กœ ๋ฐ€์–ด์„œ ์ถ”๊ฐ€ ๋˜๋Š” ์‚ญ์ œํ–ˆ๋˜ ์œ„์˜ ์ฝ”๋“œ




2๏ธโƒฃ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ

  • ์ผ๋ฐ˜์ ์œผ๋กœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๊ตฌ์กฐ์ฒด์™€ ํฌ์ธํ„ฐ๋ฅผ ํ•จ๊ป˜ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ˜„
  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฆฌ์ŠคํŠธ์˜ ์ค‘๊ฐ„ ์ง€์ ์— ๋…ธ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•จ
  • ํ•„์š”ํ•  ๋•Œ ๋งˆ๋‹ค ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ํ• ๋‹น ๋ฐ›๋Š”๋‹ค

๐Ÿ“Œ ์ฐธ๊ณ !


โœ”๏ธ ๋‹จ์ผ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ

  • ๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐ์ดํ„ฐdata์™€ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” next ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค
  • ํฌ์ธํ„ฐ๋ฅผ ์ด์šฉํ•ด ๋‹จ๋ฐฉํ–ฅ์ ์œผ๋กœ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚จ๋‹ค
  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ํ—ค๋“œ(Head)๋ผ๊ณ  ํ•˜๋ฉฐ ๋ณ„๋„๋กœ ๊ด€๋ฆฌํ•œ๋‹ค
  • ๋‹ค์Œ ๋…ธ๋“œ๊ฐ€ ์—†๋Š” ๋ ๋…ธ๋“œ์˜ ๋‹ค์Œ ์œ„์น˜ ๊ฐ’์œผ๋กœ **NULL**์„ ์ถ”๊ฐ€ํ•œ๋‹ค


โœ”๏ธ ๋‹จ์ผ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ ๊ตฌํ˜„

1) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ตฌ์กฐ์ฒด ๋งŒ๋“ค๊ธฐ

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

typedef struct {
  int data;
  struct Node *next;  // ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ณ€์ˆ˜. ํฌ์ธํ„ฐ ๋ณ€์ˆ˜
} Node;

Node *head;  // ํฌ์ธํ„ฐ ๋ณ€์ˆ˜๋ฅผ ํ™œ์šฉํ•ด ๋™์  ํ• ๋‹น์ด ์ด๋ฃจ์–ด์ง€๋„๋ก ํ•œ๋‹ค


2) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๊ตฌ์กฐ์ฒด ์‚ฌ์šฉํ•ด๋ณด๊ธฐ

  • malloc() ํ•จ์ˆ˜๋กœ ๋™์  ํ• ๋‹นํ•˜๊ธฐ
int main(void) {
  head = (Node*) malloc(sizeof(Node));
  Node *node1 = (Node*) malloc(sizeof(Node));
  node1->data = 1;
  Node *node2 = (Node*) malloc(sizeof(Node));
  node2->data = 2;
  head->next = node1;
  node1->next = node2;
  node2->next = NULL;
  Node *cur = head->next;

  while (cur != NULL) {
  	printf("%d ", cur->data);
  	cur = cur->next;
  }

  system("pause");
  return 0;
}
  • ๊ฒฐ๊ณผ๋Š” 1, 2๊ฐ€ ์ถœ๋ ฅ๋˜๋ฉฐ ์•„๋ž˜์˜ ๊ทธ๋ฆผ์˜ ๋ชจ์–‘์ด ์™„์„ฑ


3) ๋…ธ๋“œ ์‚ฝ์ž…

  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‚ฝ์ž… ํ•จ์ˆ˜ ๊ตฌํ˜„
void addFront(Node *root, int data) {
	Node *node = (Node*) malloc(sizeof(Node));
    	node->data = data;
	node->next = root->next;
	root->next = node;
}


4) ๋…ธ๋“œ ์‚ญ์ œ

  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‚ญ์ œ ํ•จ์ˆ˜ ๊ตฌํ˜„
void removeFront(Node *root) {
  Node *front = root->next;
  root->next = front->next;
  free(front);
}


5) ํ• ๋‹น๋œ ๋ฉ”๋ชจ๋ฆฌ ํ•ด์ œ

  • free() ํ•จ์ˆ˜๋กœ ๋…ธ๋“œ๋ฅผ ํ•˜๋‚˜์”ฉ ์ ‘๊ทผํ•ด์„œ ํ•ด์ œํ•ด์•ผ ํ•จ
void freeAll(Node *root) {
	Node *cur = head->next;
	while (cur != NULL) {
	    Node *next = cur->next;
            free(cur);
            cur = next;
	}
}


6) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์ „์ฒด ์ถœ๋ ฅ ํ•จ์ˆ˜

void showAll(Node *root) {
	Node *cur = head->next;

	while (cur != NULL) {
 	    printf("%d ", cur->data);
	    cur = cur->next;
	}
}


7) ์™„์„ฑ๋œ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์‚ฌ์šฉํ•˜๊ธฐ

int main(void) {
	head = (Node*) malloc(sizeof(Node));
    	head->next = NULL;
	addFront(head, 2);
	addFront(head, 1);
	addFront(head, 7);
	addFront(head, 9);
	addFront(head, 8);
	removeFront(head);
	showAll(head);
	freeAll(head);

	system("pause");
	return 0;
}


โœ”๏ธ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ํŠน์ง•

  • ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ๋ฐฐ์—ด์— ๋น„ํ•ด ๊ฐ„๋‹จํ•˜๋‹ค๋Š” ์žฅ์ 
  • ๋ฐฐ์—ด๊ณผ ๋‹ค๋ฅด๊ฒŒ ํŠน์ • ์ธ๋ฑ์Šค๋กœ ์ฆ‰์‹œ ์ ‘๊ทผํ•˜์ง€ ๋ชปํ•˜๊ณ , ์›์†Œ๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ๊ฒ€์ƒ‰ํ•ด์•ผ ํ•œ๋‹ค๋Š” ๋‹จ์ 
  • ์ถ”๊ฐ€์ ์ธ ํฌ์ธํ„ฐ ๋ณ€์ˆ˜๊ฐ€ ์‚ฌ์šฉ๋˜๋ฏ€๋กœ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์ด ๋‚ญ๋น„๋œ๋‹คโ€ฆ..




โœจ tl;dr

  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์„ ํ˜•์ ์œผ๋กœ ์ €์žฅํ•˜๊ณ  ์ฒ˜๋ฆฌํ•˜๋Š” ํ•œ ๋ฐฉ๋ฒ•์ด๋‹ค
  • ๊ธฐ์กด์— ๋ฐฐ์—ด์„ ์ด์šฉํ–ˆ์„ ๋•Œ ๋ณด๋‹ค ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ๋งŽ์€ ๊ฒฝ์šฐ์— ํšจ์œจ์ ์ด๋‹ค
  • ๋‹ค๋งŒ, ํŠน์ • ์ธ๋ฑ์Šค์— ๋ฐ”๋กœ ์ฐธ์กฐํ•ด์•ผ ํ•  ๋•Œ๊ฐ€ ๋งŽ๋‹ค๋ฉด ๋ฐฐ์—ด์„ ์ด์šฉํ•˜๋Š” ๊ฒƒ์ด ํšจ์œจ์ ์ด๋‹คโ€ฆ.