오늘 한 일 

 

환형 링크드 리스트를 다시 보고, 스택을 배열로 짜봤다. 

공부한 내용과 코드를 포스팅으로 정리했다. 

 

 

 

생각거리 

 

나름 깔끔한 포스팅을 위해 카카오 오븐을 이용해 그림을 그렸는데. 귀찮으면서도 재미있었다.

포스팅을 정성껏 해주는 사람들의 정성을 절감했다. 

내일은 SQLD에 더 시간을 들여야지. 

728x90

'일상 > Today I Learn(TIL)' 카테고리의 다른 글

2020-02-21 TIL  (0) 2020.02.21
2020-02-19 TIL  (0) 2020.02.19
2020-02-17 TIL  (0) 2020.02.17
2020-02-16 TIL  (0) 2020.02.16
2020-02-14 TIL  (0) 2020.02.14

스택이란?

 

스택에 10, 20, 30 순서로 숫자를 3개 넣어봅니다. (push 연산)

가장 먼저 들어간 10이 맨 아래에 있게 됩니다. 

 

스택의 push 연산

 

10을 즉시 꺼낼 수 없고, 30 부터 꺼내야 마지막으로 10을 얻을 수 있습니다. (pop 연산)

 

스택의 pop 연산

 

이처럼 '가장 먼저 들어간 요소가 가장 마지막에 나오는 구조 입니다. 

그래서 FILO (First In Last Out) 라고 부릅니다. 

자동메모리가 스택을 기반으로 동작하고, 대부분의 네트워크 프로토콜도 스택을 기반으로 구성되어 있습니다. 

 


 

배열로 구현하는 스택 

 

배열을 이용하면, 동적으로 스택의 길이를 조절할 수 없지만, 구현이 간단합니다. 

사용자가 정한 숫자만큼의 길이를 가진 배열을 만듭니다. 

그리고 최상위 노드의 위치를 알고있는 변수로 삽입과 제거 연산을 합니다. 

 

 

스택의 노드 

 

스택에 들어갈 노드입니다. 

데이터 하나를 담는 노드를 구조체로 표현합니다. 

노드의 위치는 배열의 인덱스로 알 수 있습니다. 

typedef struct Node {
	int data;
}Node;

 

다음은 스택 구조체입니다. 

구조체 ArrayStack에 필요한 필드는 세 가지 입니다. 

배열의 길이
배열
최상위 노드의 위치 

노드가 최대 몇 개 들어갈 수 있는지 배열의 길이를 알아야 합니다. 

그리고 노드를 저장할 '배열'이 필요하고, 최상위 노드의 위치로 삽입/제거 합니다. 

typedef struct ArrayStack {
	int capacity;		/* 배열 용량 */
	int top;	/* 최상위 노드 위치 */
	Node* arrayNodes;	/* 노드들을 보관하는 스택배열 */
}ArrayStack;

노드 배열은 포인터로 선언되어 있습니다. (포인터는 배열로 사용할 수 있습니다)

 

 

 

스택의 생성과 메모리해제 

 

CreateArrayStack() 함수는 배열의 최대길이를 이용하여 스택을 생성합니다.  

/* 스택 생성.  메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
	printf("[ 스택 생성 CreateArrayStack ]\n");

	/* 스택을 자유 저장소에 생성 */
	(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	/* 용량 만큼의 노드들을 자유 저장소에 생성 */
	(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);

	// 필드 초기화 
	(*stack)->capacity = capacity;
	(*stack)->top = 0;
}

 

 

FreeArrayStack() 함수는 노드와 스택을 자유 저장소에서 해제합니다.

void FreeArrayStack(ArrayStack** stack) {
	printf("[ 메모리 해제 FreeArrayStack ]\n");

	free((*stack)->arrayNodes);
	free((*stack));
}

 

 

 

삽입 연산 (PUSH)

 

스택 구조체가 알고있는 top 위치의 노드에 데이터를 넣습니다.

배열 인덱스가 top이 됩니다. 

데이터를 넣고, top위치를 갱신해줍니다. 

void Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;
}

 

 

스택이 꽉 찼을 때를 확인하는 Push 함수 

 

스택이 꽉 찼을 때 push를 안하고 종료하는 코드를 추가해봤습니다. 

 

capacity와 top이 같은지 확인합니다. 

