[자료구조] 단순 연결 리스트

▶순차 자료구조의 문제점

1. 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요

2. 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고있는 메모리 사용의 비효율성 문제를 그대로 가짐

 

 

 

▶연결 자료구조

• 자료의 논리적인 순서와 물리적인 순서가 불일치함
  • 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.
• 여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현
  • 크기 변경이 유연하고 더 효율적으로 메모리를 사용

 

 

▶연결리스트란?

• 연속된 노드의 연결제
• 노드란? 연결리스트에서 사용되는 하나의 데이터 덩어리(데이터, 링크를 가지고있음)

 

 

 

▶순차 자료구조와 연결 자료구조의 비교

순차자료구조

• 필요한 전체 메모리 크기를 계산하여 할당하고, 할당 된 메모리의 시작위치부터 빈자리 없이 자료를 순서대로 연속하여 저장
• 삽입,삭제 연산 후에도 빈자리 없이 자료가 순서대로 연속 저장되어, 변경된 논리적인 순서와 저장된 물리적인 순서가 일치한다.
• 배열을 이용해서 구현한다.

연결 자료구조

• 노드 단위로 메모리가 할당되며, 저장 위치의 순서와 상관 없이 노드의 링크 필드에 다음 자료의 주소를 저장한다.
• 삽입, 삭제연산 후 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적 위치는 변경되지 않는다.
• 포인터를 시용해서 구현한다.

 

 

▶구현해야하는 함수

createNode() : 노드 생성

prependNode() : 맨 앞에 삽입

appendNode() : 맨 뒤에 삽입

insertNodeAtIndex() : 인덱스 기준 삽입

deleteFrontNode() : 맨 앞 노드 삭제

deleteLastNode() : 맨 뒤 노드 삭제

deleteNodeWithValue() : 값 기준 노드 삭제

serach() : 노드 탐색

countNodes() : 노드 갯수 구하기

printList() : 리스트 출력

freeList() : 메모리 해제

 

 

 

 

▶C로 구현

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

typedef struct Node {
	int data;
	struct Node* next;
} Node;

//노드 생성
Node* createNode(int data) {
	Node* newNode = (Node*)malloc(sizeof(Node)); //newNode 동적할당
	newNode->data =data;
	newNode->next = NULL;
	return newNode; 
} 

//맨 앞에 삽입
void prependNode(Node** head, int data) {
	Node* newNode = createNode(data);
	newNode->next = *head; //newNode의 next를 head로 변경
	*head = newNode; //head를 newNode로 변경 
} 

//맨 뒤에 삽입
void appendNode(Node** head, int data) {
	Node* newNode = createNode(data);
	if(*head == NULL) { //리스트가 비어있다면, 
		*head = newNode; //newNode가 헤드 
		return;
	}
	Node* lastNode = *head;
	while(lastNode->next != NULL) {
		lastNode = lastNode->next;
	}
	lastNode->next = newNode; //newNode를 마지막 노드의 next에 저장 
} 

//중간에 삽입(인덱스 기준)
void insertNodeAtIndex(Node** head, int data, int index) {
	if (index == 0) {//맨 앞에 삽입하는 경우
		prependNode(head, data); 
		return ; 
	}
	Node* newNode = createNode(data);
	Node* temp = *head;
	for(int i = 0; i< index - 1 && temp != NULL; ++i) { //주어진 index의 바로 앞 노드까지 이동
	  temp = temp->next; 
    }  
    if(temp == NULL) { //오류 발생 시 
    	printf("Index out of bounds.\n");
    	free(newNode);
    	return;
	}
	newNode->next = temp->next; //temp의 next포인터를 newNOde의 다음 노드로 설정 
	temp->next = newNode; //temp의 next 포인터를 새노드로 변경하여 연결 
}

//맨 앞의 노드 삭제
void deleteFrontNode(Node** head) {
	if(*head == NULL) return;
	Node* temp = *head; //삭제할 노드 보관하는 임시주소
	*head = (*head)->next; //헤드 이동
	free(temp); //노드 제거 
} 

