27 min to read
자료구조(7) - 연결리스트
연결리스트와 양방향 연결리스트의 ADT를 만들고, 구현
🔚 짧게 하는 복습
✅ 1. 정적 배열로 큐와 주어진 ADT를 구현할 수 있다.
✅ 2. 동적 배열로 큐와 주어진 ADT를 구현할 수 있다.
✅ 3. 정적 배열로 환형 큐와 주어진 ADT를 구현할 수 있다.
혹시 기억이 안 난다면, 다시 돌아가자
이번 강의는 마지막 선형 자료구조인 연결 리스트에 대해 다루어보겠다.
이때까지의 선형구조는 정적 배열 혹은 동적 배열, 즉 배열을 기반으로 자료구조를 구현했다.
그런데 연결 리스트는, 구조체와 구조체 포인터를 기반으로 하여, 서로를 가리켜서 마치 배열처럼 구현된 특별한 선형 자료구조이다.
그리고 이 특별한 구조는 트리라는 자료구조로 확장되기 때문에, 꼭 잘 이해해야 한다.
연결 리스트의 구조체는 보통 이렇게 만들어진다.
typedef struct Node* nodePointer;
typedef struct Node {
int data; // 자료 값
nodePointer next; // 다음 노드를 가리키는 포인터
} node; // 노드
저 구조체 한 단위를 노드라고 하고, 한 노드안의 포인터(노드 포인터)는 다른 노드를 가리키게 된다.
처음 아무 자료가 없이 연결 리스트의 시작을 담당하는 노드 포인터를 헤드라고 한다.
보통 헤드에서 시작해서 계속 간접 참조를 하여 특정 위치까지 이동한다.
연결 리스트와 배열의 가장 큰 차이는, 인덱스의 사용 여부이다.
배열은 인덱스를 이용하면 직접 참조할 수 있지만, 연결 리스트는 헤드에서 시작해서 포인터를 이용해서 접근해야 하므로 느리다.
이러한 이유로 연결 리스트는 보통 인덱스를 사용하지 않는다.(처음 혹은 끝에 접근해서 추가, 삭제 혹은 값을 찾아서 삭제)
연결 리스트 ADT
역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정할 수 있다.
연결리스트 구현
#include <stdio.h>
#include <stdlib.h>
/*
자료 : 정수
기능1 끝 삽입 : 원소를 연결리스트의 끝에 입력한다.
기능2 처음 삽입 : 원소를 연결리스트의 처음에 입력한다.
기능3 끝 삭제 : 연결리스트의 마지막 값을 삭제한다.
기능4 처음 삭제 : 연결리스트의 처음 값을 삭제한다.
기능5 값 삭제 : 원소를 입력받아, 그 값이 있다면 값을 삭제한다.
기능6 수정 : 원소를 입력받아, 그 값이 있다면 기존의 값을 입력받은 값으로 수정한다.
기능7 순회 : 연결리스트의 모든 원소를 처음부터 출력한다.
*/
typedef struct Node* nodePointer;
typedef struct Node {
int data; // 자료 값
nodePointer next; // 다음 노드를 가리키는 포인터
} node; // 노드
// + 노드를 만드는 함수
nodePointer make_node(int data) {
nodePointer new_node = (nodePointer)malloc(sizeof(node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// 노드가 비었는지 확인하는 함수
int is_empty(nodePointer head) {
if (head == NULL) {
return 1; // 비었다면 참
}
else {
return 0; // 아니라면 거짓
}
}
//기능1 끝 삽입 : 원소를 연결리스트의 끝에 입력한다.
int push_back(nodePointer* head, const int data) {
if (is_empty(*head)) {
*head = make_node(data);
}
else {
nodePointer temp = *head;
//편하게 하기 위해 temp 변수 생성
while (temp->next != NULL) {
//다음 노드포인터 값이 NULL일 때까지
temp = temp->next;
}
temp->next = make_node(data);
//맨 마지막에 추가
}
printf("sucessfully pushed %d in the back of linked list\n\n", data);
return 0;
}
//기능2 처음 삽입 : 원소를 연결리스트의 처음에 입력한다.
int push_front(nodePointer* head, const int data) {
if (is_empty(*head)) {
*head = make_node(data);
}
else {
nodePointer temp = *head;
//만약 헤드가 가리키던 노드가 있다면, temp에 주소 저장
nodePointer new_node = make_node(data);
*head = new_node;
//헤드는 새 노드를 가리키고,
new_node->next = temp;
// 새 노드는 헤드가 가리키던 노드를 연결
}
printf("sucessfully pushed %d in the front of linked list\n\n", data);
return 0;
}
//기능3 끝 삭제 : 연결리스트의 마지막 값을 삭제한다.
int del_back(nodePointer* head) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");
return -1;
//비었으면 에러
}
else {
nodePointer temp = *head;
nodePointer prev = NULL;
// 마지막 노드포인터 직전의 노드포인터를 알아야, next에 NULL처리를 해줄 수 있음.
while (temp->next != NULL) {
//다음 노드포인터 값이 NULL일 때까지
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}
printf("sucessfully deleted in the back of linked list\n\n");
return 0;
}
//기능4 처음 삭제 : 연결리스트의 처음 값을 삭제한다.
int del_front(nodePointer* head) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");
return -1;
//비었으면 에러
}
else {
nodePointer temp = *head;
//만약 헤드가 가리키던 노드가 있다면, temp에 주소 저장
*head = temp->next;
// 헤드가 가리키던 노드(temp)의 다음 노드를 가리키게 함.
free(temp);
}
printf("sucessfully deleted in the front of linked list\n\n");
return 0;
}
//기능5 값 삭제 : 원소를 입력받아, 그 값이 있다면 값을 삭제한다.
int del_value(nodePointer* head, const int data) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");//비었으면 에러
return -1;
}
else {
nodePointer temp = *head;
nodePointer prev = NULL;
// 특정 값 노드포인터 직전의 노드포인터를 알아야, next에 NULL처리를 해줄 수 있음.
while (temp->next != NULL) {
//다음 노드포인터 값이 NULL일 때까지
if (temp->data == data) {
prev->next = temp->next; //
free(temp);
printf("sucessfully %d is deleted in the front of linked list\n\n", data);
return 0;
}
prev = temp;
temp = temp->next;
}
}
printf("There is no %d in linked list\n\n", data);
return -1;
}
//기능6 수정 : 원소를 입력받아, 그 값이 있다면 기존의 값을 입력받은 값으로 수정한다.
int update(nodePointer* head, const int data, const int new_data) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");
return -1;
//비었으면 에러
}
else {
nodePointer temp = *head;
nodePointer prev = NULL;
// 특정 값 노드포인터 직전의 노드포인터를 알아야, next에 NULL처리를 해줄 수 있음.
while (temp->next != NULL) {
//다음 노드포인터 값이 NULL일 때까지
if (temp->data == data) {
temp->data = new_data;
printf("sucessfully %d is deleted in the front of linked list\n\n", data);
return 0;
}
prev = temp;
temp = temp->next;
}
}
printf("There is no %d in linked list\n\n", data);
return -1;
}
//기능7 순회 : 연결리스트의 모든 원소를 처음부터 출력한다.
int traversal(nodePointer head) {
if (is_empty(head)) {
printf("Linked list has no element!\n\n");
//비었으면 에러
return -1;
}
else {
printf("traversal:\n");
nodePointer temp = head;
while (temp != NULL) {
//현재 포인터 값이 NULL일 때까지
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n\n");
}
return 0;
}
int main(void) {
nodePointer head = NULL;// 시작 노드
traversal(head);
push_back(&head, 1);
push_back(&head, 2);
push_back(&head, 3);
traversal(head); // 1 2 3
push_front(&head, 1);
push_front(&head, 2);
push_front(&head, 3);
traversal(head); // 3 2 1 1 2 3
del_front(&head);
del_back(&head);
traversal(head); // 2 1 1 2
push_front(&head, 7);
push_front(&head, 6);
push_front(&head, 4);
push_back(&head, 5);
traversal(head); // 4 6 7 2 1 1 2 5
del_value(&head, 6);
del_value(&head, 8); //에러
traversal(head); // 4 7 2 1 1 2 5
update(&head, 7, 3);
update(&head, 7, 3);//에러
traversal(head); // 4 3 2 1 1 2 5
}
연결 리스트 뿐만 아니라, 자료구조를 공부할 때는 그림을 잘 상상하는 것이 중요하다.
할당과 해제 시, 어떤 구조를 가지는지 잘 생각해봐야 하는데 각각의 상황은 마치 이렇다.
검은색 실선은 실제로 가리키는 것, 초록색 점선은 포인터의 더 이상 가리키지 않는 주소이다.
또한, 초록색 점선이 노드를 가리키고 있다면 할당 해제를 의미한다.
빈 연결 리스트에 연결하는 경우
- head가 아무것도 가리키지 않고 있다.(NULL)
- 새로 노드를 할당하고, head가 새 노드를 가리키게 한다.
원소가 한 개 이상 있는 연결 리스트의 마지막에 연결하는 경우
- 마지막 노드의 노드 포인터가 아무것도 가리키지 않고 있다.(NULL)
- 새로 노드를 할당하고, 마지막 노드의 노드 포인터가 새 노드를 가리키게 한다.
원소가 한 개 이상 있는 연결 리스트의 처음에 연결하는 경우
- head가 다음 노드를 가리키고 있다.
- 새로 노드를 할당하고, head가 원래 가리키던 노드 말고 새 노드를 가리킨다.
- 새 노드가 원래 head가 가리키던 노드를 가리킨다.
원소가 한 개 이상 있는 연결 리스트의 마지막 원소를 삭제하는 경우
- 마지막 노드의 노드 포인터가 아무 것도 가리키지 않고 있다. (NULL)
- 마지막 노드의 바로 전 노드의 노드 포인터를 아무것도 가리키지 않게 한다.(NULL)
- 마지막 노드를 할당 해제한다.
원소가 한 개 이상 있는 연결 리스트의 처음 원소를 삭제하는 경우
- head가 처음 노드를 가리키고 있다.
- head가 원래 가리키던 처음 노드 말고, 그 노드가 가리키던 다음 주소를 가리킨다.
- 처음 노드를 할당 해제한다.
원소가 한 개 이상 있는 연결 리스트의 중간 원소를 삭제하는 경우
가장 복잡하기 때문에, 과제로 넘기도록 하겠다!
결과창
Linked list has no element!
sucessfully pushed 1 in the back of linked list
sucessfully pushed 2 in the back of linked list
sucessfully pushed 3 in the back of linked list
traversal:
1 2 3
sucessfully pushed 1 in the front of linked list
sucessfully pushed 2 in the front of linked list
sucessfully pushed 3 in the front of linked list
traversal:
3 2 1 1 2 3
sucessfully deleted in the front of linked list
sucessfully deleted in the back of linked list
traversal:
2 1 1 2
sucessfully pushed 7 in the front of linked list
sucessfully pushed 6 in the front of linked list
sucessfully pushed 4 in the front of linked list
sucessfully pushed 5 in the back of linked list
traversal:
4 6 7 2 1 1 2 5
sucessfully 6 is deleted in the front of linked list
There is no 8 in linked list
traversal:
4 7 2 1 1 2 5
sucessfully 7 is deleted in the front of linked list
There is no 7 in linked list
traversal:
4 3 2 1 1 2 5
연결 리스트의 종류
사실 연결 리스트는 디테일에 따라 나뉘는 종류가 많다.
우리가 구현한 연결 리스트는 단일 연결 리스트라고 하고, 모든 응용 연결 리스트의 기본이 되는 구조이다.
여기서 연결 리스트가 다음 노드 정보만 가지는 것이 아니라, 이전 노드의 정보를 가지면 이중 연결 리스트,
단일 연결 리스트의 마지막 노드가 다시 처음 노드를 가리키면 원형 단일 연결 리스트,
이중 연결 리스트의 마지막 노드가 다시 처음 노드를 가리키면 원형 이중 연결 리스트이다.
모든 구조의 연결 리스트를 다루기에는 한 강의에서 힘들어서, 이번 강의에서는 단일 연결 리스트, 이중 연결 리스트만 다루고, 원형 연결리스트는 과제로 넘기겠다.
이중 연결 리스트의 구현
이중 연결 리스트는 단일 연결 리스트의 구조체를 조금만 수정해서 구현할 수 있다.
다음 노드를 가리키는 것뿐만 아니라, 이전 노드의 값을 가져야 한다는 점이 다르다.
이게 무슨 이점을 가지냐 하면, 양방향 참조가 가능하다.
int r_traversal(nodePointer head) { //역방향 참조
if (is_empty(head)) {
printf("Linked list has no element!\n\n");//비었으면 에러
return -1;
}
else {
printf("traversal:\n");
nodePointer temp = head;
while (temp->next != NULL) {//현재 포인터 값이 NULL일 때까지
temp = temp->next;
}// 마지막 노드로 가서
while (temp != NULL) {//현재 포인터 값이 NULL일 때까지
printf("%d", temp->data);
temp = temp->prev;
}// 마지막 노드로 가서
printf("\n\n");
}
return 0;
}
그 덕분에, 삭제 혹은 추가 시 훨씬 간단하게 처리할 수 있다.
그전에는 노드 포인터를 굳이 2개를 만들어야 했다면, 여기서는 하나의 노드 포인터로만 해도 충분히 가능하다.
typedef struct Node* nodePointer;
typedef struct Node {
int data; // 자료 값
nodePointer prev; // 이전 노드를 가리키는 포인터
nodePointer next; // 다음 노드를 가리키는 포인터
} node; // 노드
대부분의 코드는 수정할 것이 없고, make_node를 이렇게 바꿔줘야한다.
nodePointer make_node(int data) {
nodePointer new_node = (nodePointer)malloc(sizeof(node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
또한, push 함수들은 새로운 노드가 앞, 뒤의 노드를 가리킬 수 있게 한 문장만 추가해주면 된다.
int push_back(nodePointer* head, int data) {
if (is_empty(*head)) {
*head = make_node(data);
}
else {
nodePointer temp = *head;//편하게 하기 위해 temp 변수 생성
while (temp->next != NULL) { //다음 노드포인터 값이 NULL일 때까지
temp = temp->next;
}
temp->next = make_node(data);//맨 마지막에 추가
temp->next->prev = temp;// 새 노드의 prev는 처음을 가리키도록 한다.
}
printf("sucessfully pushed %d in the back of linked list\n\n", data);
return 0;
}
//기능2 처음 삽입 : 원소를 연결리스트의 처음에 입력한다.
int push_front(nodePointer* head, int data) {
if (is_empty(*head)) {
*head = make_node(data);
}
else {
nodePointer temp = *head;
//만약 헤드가 가리키던 노드가 있다면, temp에 주소 저장
nodePointer new_node = make_node(data);
*head = new_node;
//헤드는 새 노드를 가리키고,
temp->prev = new_node;
// temp 노드도 새 노드를 가리킴
new_node->next = temp;
// 새 노드는 헤드가 가리키던 노드를 연결
}
printf("sucessfully pushed %d in the front of linked list\n\n", data);
return 0;
}
역시, 삭제 함수들이 더 이상 prev에 대한 노드 포인터를 안 만들어도 되니까 더 간단해진다.
//기능3 끝 삭제 : 연결리스트의 마지막 값을 삭제한다.
int del_back(nodePointer* head) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");//비었으면 에러
return -1;
}
else {
nodePointer temp = *head;
while (temp->next != NULL) { //다음 노드포인터 값이 NULL일 때까지
temp = temp->next;
}
temp->prev->next = NULL;// 더 이상 prev를 변수로 만들 필요가 없어짐
free(temp);
}
printf("sucessfully deleted in the back of linked list\n\n");
return 0;
}
//기능4 처음 삭제 : 연결리스트의 처음 값을 삭제한다.
int del_front(nodePointer* head) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");//비었으면 에러
}
else {
nodePointer temp = *head; //만약 헤드가 가리키던 노드가 있다면, temp에 주소 저장
if(temp->next != NULL){ //만약 temp 노드가 가리키던 노드가 있다면,
temp->next->prev = NULL; //그 노드의 prev는 NULL로 만들어야 함.
}
*head = temp->next; // 헤드는 temp 노드의 다음 노드를 가리키게 함.
free(temp);
}
printf("sucessfully deleted in the front of linked list\n\n");
return 0;
}
//기능5 값 삭제 : 원소를 입력받아, 그 값이 있다면 값을 삭제한다.
int del_value(nodePointer* head, int data) {
if (is_empty(*head)) {
printf("Linked list has no element!\n\n");//비었으면 에러
return -1;
}
else {
nodePointer temp = *head;
while (temp->next != NULL) { //다음 노드포인터 값이 NULL일 때까지
if (temp->data == data) {
if(temp->prev != NULL){
temp->prev->next = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
printf("sucessfully %d is deleted in the front of linked list\n\n", data);
return 0;
}
temp = temp->next;
}
}
printf("There is no %d in linked list\n\n", data);
return -1;
}
그리고 마지막, 이중 연결 리스트의 꽃, 역방향 순회이다.
int r_traversal(nodePointer head) { //역방향 참조
if (is_empty(head)) {
printf("Linked list has no element!\n\n");//비었으면 에러
return -1;
}
else {
printf("reverse traversal:\n");
nodePointer temp = head;
while (temp->next != NULL) {//현재 포인터 값이 NULL일 때까지
temp = temp->next;
}// 마지막 노드로 가서
while (temp!= NULL) {//현재 포인터 값이 NULL일 때까지
printf("%d ", temp->data);
temp = temp->prev;
}// 처음 노드로 가서
printf("\n\n");
}
return 0;
}
결과창
Linked list has no element!
sucessfully pushed 1 in the back of linked list
sucessfully pushed 2 in the back of linked list
sucessfully pushed 3 in the back of linked list
traversal:
1 2 3
reverse traversal:
3 2 1
sucessfully pushed 1 in the front of linked list
sucessfully pushed 2 in the front of linked list
sucessfully pushed 3 in the front of linked list
traversal:
3 2 1 1 2 3
reverse traversal:
3 2 1 1 2 3
sucessfully deleted in the front of linked list
sucessfully deleted in the back of linked list
traversal:
2 1 1 2
reverse traversal:
2 1 1 2
sucessfully pushed 7 in the front of linked list
sucessfully pushed 6 in the front of linked list
sucessfully pushed 4 in the front of linked list
sucessfully pushed 5 in the back of linked list
traversal:
4 6 7 2 1 1 2 5
reverse traversal:
5 2 1 1 2 7 6 4
sucessfully 6 is deleted in the front of linked list
There is no 8 in linked list
traversal:
4 7 2 1 1 2 5
reverse traversal:
5 2 1 1 2 7 4
sucessfully 7 is deleted in the front of linked list
There is no 7 in linked list
traversal:
4 3 2 1 1 2 5
reverse traversal:
5 2 1 1 2 3 4
단일 연결 리스트와 이중 연결 리스트의 장단점
이때까지 단일 연결 리스트와 이중 연결 리스트를 둘 다 다루어보았다.
단일 연결 리스트의 장점은 명확하다. Simple is the best, 메모리도 절약되고 자체적으로도 필수적인 기능은 모두 구현할 수 있다.
하지만 단점은, 포인터에 대한 이해가 확실해야 하고 한 방향 순회밖에 안 된다는 단점이 있다.
반대로, 이중 연결 리스트는 노드 포인터를 하나 더 저장해야 하기에 메모리에 대한 손해를 감수한다.
하지만 구현이 훨씬 직관적이며, 양방향 순회가 가능하다.
어떤 게 무조건 좋다는 것이 아니라, 필요한 상황에 적절한 자료구조를 선택할 수 있게 이해하는 것이 중요하다.
📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)
✅ 1. 단일 연결 리스트를 구현할 수 있다.
✅ 2. 이중 연결 리스트를 구현할 수 있다.
✅ 3. 단일, 이중 연결 리스트의 장단점을 각각 안다.
✅ 4. 원형 단일, 이중 연결 리스트의 장단점을 각각 안다.(과제!!)
⚠️ 어떤 게 무조건 좋다는 것이 아니라, 필요한 상황에 적절한 자료구조를 선택하자.
💣 과제,
-
연결리스트의 중간 값을 삭제했을 때 포인터가 어떻게 처리되야하는지 그림으로 그려보자. (난이도 中)
-
오름차순 정렬된 이중 연결 리스트를 구현해보자. (난이도 中) (삽입하면 자기가 저장될 위치를 찾아서 저장됨)
-
stack, queue, deque 를 단일 연결 리스트로 구현해보자(난이도 中)
-
위의 자료구조를 구현할 때 배열과 연결 리스트 중 어떤 것이 좋은지, 둘의 장단점을 기준으로 생각해보자(난이도 上)
-
원형 연결리스트를 구현해보고, 장점을 생각해보자. (힌트 : 마지막 노드를 찾는 기능을 구현해보자)
Comments