연결 리스트
연결 리스트의 필요성
- 일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고 나열할 수 있음
- 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음
배열 기반의 리스트
1.
- 데이터를 순차적으로 저장하고 처리할 때는 배열 기반의 리스트를 간단히 이용할 수 있음
* 1 5 4 7 6 8
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define mem 10000
int arr[mem];
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) {
addBack(7);
addBack(6);
addBack(8);
addFirst(4);
addFirst(5);
addFirst(1);
show();
system("pause");
return 0;
}
* 특정한 위치의 원소를 삭제하는 함수를 만드는 방법
- 특정한 위치의 원소를 삭제하는 removeAt() 함수 구현
- 값들을 하나씩 덮어쓰기 하는 방식
- 차례대로 뒤로 넘어가면서 각각의 값들을 앞으로 넣어주는 방식으로 리스트에서 특정한 원소를 삭제할 수 있음
1 2 3 4 5가 있을 때 3을 없앤다고 가정해보자 3은 인덱스 2번에 해당하니 인덱스 2번 자리에 4를 3번 자리에는 5를 넣어 하나씩 값을 앞으로 이동해서 삭제
void removeAt(int index) {
for (int i = index; i < count - 1; i++) {
arr[i] = arr[i + 1];
}
count--;
}
2.
- 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있음
- 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점이 있음
- 원하는 위치로의 삽입이나 삭제가 비효율적
연결 리스트
1.
- 일반적인 연결 리스트는 구조체와 포인터를 함께 사용하여 구현
- 연결 리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 함
- 필요할 때마다 메모리 공간을 할당 받음
2.
- 단일 연결 리스트는 다음과 같은 형태로 나타낼 수 있음
- 포인터를 이용해 단방향적으로 다음 노드를 가리킴
- 하나의 구조체 안에 두 개의 변수가 들어가도록 만듦, 한 개는 data를 담는 변수 한 개는 다음 노드를 가리키는 next 변수
data next > data next > data next
- 일반적으로 연결 리스트의 시작 노드를 헤드(Head)라고 하며 별도로 관리함
- 다음 노드가 없는 끝 노드의 다음 위치 값으로는 null을 넣음
next(Head) > data next(일반 노드) > data next(일반 노드) > null
* 연결 리스트 구조체 만들기
typedef struct{ // 하나의 구조체 생성
int data;
struct Node *next; // 다음 node를 가리키는 next변수 넣어줌
} Node; // 구조체의 이름
Node *head; // 연결 리스트 같은 경우는 head 노드로 부터 출발,
node는 포인터 변수로 동적 할당을 이용해서 변수를 만들수 있게 하는게 일반적
* 연결 리스트 구조체 사용해보기
int main(void){
head = (Node*)malloc(sizeof(Node)); // malloc을 이용해 필요한 만큼만 메모리 할당
Node *node1 = (Node*)malloc(sizeof(Node)); // 첫 번쨰 node 생성
node1->data = 1; // 첫 번째 node의 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;
}
연결 리스트 삽입 과정
next(Head) > 1 next(일반 노드) > 2 next(일반 노드) > null
7 next(Head와 1 사이에 삽입할 코드)
void addFront(Node *root, int data) { // root를 이용해 위치를 지정
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = root->next;
root->next = node;
}
연결 리스트 삭제 과정
next(Head) > 1 next(삭제할 노드) > 2 next(일반 노드) > null
void removeFront(Node *root) {
Node *front = root->next;
root->next = front->next;
free(front);
}
연결 리스트 메모리 해제 함수
void freeAll(Node *root) {
Node *cur = head->next;
while (cur != NULL) {
Node *next = cur->next;
free(cur);
cur = next;
}
연결 리스트 전체 출력 함수
void showAll(Node *root) {
Node *cur = head->next;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
}
완성된 연결 리스트 사용하기
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int data;
struct Node *next;
} Node;
Node *head;
void addFront(Node *root, int data) { // root를 이용해 위치를 지정
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = root->next;
root->next = node;
}
void removeFront(Node *root) {
Node *front = root->next;
root->next = front->next;
free(front);
}
void freeAll(Node *root) {
Node *cur = head->next;
while (cur != NULL) {
Node *next = cur->next;
free(cur);
cur = next;
}
}
void showAll(Node *root) {
Node *cur = head->next;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
}
int main(void){
head = (Node*)malloc(sizeof(Node));
head->next = NULL; // 항상 head의 next부분은 null값을 넣어야 함, 초기 상태부터 지금까지 아무 값이 없기 때문에 항상 연결리스트의 마지막은 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;
}
연결 리스트 구현에 있어서 주의할 점
- 위 소스코드에 덧붙여서 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있음
- 삭제할 원소가 없는데 삭제하는 경우, 머리(Head) 노드 자체를 잘못 넣은 경우 등을 체크해야 함
연결 리스트의 특징
- 삽입과 삭제가 배열에 비해서 간단하다는 장점이 있음
- 배열과 다르게 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야 함
- 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비됨
- 연결 리스트는 데이터를 선형적으로 저장하고 처리하는 한 방법
- 기존에 배열을 이용했을 때보다 삽입과 삭제가 많은 경우에서 효율적
- 다만 특정한 인덱스에 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적