//맨 뒤의 노드 삭제
void deleteLastNode(Node** head) {
	if(*head == NULL) return; //비었을 때
	if((*head)->next == NULL) { // 노드가 하나일 때
		free(*head);
		*head = NULL;
		return; 
	} 
	Node* secondLast = *head;
	while(secondLast->next->next != NULL) { //[:-1]값 찾기([:-1]의 next의 next가 NULL : 마지막)
		secondLast = secondLast->next; 
	}
	free(secondLast->next); 
	secondLast->next = NULL; //NULL로 변경 
} 

// 중간의 노드 삭제(값 기준)
void deleteNodeWithValue(Node** head, int value) {
	if(*head == NULL) return; //비었을 때
	if((*head)->data == value) { //삭제할 값이 첫번째(head)와 동일할 때 
		Node* temp = *head; 
		*head = (*head)->next;
		free(temp);
		return;
	} 	
	Node* temp = *head;
	while(temp->next !=NULL && temp->next->data != value) { //삭제한는 값과 일치하는 노드 앞까지 
		temp = temp->next;
	}
	if(temp->next == NULL) { //못찾은 경우
		printf("Node not found\n");
		return; 
	} 
	Node* toDelete = temp->next; //삭제할 노트를 toDelete 포인터에 저장 
	temp->next = temp->next->next; //삭제할 노드의 다음 노드를 temp의 다음 노드로 설정하여 리스트에서 노드를 제거 
	free(toDelete);
} 

//노드 탐색
Node* search(Node* head, int value) {
	Node* temp = head; //방문한 노드 주소를 저장하는 임시 변수(처음)
	while(temp !=  NULL) {
		if(temp->data == value) return temp;
		temp = temp->next;
	} 
	return NULL;
} 

//노드 갯수 구하기 
int countNodes(Node* head) {
	int count = 0;
	Node* temp = head;
	while(temp != NULL){
		count++;
		temp = temp->next;
	}
	return count;
} 

//리스트 출력
void printList(Node* head) {
	Node* temp = head;
	while(temp != NULL) {
		printf("%d -> ", temp->data);
		temp = temp->next;
	}
	printf("NULL\n");
} 

//메모리 해제
void freeList(Node* head) {
	Node* temp;
	while(head != NULL) {
		temp = head;
		head = head->next;
		free(temp);
	}
} 

int main() {
	Node* head = NULL;
	
	//맨 앞에 노드 삽입
	prependNode(&head, 3); 
	prependNode(&head, 2);
	prependNode(&head, 1);
	
	//맨 뒤에 노드 삽입
	appendNode(&head, 4); 
	appendNode(&head, 5);
	
	//중간에 노드 삽입 (3번째 위치에 10 삽입)
	insertNodeAtIndex(&head, 10, 2);
	
	printf("초기 리스트: ");
	printList(head);
	
	//노드 탐색
	Node* found = search(head, 10);
	if(found != NULL) {
		printf("노드 %d 탐색 성공\n", found->data);
	}
	else{
		printf("노드 탐색 실패\n");
	}
	
	//노드 삭제
	deleteFrontNode(&head); //맨 앞 노드 삭제
	deleteLastNode(&head); //맨 뒤 노드 삭제
	deleteNodeWithValue(&head, 10); //값이 10인 노드 삭제
	
	printf("삭제 후 리스트 : ");
	printList(head);
	
	//노드 갯수 구하기
	int count = countNodes(head);
	printf("노드의 총 갯수 : %d\n", count);
	
	//메모리 해제
	freeList(head);
	
	return 0; 
}

위에서부터 보자면

 

typedef struct Node {
	int data;
	struct Node* next;
} Node;

Node 구조체를 만든다. 이 구조체는 2개의 필드를 가지고있고 data에는 데이터 값을 저장, next에는 다음 노드를 가리키는 포인터를 저장한다.

 