Push의 리턴을 bool로 바꾸고, 삽입이 불가하면 false를 리턴하도록 했습니다. 

 

bool Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	if (stack->capacity == stack->top) {
		printf("[ 용량초과! ] 삽입이 불가합니다. \n");
		return false;
	}

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;

	return true;
}

 

 

삽입/제거 연산을 확인해본 main 함수 코드입니다.

 

 

int main() {

	ArrayStack* stack = NULL;

	CreateArrayStack(&stack, 10);

	// 12번 Push
	for (int i = 10; i <= 120; i+=10) {
		if (!Push(stack, i)) {
			break;
		}
	}

	// 5번 Pop
	for (int i = 0; i < 5; i++) {
		printf("%3d를 제거합니다.\n", Pop(stack));
	}
	
	return 0;
}

 

배열 최대 길이가 10인데, Push 연산을 12번 했을 경우 콘솔 화면 입니다. 

10번 넣고, 11번 넣으려고 할때 용량이 초과되서 for 문을 break 합니다.

이어서 제거 연산을 5번 수행합니다. 

 

 

 

스택용량이 Full 인지 확인하는 함수로 분리하면 더 좋을 것 같습니다. 

 

 

 

제거 연산 (POP)

 

삽입과는 달리, top 값을 1 감소하면 됩니다. 

그리고 top 위치에 있던 data를 호출자에게 반환합니다. 

int Pop(ArrayStack* stack) {
	printf("[ 제거연산 Pop ]\n");

	int location = --(stack->top);

	return stack->arrayNodes[location].data;
}

POP 연산 시, 배열의 인덱스를 주의해야 합니다. 

왜냐하면 top이 1이라면, 노드가 위치하는 실제 인덱스는 0이기 때문입니다. 

 

 

 

스택이 비었는지 확인  : Pop 전에 확인 

 

/* 스택이 비었는지 확인 : 제거 전에 확인  */
int isEmpty(ArrayStack* stack) {
	// true 1 반환. false 0 반환 
	return (0 == stack->top);
}

 


 

전체 코드 

 

배열길이는 10을 주고 10부터 100까지 10개의 숫자를 PUSH 합니다. 

12번의 POP을 시도하지만 10번까지만 하고 종료되는 코드입니다. 

 

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


typedef struct Node {
	int data;
}Node;

typedef struct ArrayStack {
	int capacity;		/* 배열 용량 */
	int top;	/* 최상위 노드 위치 */
	Node* arrayNodes;	/* 노드들을 보관하는 스택배열 */
}ArrayStack;


/* 스택 생성.  메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
	printf("[ 스택 생성 CreateArrayStack ]\n");

	/* 스택을 자유 저장소에 생성 */
	(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	/* 용량 만큼의 노드들을 자유 저장소에 생성 */
	(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);

	// 필드 초기화 
	(*stack)->capacity = capacity;
	(*stack)->top = 0;
}

/* 메모리 해제 */
void FreeArrayStack(ArrayStack** stack) {
	printf("[ 메모리 해제 FreeArrayStack ]\n");

	free((*stack)->arrayNodes);
	free((*stack));
}

/* 삽입 Push 연산 */
void Push(ArrayStack* stack, int inputData) {
	printf("[ 삽입연산 Push ] %d를 Push \n", inputData);

	int location = stack->top;

	stack->arrayNodes[location].data = inputData;
	stack->top = location + 1;
}

/* 스택이 비었는지 확인 : 제거 전에 확인  */
int isEmpty(ArrayStack* stack) {
	// true 1 반환. false 0 반환 
	return (0 == stack->top);
}

/* 제거 Pop 연산 */
int Pop(ArrayStack* stack) {
	printf("[ 제거연산 Pop ]\n");

	int location = --(stack->top);

	return stack->arrayNodes[location].data;
}



int main() {

	ArrayStack* stack = NULL;

	CreateArrayStack(&stack, 10);

	// 10개 Push
	for (int i = 10; i <= 100; i+=10) {
		Push(stack, i);

	}

	// 12번을 pop 해본다 
	for (int i = 0; i < 12; i++) {

		if (isEmpty(stack)) {
			printf("스택이 비었습니다. \n");
			break;
		}
		else {
			printf("%3d를 제거합니다.\n", Pop(stack));
		}
	}
	
	return 0;
}

 

