[Data Structure] 연결 리스트 (Linked list)

[연결 리스트] 

노드라는 구조체로 이루어진 선형자료구조이다.

노드마다 다음 노드의 주소를 가리키고 있는 포인터변수가 존재한다.

메모리 공간상에서 연속적으로 존재하지 않고, 논리적으로만 연속적으로 존재한다.

 

 

 

[배열과의 차이점]

배열(array)와 리스트의 차이점은 메모리 공간을 차지하는 형태이다.

배열은 메모리 공간을 연속적으로 차지 하지만,

연결리스트는 연속적인 메모리 공간을 차지 하지 않는다.

따라서 연결리스트는 순회하는 연산은 시간이 오래걸리지만, 삽입,삭제의 연산이 빠르다.

 

 

[c언어 포인터를 사용한 단일 연결리스트 구현]

 

메모리 동적할당은 ->https://0802ojw.tistory.com/22 참조

구조체는 아직 x ->

포인터  ->

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


// 노드를 구조체로 정의 한다
typedef struct node {
	int data;
	node* next; //node라는 구조체를 가리키는 포인터 변수 선언
} node;


// 맨앞에 노드 삽입하는 함수
node* insertFront(node* head, int value) {
	node* p = (node*)malloc(sizeof(node)); // 메모리 동적할당
	p->data = value; 
	p->next = head;
	head = p;
	return head;
}

// 맨앞의 노드 제거하는 함수 
node* deleteFront(node* head) {
	node* removed;
	if (head == NULL)return NULL;
	removed = head;
	head = removed->next;
	free(removed);
	return head;
}

// 중간에 새로운 노드 삽입
node* Insert(node* head, node* pre, int value) {
	node* p = (node*)malloc(sizeof(node));
	p->data = value;
	p->next = pre->next;
	pre->next = p;
	return(head);
}

// 중간에 있는 노드 삭제
node* Delete(node* head, node* pre) {
	node* removed;
	removed = pre->next;
	pre->next = removed->next;
	free(removed);
	return head;
}


// 연결리스트 출력
void Display(node* head) {
	for (node* p = head; p != NULL; p = p->next) {
		printf("[%d|data:%d,next:%d] -->", p, p->data, p->next);
	}
	printf("NULL \n");
}


// 메인함수 (테스트)
int main(void)
{
	node* head = NULL;

	for (int i = 0; i < 5; i++) {
		head = insertFront(head, i);
		Display(head);
	}
	for (int i = 0; i < 5; i++) {
		head = deleteFront(head);
		Display(head);
	}
	return 0;
}

 

 

[출력 결과]

 

 

[노드의 삽입과 삭제 원리]

 

 

 

 

포인터라는 주소를 가리키는 화살표(변수)를 

내가 원하는 곳을 가리키게 조작하고 

필요하면 할당된 메모리를 삭제하는 과정이다.