//노드 생성
Node* createNode(int data) {
	Node* newNode = (Node*)malloc(sizeof(Node)); //newNode 동적할당
	newNode->data =data;
	newNode->next = NULL;
	return newNode; 
}

노드를 생성하는 createNode함수이다. data를 받아서 newNode의 data에 넣어주고 next에는 NULL값을 넣어준다.

그 후 만들어진 newNode를 반환한다. 

 

//맨 앞에 삽입 
void prependNode(Node** head, int data) {
	Node* newNode = createNode(data);
	newNode->next = *head; //만들어진 노드의 next를 현재 head로 바꿔준다.
	*head = newNode; //기존의 head를 현재 만든 노드로 변경

prependNode는 리스트의 맨 앞에 해당 노드를 삽입하는 함수이다. head는 리스트에서 가장 앞에있는 노드를 의미한다.

우선 createNode로 newNode를 만들어준다. 그 후 newNode의 next에 기존의 첫번째 노드를 넣어주고, head를 새롭게 만든 newNode로 변경한다.

 

//맨 뒤에 삽입 
void appendNode(Node** head, int data) {
	Node* newNode = createNode(data);
	if(*head == NULL) {
		*head = newNode;
		return;
	}
	Noed* lastNode = *head; //lastNode를 리스트의 첫번째 노드로 설정 
	while(lastNode->next != NULL) { //lastNode의 next가 NULL일때까지 반복 , 마지막 노드를 찾는 과정 
		lastNode = lastNode->next; //lastNode를 다음 노드로 이동시키는 코드 
	} //while문이 끝나면 lastNode는 마지막 노드가 된다.
	lastNode->next = newNode;
}

appendNode는 리스트의 맨 뒤에 노드를 삽입한다.

우선 노드를 newNode를 만들고, 만약 리스트의 첫 노드가 NULL이라면 즉 리스트가 비어있다면 head를 새로 만든 노드로 설정해준다.

그게 아니라면 

우선 lastNode라는이름의 노드를 첫번째 노드로 설정해 준 후

lastNode의 next가 NULL일 때 까지 lastNode에 계속 다음 노드를 대입한다. 그러면 next가 NULL인 노드 즉, 마지막 노드가 결국 lastNode가 될것이다.

그 후 lastNode의 next를 newNode 새로만든 노드로 설정해주면 리스트의 맨 뒤에 삽입이 완료된다.

 

//인덱스기준 삽입 
void insertNodeAtIndex(Node** head, int data, int index) {
	//첫번째 인덱스에 삽입하는 경우 
	if(index == 0) {
		prependNode(head, data);
		return;
	} 
	//주어진 인덱스에 삽입하는 경우 
	Node* newNode = createNode(data);
	Node* temp = *head;
	for(int i = 0; i < index - 1 && temp != NULL; ++i) {
		temp = temp->next;
	}
	
	//오류 발생 시 
	if(temp == NULL) {
		printf("error");
		free(newNode);
		return;
	}
	newNode->next = temp->next;
	temp->next = newNode;
}

insertNodeAtIndex는 인덱스를 기준으로 노드를 삽입하는 함수이다.

우선 인덱스가 0 즉 첫번째에 삽입하고 싶으면 앞에서 짠 prependNode함수를 사용하면 된다.

그게아닌 주어진 인덱스에 삽입하고 싶으면 우선 newNode를 만든다. 

그 후 temp라는 노드를 리스트의 첫노드로 설정한다. 그리고for문을 따라 반복하면 temp는 입력한 인덱스의 한칸 전으로 갈 것이다. 그 후 newNode의 넥스트에 temp의 next를 넣어줘서 newNode가 리스트에 이어지게 만든다.

그 후 temp의 next를 newNode로 설정한다,

이렇게 하면 index를 기준으로 노드를 삽입할 수 있다.

for(int i = 0; i < index - 1 && temp !=NULL; ++i) 잘 알아두기!

 

 

//맨 앞 노드 삭제 
void deleteFrontNode(Node** head) {
	if(*head == NULL) return;
	Node* temp = *head
	*head = *head->next;
	free(temp);
}

deleteFrontNode는 맨 앞의 노드를 삭제하는 함수이다.

만약 head가 즉 리스트의 첫 노드가 없다면 그냥 그 리스트를 리턴해주고

아니라면 temp를 리스트의 첫 노드로 설정하고 그 노드를 다음 노드로 변경해준 후

첫 노드로 설정한 temp를 free로 메모리해제를 해준다.

 

//맨 뒤의 노드 삭제
void deleteLastNode(Node** head) {
	if(*head == NULL) return; //비었을 때
	if((*head)->next == NULL) { // 노드가 하나일 때
		free(*head);
		*head = NULL;
		return; 
	} 
	Node* secondLast = *head;
	while(secondLast->next->next != NULL) { //[:-1]값 찾기([:-1]의 next의 next가 NULL : 마지막)
		secondLast = secondLast->next; 
	}
	free(secondLast->next); 
	secondLast->next = NULL; //NULL로 변경 
}

deleteLastNode는 맨 뒤의 노드를 삭제하는 함수이다.

만약 head가 NULL이라면 그 리스트를 그대로 반환해주고

만약 head의 다음 노드가 없다면 즉 노드가 하나인 리스트라면 그 첫 노드를 메모리 해제해준 후

head를 NULL로 초기화시켜준다.

아니면 secondLast라는 노드를 첫번째 노드로 설정해주고

그 첫번째 노드의 다음 다음 노드가 마지막 노드일 때까지

즉, 뒤에서 두번째인 노드일 때까지 반복시켜준다. 

그 후 그 뒤에서 두번째인 노드의 next노드를 free해준 후

그 free한 노드의 next값을 NULL로 변경해준다.

 

// 중간의 노드 삭제(값 기준)
void deleteNodeWithValue(Node** head, int value) {
	if(*head == NULL) return; //비었을 때
	if((*head)->data == value) { //삭제할 값이 첫번째(head)와 동일할 때 
		Node* temp = *head; 
		*head = (*head)->next;
		free(temp);
		return;
	} 	
	Node* temp = *head;
	while(temp->next !=NULL && temp->next->data != value) { //삭제한는 값과 일치하는 노드 앞까지 
		temp = temp->next;
	}
	if(temp->next == NULL) { //못찾은 경우
		printf("Node not found\n");
		return; 
	} 
	Node* toDelete = temp->next; //삭제할 노트를 toDelete 포인터에 저장 
	temp->next = temp->next->next; //삭제할 노드의 다음 노드를 temp의 다음 노드로 설정하여 리스트에서 노드를 제거 
	free(toDelete);
}

deleteNodeWithValue함수는 값 기준으로 노드를 삭제하는 함수이다.

만약 리스트가 비었으면 그 리스트를 반환해주고

만약 첫번째 노드의 data값이 삭제한 value값과 같다면 temp라는 노드에 head를 담고

head를 다음 노드로 설정해준 뒤 temp를 free해주면 된다.

그게 아니라면 그냥 temp에 head를 넣어주고

while(temp->next !=NULL && temp->next->data != value)

temp의 다음 노드가 NULL이 아니고 노드의 data가 value가 아닌게 참이면 

즉 temp의 다음 노드가 NULL이거나, 그 노드의 data는 value일 때 멈춘다. 그때까지 temp를 이동시킨다.

만약 temp의 다음이 NULL이면 찾지 못한경우이니 printf를 통해 찾지 못했다고 말해준 후

찾았다면 toDelete 노드를 temp의 다음 노드로 지정해주고

temp의 다음 다음을 temp의 next로 지정해준다.

그 후 toDelete의 메모리를 해제해준다.

 

//노드 탐색
Node* search(Node* head, int value) {
	Node* temp = head; //방문한 노드 주소를 저장하는 임시 변수(처음)
	while(temp !=  NULL) {
		if(temp->data == value) return temp;
		temp = temp->next;
	} 
	return NULL;
}

search는 노드를 탐색해주는 함수이다. 

우선 temp에 리스트의 첫번째 위치를 넣어준다.

그 후 temp가 NULL이 아니면 아래 if문을 돌려준다. 즉 temp가 NULL이면 멈춤다는 건데 temp가 NULL이라는것은 리스트의 끝이라는이야기이다.

아무튼 리스트의 끝까지 갈 때까지 만약 temp의 data가 넣어준 value값이랑 같다면 그 temp를 반환해 준다.

그게 아니면 temp를 다음 노드로 이동시킨다.

만약 리스트를 다 순회했는데 찾지 못했다면 NULL을 반환해준다.

 

//노드 갯수 구하기 
int countNodes(Node* head) {
	int count = 0;
	Node* temp = head;
	while(temp != NULL){
		count++;
		temp = temp->next;
	}
	return count;
}

countNodes는 노드 갯수를 구해서 반환해주는 함수이다.

temp를 리스트의 첫번째 노드로 설정하고 리스트를 한바퀴 돈다.

노드가 이동될 때 마다 count를 1씩 증가시키고 temp를 다음 노드로 이동시킨다.

그 후 count를 반환해주면 된다.

 

//리스트 출력
void printList(Node* head) {
	Node* temp = head;
	while(temp != NULL) {
		printf("%d -> ", temp->data);
		temp = temp->next;
	}
	printf("NULL\n");
}

printList는 리스트를 출력해주는 함수이다.

우선 temp를 리스트의 첫번째 노드로 설정해주고 리스트를 한바퀴 돈다.

한바퀴를 돌면서 temp의 data값을 하나씩 출력해준 후 temp를 다음 노드로 이동시킨다.

그 후 리스트를 다 돌았다면 NULL을 출력해서 리스트가 끝났음을 알려준다.

 

//메모리 해제
void freeList(Node* head) {
	Node* temp;
	while(head != NULL) {
		temp = head;
		head = head->next;
		free(temp);
	}
}

freeList는 메모리를 해제해주는 함수이다.

temp를 만들어주고

head가 NULL이면 끝난다 즉 끝까지 순회한다.

temp를 head로 두고 head는 계속 다음 노드로 이동한다.

그 후 temp를 메모리해제해주면 모든 노드가 메모리가 해제된다.

 

int main() {
	Node* head = NULL;
	
	//맨 앞에 노드 삽입
	prependNode(&head, 3); 
	prependNode(&head, 2);
	prependNode(&head, 1);
	
	//맨 뒤에 노드 삽입
	appendNode(&head, 4); 
	appendNode(&head, 5);
	
	//중간에 노드 삽입 (3번째 위치에 10 삽입)
	insertNodeAtIndex(&head, 10, 2);
	
	printf("초기 리스트: ");
	printList(head);
	
	//노드 탐색
	Node* found = search(head, 10);
	if(found != NULL) {
		printf("노드 %d 탐색 성공\n", found->data);
	}
	else{
		printf("노드 탐색 실패\n");
	}
	
	//노드 삭제
	deleteFrontNode(&head); //맨 앞 노드 삭제
	deleteLastNode(&head); //맨 뒤 노드 삭제
	deleteNodeWithValue(&head, 10); //값이 10인 노드 삭제
	
	printf("삭제 후 리스트 : ");
	printList(head);
	
	//노드 갯수 구하기
	int count = countNodes(head);
	printf("노드의 총 갯수 : %d\n", count);
	
	//메모리 해제
	freeList(head);
	
	return 0; 
}

마지막으로 main함수까지 작성해서 실행시켜보면

 

이런 결과가 나오게 된다.