콘솔 결과 입니다. 

 

 


다음 포스팅에서는 링크드 리스트로 구현하는 스택을 다루겠습니다.

 

728x90

오늘 한 일 

 

환형 더블 링크드 리스트를 공부하고 코딩했다. 

최호성님의 C언어 강의에서 '스택메모리'를 공부하는 '함수응용' 강의를 들었다. 

 

 

 

생각거리 

 

환형 더블 링크드 리스트. 이름 참 길다.

노드 추가, 삭제만 했는데, 더블 링크드를 두번 짜봐서 그런지 크게 힘들지는 않았다. 

다행이다.

 

내일도 화이팅!! 

 

728x90

'일상 > Today I Learn(TIL)' 카테고리의 다른 글

2020-02-19 TIL  (0) 2020.02.19
2020-02-18 TIL  (0) 2020.02.18
2020-02-16 TIL  (0) 2020.02.16
2020-02-14 TIL  (0) 2020.02.14
2020-02-13 TIL  (0) 2020.02.13

환형 링크드 리스트 

 

환형 링크드 리스트도 더블 링크드 리스트와 비슷합니다. 

유의할 점은 테일의 다음 노드 포인터가 헤드를 가리키게 하면 됩니다. 

이것 빼고는 더블 링크드 리스트와 똑같습니다. 그래서 노드 추가, 삭제만 살펴볼 것입니다. 

 

테일의 다음이 헤드이고, 헤드의 앞이 테일이기 때문에 "뒤"부터 검색할 수도 있습니다!

그래서 탐색과 추가 기능의 성능을 개선할 수 있습니다. 

 

 

환형 더블 링크드 리스트의 주요 연산 

 

유의할 점은 다음 두 가지 입니다. 

 

첫 번째, 테일은 헤드의 '앞 노드'이다. 
두 번째, 헤드는 테일의 '뒷 노드'이다. 

 

 

노드 추가 

 

void AppendNode(Node** head, Node* newNode) {
	printf("[AppendNode] %d를 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { // 헤드가 비었다면 뉴 노드가 헤드
		
		(*head) = newNode;
		(*head)->nextNode = (*head);
		(*head)->prevNode = (*head);

	}
	else { // 테일과 헤드 사이에 뉴노드 삽입 

		// 뉴노드의 다음은 헤드, 뉴노드 이전은 테일 
		newNode->nextNode = (*head);
		newNode->prevNode = (*head)->prevNode;

		// 기존테일의 다음노드가 뉴노드.
		(*head)->prevNode->nextNode = newNode;
		// 뉴노드가 새로운 테일이 된다.
		(*head)->prevNode = newNode;

	}
}

 

 

리스트 출력 (do-while 이용)

 

환형 리스트 이므로, while 조건문에 유의하여 리스트를 출력했습니다. 

void PrintList(Node* list) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* current = list;

	do {
		printf("%3d", current->data);
		current = current->nextNode;
	} while (current->nextNode != list->nextNode);

	printf("\n");
}

 

 

노드 탐색 

 

인덱스를 입력하여 노드의 주소를 리턴합니다. 

Node* GetLocation(Node* head, int location) {
	printf("[GetLocation] %d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((--location) >= 0) {
		//printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;
	}

	return current;
}

 

 

 

노드 삭제 

 

RemoveNode() 함수는 특정 주소에 있는 노드를 삭제합니다. 

 

 

void RemoveNode(Node** head, Node* target) {
	printf("[RemoveNode] %d를 삭제합니다. \n", target->data);

	if ((*head) == target) {
    	// 헤드의 앞뒤 노드의 포인터를 갱신  
		(*head)->prevNode->nextNode = (*head)->nextNode;
		(*head)->nextNode->prevNode = (*head)->prevNode;

		// 헤드를 갱신 
		(*head) = (*head)->nextNode;
	}
	else {
    	// 타겟의 앞뒤 노드의 포인터를 갱신 
		target->prevNode->nextNode = target->nextNode;
		target->nextNode->prevNode = target->prevNode;
	}

	// 타겟 메모리해제 
	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);
}

 


전체 코드 입니다. 

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

// 환형 링크드 리스트  

/* 노드 정의 */
typedef struct Node {
	int data;
	struct Node* prevNode;
	struct Node* nextNode;
}Node;

