리스트(list)
자료를 정리하는 방법 중에 하나
리스트의 기본 연산
1. 삽입 연산
리스트에 새로운 항목을 추가
2. 삭제 연산
리스트에서 항목을 삭제
3. 탐색 연산
리스트에서 특정한 항목을 검색
리스트의 구현 방법
리스트는 배열과 연결리스트를 이용하여 구현 가능
| 장점 | 단점 | |
| 배열 | 간단하게 구현가능, 크기가 고정 | 1. 데이터를 중간에 삽입할 경우에 데이터들이 이동해야함 2. 데이터를 삽입할 경우 공간이 부족하면 더 큰 배열을 만들어서 데이터를 기존 복사하고 새로운 데이터를 추가 => cpu시간을 낭비시킴 |
| 연결 리스트 | 1. 중간에 쉽게 삽입/삭제 가능 2. 리스트의 크기가 제한되지 않음 |
임의의 항목에 접근할 경우 배열보다 시간이 오래 걸림 |
구조체로 정의한 리스트
#define MAX_LIST_SIZE 100
typedef int element;
typedef struct {
element array[MAX_LIST_SIZE];
int size;
} ArrayListType;
기초 연산
구조체를 참조하기 위하여 포인터를 전달
포인터를 사용하지 않으면 복사본(레퍼런스)이 전달됨
void error(char* message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 리스트 초기화 함수
void init(ArrayListType* L)
{
L->size = 0;
}
// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType* L)
{
return L->size == 0;
}
// 리스트가 가득 차 있으면 1을 반환
// 그렇지 많으면 1을 반환
int is_full(ArrayListType* L)
{
return L->size == MAX_LIST_SIZE;
}
//
element get_entry(ArrayListType* L, int pos)
{
if (pos < 0 || pos >= L->size)
error("위치 오류");
return L->array[pos];
}
// 리스트 출력
void print_list(ArrayListType* L)
{
int i;
for (i = 0; i < L->size; i++)
printf("%d->", L->array[i]);
printf("\n");
}
리스트의 끝에 항목 추가 연산(리스트에 빈 공간이 없으면 오류를 발생시킴)
void insert_last(ArrayListType* L, element item)
{
if (L->size >= MAX_LIST_SIZE) {
error("리스트 오버플로우");
}
L->array[L->size++] = item;
}
ArrayListType의 구현
리스트의 중간에 항목 추가 연산
void insert(ArrayListType* L, int pos, element item)
{
if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
for (int i = (L->size - 1); i >= pos; i--)
L->array[i + 1] = L->array[i];
L->array[pos] = item;
L->size++;
}
}
pos = 1에 새로운 항목을 추가할 경우(마지막 원소가 array[3]인 경우)
array[1]부터 array[3]까지 한 칸씩 오른쪽으로 이동
뒤에서 부터 array[3]을 array[4]로 옮기는 작업 시작
마지막으로 새로운 항목을 array[1]에 삽입
항목 삭제 연산
element delete(ArrayListType* L, int pos)
{
element item;
if (pos < 0 || pos >= L->size)
error("위치 오류");
item = L->array[pos];
for (int i = pos; i < (L->size - 1); i++)
L->array[i] = L->array[i + 1];
L->size--;
return item;
}
1. pos 위치의 항목을 삭제
2. 삭제한 후 array[pos + 1]부터 array[size - 1]까지 삽입과 반대로 한 칸씩 앞으로 이동
연결된 표현(linked representation)
특징
1. 하나의 프로그램 안에는 동시에 여러 개의 연결 리스트가 존재할 수 있음
2. 연결리스트의 첫번째 데이터로 연결리스트를 구분
=> 첫번째 데이터를 알면 나머지는 이어진 포인터 정보로 알 수 있음
3. 연결리스트는 데이터를 추가할 때 마다 동적으로 추가
C언어에선 malloc()을 사용
4. 구현이 어렵고 오류가 발생하기 쉬움
5. 데이터 검색 시 배열보다 복잡함
=> i번째 데이터를 읽으려면 첫번째 데이터부터 순차적으로 읽어야 함.
구조
1. 연결리스트의 항목을 노드(node)라고 지칭
2. 연결리스트는 노드(node)들의 집합
3. 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성
=> 데이터 필드 - 리스트의 원소, 즉 데이터 값을 저장하는 곳
=> 링크 필드 - 다른 노드의 주소 값을 저장하는 장소(포인터)
4. 연결리스트는 첫번째 노드를 알아야 전체 노드에 접근 가능
5. 마지막 노드의 링크 필드는 NULL로 설정
종류
1. 단순 연결 리스트
=> chain이라고도 하며 한 방향으로만 연결
=> 마지막 노드의 링크 필드는 NULL값을 가짐
2. 원형 연결 리스트
=> 단순 연결 리스트처럼 한 방향으로 연결되어 있으며 마지막 노드의 링크는 첫번째 노드를 가리킴
3. 이중 연결 리스트
=> 각 노드마다 2개의 링크가 존재
=> 각각 앞뒤의 노드를 가리킴
단순 열결 리스트
=> 하나의 링크 필드르르 가지고 다른 노드와 연결
자기 참조 구조체로 노드를 정의
malloc()을 호출하여 노드를 동적으로 생성
free()를 호출하여 노드를 삭제(메모리 해제)
노드의 정의
노드는 자기 참조 구조체를 이용하여 정의
(자기 참초 구조체 : 자기 자신을 참조하는 포인터를 포함하는 구조체)
구조체 내부에는 데이터를 저장하는 data필드와 포인터가 저장되는 link필드가 존재
data필드는 element 타입의 데이터를 저장
link필드는 listnode를 가리키는 포인터로 정의되며 다음 노트의 주소가 저장
typedef struct ListNode { // 노드 타입을 구조체로 정의한다.
element data;
struct ListNode* link;
} ListNode;
공백 리스트의 생성
단순 연결리스트는 레드포인터가 있어야 연결된 모든 노드를 찾을 수 있음
하나의 단순 연결 리스트를 생성할 경우에 노드를 가리키는 포인터 head를 정의
=> 노드가 없는 경우에는 헤드포인터를 NULL로 설정
노드의 생성
동적 메모리 할당으로 노드를 생성
*첫번째 노드의 주소를 head에 저장("너무 중요한 말")
ListNode* head = NULL;
head = (ListNode *)malloc(sizeof(ListNode));
head -> data = 10;
head -> link = NULL;
노드의 연결
ListNode *p;
p = (ListNode *)malloc(sizeof(ListNode));
p -> data = 20;
p -> link = NULL;
여기는 20의 값을 가진 노드를 생성만 한것이고 이제 10의 값을 가진 노드와 연결해야한다.
head ->link = p;
첫번째 노드의 주소를 head에 저장했기 때문에 이제 head가 첫번째 노드입니다. 그래서 head -> link = p;는 첫번째 노드의 링크를 두번째 노드에 연결한다는 의미가 됩니다.
단순 연결 리스트의 연산
insert_first() : 리스트의 시작 부분에 항목을 삽입하는 함수
insert() : 리스트의 중간 부분에 항목을 삽입하는 함수
delete_first() : 리스트의 첫 번째 항목을 삭제하는 함수
delete() : 리스트의 중간 항목을 삭제하는 함수
print_llist() : 리스트를 방문하여 모든 항목을 출력하는 함수
1. insert_first()
ListNode* insert_first(ListNode* head, int value) {
ListNode* p = (ListNode*)malloc(sizeof(ListNode)); //(1)
p->data = value;
// (2)
p->link = head; //(3)
head = p; //(4)
return head; // 변경된 헤드포인터 반환
}
(1)은 새로운 포인터 p 생성, (2)는 인자로 받은 값을 data로 입력, (3)은 head가 가리키는 첫번째 노드를 p의 링크도 가리키게 함 (4)는 head를 p노드로 지정. 마지막으로 return head는 새로만든 노드 리턴
*(3)번이 좀 헷갈릴 수 있다.
2. insert()
// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, element value)
{
ListNode* p = (ListNode*)malloc(sizeof(ListNode));
//(1)
p->data = value; //(2)
p->link = pre->link; //(3)
pre->link = p; //(4)
return head; //(5)
}
(2)는 새로운 노드에 value 입력 (3)은 pre의 링크가 가리키는 노드를 p의 링크도 가리키도록 지정 (4)는 pre의 링크를 p로 지정 그리고 return head는 중간에 노드가 추가된 연결 리스트 반환.
3. delete_first()
// 앞부분의 노드 제거
ListNode* delete_first(ListNode* head)
{
ListNode* removed;
if (head == NULL) return NULL;
removed = head; // (1)
head = removed->link; // (2)
free(removed); // (3)
return head; // (4)
}
(1)은 제거할 첫번째 노드(head)를 removed에 저장 (2)는 removed의 링크가 가리키는 값을 head가 가리키게 함 (3)은 이제 removed를 소멸시켜버려서 삭제해버림 return head하면 정렬되어 있진 않지만 포인터로 연결된 노드들이 반환.
4. delete()
// pre가 가리키는 노드의 다음 노드를 삭제.
ListNode* delete(ListNode* head, ListNode* pre)
{
ListNode* removed;
removed = pre->link; // (1)
pre->link = removed->link; // (2)
free(removed); // (3)
return head; // (4)
}
(1)은 pre의 링크가 가리키는 노드를 removed로 지정 이러면 지워야할 노드 전에 있는 pre로 지워야할 노드 지정 가능(2)는 removed가 가리키는 지워야할 노드의 다음 노드를 지워야할 노드의 전 노드인 pre의 링크가 가리키게 함 (3) removed를 소멸 시킴으로서 지워야할 노드를 지워버림 return head는 링크끼리의 연결도 끊어지고 메모리에서도 소멸된 노드가 없는 연결 리스트 반환
5. print_list()
// 리스트 출력
void print_list(ListNode* head)
{
for (ListNode* p = head; p != NULL; p = p->link)
printf("%d->", p->data);
printf("NULL \n");
}
for문은 p가 head에서 시작해서 연결된 링크를 계속 따라가는데 연결리스트의 마지막 노드가 NULL인것을 감안해서 NULL이면 멈추는 반복이다.
// 메인
int main(void)
{
ListNode *head = NULL;
for (int i = 0; i < 5; i++) {
head = insert_first(head, i);
print_list(head);
}
for (int i = 0; i < 5; i++) {
head = delete_first(head);
print_list(head);
}
return 0;
}
위의 내용을 모두 합치고 main() 함수를 실행하면 다음과 같은 결과가 나옵니다.
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL
'[Computer Science] > [자료구조 in C]' 카테고리의 다른 글
| [자료구조] 이진트리와 시간복잡도 로그의 의미 (0) | 2022.06.19 |
|---|---|
| [자료구조] 정렬 : C언어 (0) | 2022.06.18 |
| [자료구조] 트리_하 : C언어 (0) | 2022.06.18 |
| [자료구조] 트리_상 : C언어 (0) | 2022.06.18 |
| [자료구조] 연결리스트(2) : C언어 (0) | 2022.05.30 |