/* 노드 생성*/
Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->prevNode = NULL;
	newNode->nextNode = NULL;

	return newNode;
}



/* 리스트 출력 */
void PrintList(Node* list) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* current = list;

	do {
		printf("%3d", current->data);
		current = current->nextNode;
	} while (current->nextNode != list->nextNode);

	printf("\n");
}

/* 노드 탐색 */
Node* GetLocation(Node* head, int location) {
	printf("[GetLocation] %d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((--location) >= 0) {
		//printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;
	}

	return current;
}


/* 노드 추가 */
void AppendNode(Node** head, Node* newNode) {
	printf("[AppendNode] %d를 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { // 헤드가 비었다면 뉴 노드가 헤드
		
		(*head) = newNode;
		(*head)->nextNode = (*head);
		(*head)->prevNode = (*head);

	}
	else { // 테일과 헤드 사이에 뉴노드 삽입 

		//Node* tail = (*head)->prevNode;

		// 뉴 노드의 다음은 헤드, 뉴 노드 이전은 테일 
		newNode->nextNode = (*head);
		newNode->prevNode = (*head)->prevNode;

		// 기존테일의 다음노드가 뉴노드.
		(*head)->prevNode->nextNode = newNode;
		// 뉴노드가 새로운 테일이 된다.
		(*head)->prevNode = newNode;
	}
}


/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) {
	printf("[RemoveNode] %d를 삭제합니다. \n", target->data);

	if ((*head) == target) {
		(*head)->prevNode->nextNode = (*head)->nextNode;
		(*head)->nextNode->prevNode = (*head)->prevNode;

		(*head) = (*head)->nextNode;
	}
	else {
		target->prevNode->nextNode = target->nextNode;
		target->nextNode->prevNode = target->prevNode;
	}

	// 타겟 메모리해제 
	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);
}

int main() {
	Node* list = NULL;

	AppendNode(&list, CreateNode(10));
	AppendNode(&list, CreateNode(20));
	AppendNode(&list, CreateNode(30));

	PrintList(list);
	
	// 3번째 노드 삭제(인덱스2)
	RemoveNode(&list, GetLocation(list, 2));
	PrintList(list);

	AppendNode(&list, CreateNode(40));
	PrintList(list);

	// 1번째 노드 삭제(인덱스0)
	RemoveNode(&list, GetLocation(list, 0));
	PrintList(list);

	// 2번째 노드 삭제(인덱스1)
	RemoveNode(&list, GetLocation(list, 1));
	PrintList(list);

	return 0;
}

 

콘솔 결과 입니다. 

728x90

오늘 한 일 

뇌를 자극하는 알고리즘 도서를 보고  '더블 링크드 리스트' 를 공부했다. 

 

 

생각거리

공부한 내용을 정리한 포스팅을 전체공개 하기에는, 저작권 법을 위반하게 되니까. 

배운 내용 중에서 가장 중요한 내용만 나만의 코드로 변형해서 정리해야겠다. 

주의해야지 :)

 

728x90

'일상 > Today I Learn(TIL)' 카테고리의 다른 글

2020-02-18 TIL  (0) 2020.02.18
2020-02-17 TIL  (0) 2020.02.17
2020-02-14 TIL  (0) 2020.02.14
2020-02-13 TIL  (0) 2020.02.13
2020-02-12 TIL  (0) 2020.02.12

 

더블 링크드 리스트란

 

링크드 리스트의 탐색 기능을 개선한 자료구조입니다.

자신의 앞에 있는 노드를 가리키는 포인터도 있어서, 앞으로도 뒤로도 이동할 수 있습니다. 

다음은 더블 링크드 리스트를 표현한 구조체입니다. 

typedef struct Node {
	struct Node* prevNode;
	int Data;
	struct Node* nextNode;
}Node;

 

특별한건 없고 '앞 노드'를 처리하기 위한 포인터만 추가됩니다. 

 

 

노드 생성

 

다음은 노드를 생성하는 CreateNode() 함수 입니다. 

'앞 노드'를 가리키는 prevNode 포인터를 NULL로 초기화 하는것 말고는 싱글 링크드 리스트와 똑같습니다. 

Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
    
	newNode->data = data;
	newNode->prevNode = NULL;
	newNode->nextNode = NULL;

	return newNode;
}

 

 

노드 추가

 

테일을 찾아서 새 노드를 추가합니다. 

새 노드의 prevNode 포인터가 tail 노드를 가리키도록 합니다. 

void AppendNode(Node** head, Node* newNode) {
	
	if (NULL == (*head)) { //헤드 노드가 없다면, 새 노드가 헤드 노드
		(*head) = newNode;
	}
	else {  // 테일 노드를 찾아서, 테일 뒤에 새 노드를 덧붙인다 
		Node* tail = (*head);

		while (NULL != tail->nextNode) {
			tail = tail->nextNode;
		}

		newNode->prevNode = tail;
		tail->nextNode = newNode;

	}
}

헤드 노드가 없으면, 새 노드가 헤드 노드가 됩니다. 

그렇지 않으면, 현재 노드가 테일 노드가 될 때까지 이동하고,

 

테일을 찾아내면,새 노드의 이전이 테일이고, 테일의 다음 노드가 새 노드가 되도록 포인터 변수값을 넣습니다.

 

 

 

 

노드 삭제

 

조금 어려운 부분입니다.

변경 해야 할 노드의 포인터가 4개이기 때문입니다.

 

앞 노드, 삭제할 노드, 뒷 노드  순으로 존재한다고 가정할 때, 

삭제할 노드의 '앞 노드'와 삭제할 노드의 '뒷 노드'의 포인터를 포함하여 총 4개입니다. 

void RemoveNode(Node** head, Node* target) {

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	if ((*head) == target) { // 헤드를 삭제하는 경우, 
		// 헤드를 변경 
		(*head) = target->nextNode;

		if (NULL != (*head)) {
			(*head)->prevNode = NULL;
		}
		// 타겟을 제거 
		target->nextNode = NULL;
		target->prevNode = NULL;
		free(target);
	}
	else { 
		// temp = 타겟
		Node* temp = target;

		// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
		temp->prevNode->nextNode = temp->nextNode;

		if (NULL != temp->nextNode) {
			temp->nextNode->prevNode = temp->prevNode;
		}

		target->nextNode = NULL;
		target->prevNode = NULL;
		free(target);
	}
}

삭제할 노드의 '앞 노드'가 삭제할 노드의 '뒷 노드'를 가리키도록 변경합니다. 

'뒷 노드'의 prevNode* 가 '앞 노드'의 nextNode*를 가리키도록 변경합니다. 

삭제할 노드의 앞뒤 포인터 두 개를 전부 NULL을 가리키도록 변경합니다. 

 

중복을 제거한 다음 코드도 정상 동작합니다. 

void RemoveNode(Node** head, Node* target) {

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	if ((*head) == target) { // 헤드를 삭제하는 경우, 
		// 헤드를 변경 
		(*head) = target->nextNode;

		if (NULL != (*head)) {
			(*head)->prevNode = NULL;
		}
	}
	else { 
		// temp = 타겟
		Node* temp = target;

		// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
		temp->prevNode->nextNode = temp->nextNode;

		if (NULL != temp->nextNode) {
			temp->nextNode->prevNode = temp->prevNode;
		}
	}

	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);

}

 

 

 

 

노드 삽입 

 

기준 노드(current) 뒤에 새 노드(newNode)를 삽입하는 것이므로 새 노드의 포인터만 주의하면 됩니다.

 

새 노드의 뒤 노드는 기준노드의 다음 노드를 가리킵니다.

새 노드의 앞 노드는 기준노드를 가리킵니다.

기준노드의 다음노드의 앞 포인터(current->nextNode->prevNode)와 기준노드의 뒷 포인터(current->nextNode)를 수정합니다. 

void InsertAfter(Node* current, Node* newNode) {

	newNode->prevNode = current;
	newNode->nextNode = current->nextNode;

	if (NULL != current->nextNode) {
		current->nextNode->prevNode = newNode;
	}

	current->nextNode = newNode;
}

 

 

 

전체 코드 입니다. 

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


// 더블 링크드 리스트 

/* 노드 선언 */
typedef struct Node {
	struct Node* prevNode;
	struct Node* nextNode;
	int data;
};


/* 노드 생성 */
Node* CreateNode(int data) {
	
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->prevNode = NULL;
	newNode->nextNode = NULL;

	return newNode;
}

/* [공통] 노드 탐색 */
Node* GetLocation(Node* head, int location) {
	printf("[GetLocation]%d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((NULL != current) && (--location) >= 0) {
		printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;

	}

	return current;
}


/* [공통] 리스트 출력 */
void PrintList(Node* head) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* tempNode = head;
	int count = 0;

	while (NULL != tempNode) {
		printf("%5d", tempNode->data);
		tempNode = tempNode->nextNode;
		count++;
	}
	printf("\n");
	printf("%5d개의 노드가 있습니다.\n", count);
}

/* 노드 추가. 테일 뒤에 새 노드를 덧붙인다 */
void AppendNode(Node** head, Node* newNode) {

	printf("[AppendNode] 데이터 %2d 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { //헤드 노드가 없다면, 새 노드가 헤드 노드
		(*head) = newNode;
	}
	else {  // 테일 노드를 찾아서, 테일 뒤에 새 노드를 덧붙인다 
		Node* tail = (*head);

		while (NULL != tail->nextNode) {
			tail = tail->nextNode;
		}

		newNode->prevNode = tail;
		tail->nextNode = newNode;
	}
}

/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) {

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	if ((*head) == target) { // 헤드를 삭제하는 경우, 
		// 헤드를 변경 
		(*head) = target->nextNode;

		if (NULL != (*head)) {
			(*head)->prevNode = NULL;
		}

	}
	else { 
		// temp = 타겟
		Node* temp = target;

		// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
		temp->prevNode->nextNode = temp->nextNode;

		if (NULL != temp->nextNode) {
			temp->nextNode->prevNode = temp->prevNode;
		}
	}

	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);

}

/* 노드 삽입. 특정 노드 뒤에 새 노드를 삽입한다. */
void InsertAfter(Node* current, Node* newNode) {

	printf("[InsertAfter] %2d를 %d 뒤에 삽입합니다.\n", newNode->data, current->data);

	newNode->prevNode = current;
	newNode->nextNode = current->nextNode;

	if (NULL != current->nextNode) {
		current->nextNode->prevNode = newNode;
	}

	current->nextNode = newNode;
}

int main() {

	Node* list = NULL;

	AppendNode(&list, CreateNode(10));
	AppendNode(&list, CreateNode(20));
	AppendNode(&list, CreateNode(30));

	PrintList(list);

	// 2번째 노드 위치 탐색(인덱스 1)
	// 2번째 노드 삭제 
	RemoveNode(&list, GetLocation(list, 1));

	PrintList(list);

	// 헤드 뒤에 삽입
	InsertAfter(list, CreateNode(40));
	PrintList(list);

	// 3번째 노드(인덱스 2) 뒤에 삽입 
	InsertAfter(GetLocation(list, 2), CreateNode(50));
	PrintList(list);

	return 0;
}

 

콘솔 화면 입니다.

 


다음 포스팅은 '환형 링크드 리스트' 입니다. 

728x90

오늘 한 일 

 

요세퍼스 문제 를 링크드 리스트로 풀었는데, 자꾸 시간초과가 나서 혼자 수렁에 빠졌다. 

흠.. 다음에 큐를 배워서 큐로 풀어야 하나.

링크드 리스트는 조회 빼고 추가/삽입/삭제만 빠르다.

조회를 해야하는 부분이.. 특히 tail을 찾으려면 꼭 head 부터 찾게 하는 코드 때문에 while문 에서 시간을 많이 잡아 먹은 것 같다. 

고쳐야지.

 

'C언어 포인터'책 구조체 부분을 공부했다. 

구조체 멤버변수 중에 문자열을 가리키는 포인터 변수가 있으면, 자주 하게 되는 실수 부분이 기억에 남았다. 

포인터 변수가 가리킬 '문자열의 공간'까지 할당 받아야 한다는 것!

 

 

생각거리 

 

링크드 리스트에 대한 낯설음과 부담감을 떨쳤다. 

내일 공부할 더블 링크드 리스트, 환형 링크드 리스트까지... 화이팅!

seize the day! 

728x90

'일상 > Today I Learn(TIL)' 카테고리의 다른 글

2020-02-17 TIL  (0) 2020.02.17
2020-02-16 TIL  (0) 2020.02.16
2020-02-13 TIL  (0) 2020.02.13
2020-02-12 TIL  (0) 2020.02.12
2020-02-11 TIL  (0) 2020.02.11

+ Recent posts