학교수업, CS/자료구조
단순 연결 리스트
빨대도둑
2022. 11. 1. 15:26
「리스트」
- 리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 스택과 큐도 넓게 보면 리스트의 일종이다.
리스트 표기법
L=(item0, item1, item2, item3...item n-1)- 삽입 연산: 리스트에 새로운 항목을 추가한다
- 삭제 연산: 리스트에서 항목을 삭제한다
- 탐색 연산: 리스트에서 특정한 항목을 찾는다
- 리스트 ADT
insert(list, pos, item)::=pos위치에 요소를 추가
insert_list(list,item)::=맨 끝에 요소를 추가
insert_first(list, item)::=맨 처음에 요소를 추가
delete(list, pos)::=pos 위치의 요소를제거
clear(list)::=리스트의 모든 요소를 제거
get_entry(list,pos)::=pos위치의 요소를 반환
get_length(list)::= 리스트의 길이를 구함
is_empty(list)::=리스트가 비었는지 검사
is_full(list)::=리스트가 찼는지 검사
print_list(list)::=리스트의 모든 요소 표시
- 리스트 구현
> 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다. 배열을 이용하면 리스트 ADT를 간단하게 구현할 수 있지만 크기가 고정되는 단점이 있다. 다른 방법으로 포인터를 이용해서 연결 리스트를 만들 수 있다. 연결리스트는 중요할 때마다 중간에 속지를 추가해서 사용할 수 있는 바인더 공책과 비슷하다.
장점 > 구현이 간단하고 속도가 빠르다
단점> 리스트의 크기가 고정된다
> 배열의 특성상 동적으로 크기를 늘리거나 줄이는 것이 힘들다. 그래서 만약 데이터를 추가하고 싶은데 더이상 남는 공간이 없다면 문제가 발생한다.
> 연결 리스트는 크기가 제한되지 않고, 중간에 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트를 구현할 수 있다. 하지만 구현이 복잡하고 임의의 항목을 추출하려고 할 때에 배열을 사용하는 방법보다 시간이 많이 걸린다는 단점이 있다.
- 배열로 구성된 리스트
> 배열을 이용해 리스트를 구현하면 순차적인 메모리 공간이 할당되므로 이것을 리스트의 순차적 표현(sequential representation)이라고 한다.
#include <stdio.h>
#include <stdlib.h>
// 리스트의 최대크기
#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;
}
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++;
}
}
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;
}
int main(void)
{
/* ArrayListType를 정적으로 생성하고 ArrayListType를
가리키는 포인터를 함수의 매개변수로 전달한다.*/
ArrayListType list;
init(&list);
insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가
insert(&list, 0, 20); print_list(&list); // 0번째 위치에 20 추가
insert(&list, 0, 30); print_list(&list); // 0번째 위치에 30 추가
insert_last(&list, 40); print_list(&list); // 맨 끝에 40 추가
delete(&list, 0); print_list(&list); // 0번째 항목 삭제
return 0;
}시간 복잡도 > 임의의 항목에 접근하는 연산인 get_entry 연산은 인덱스를 사용하여 항목에 바로 접근할 수 있으므로 O(1)이다. 삽입이나 삭제 연산은 다른 항목들을 이용하는 경우가 많으므로 최악의 경우 O(n)이 된다.
「연결 리스트」
- 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현(linked)
> 포인터를 사용하여 데이터를 연결 한다.
> 연결된 표현은 일단 데이터를 한 군데 모아두는 것을 포기한다. 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다. 이런 식으로 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결리스트(linked list)라고 한다. 상자를 연결하는 줄은 pointer로 구현한다.
> 하나의 프로그램 안에는 동시에 여러 개의 연결 리스트가 존재할 수 있다. 이럴 때 연결 리스트들을 구분하는 것은 첫 번째 데이터이다. 첫번째 데이터만 알 수 있으면 연결 리스트의 나머지 데이터들은 줄만 따라가면 얻을 수 있다. 연결 리스트의 또 하나의 장점은 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다. 배열에서 장점이 된다.
- 연결 리스트의 구조
> 연결 리스트는 노드(node)의 집합이다. 노드들은 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서 현재 노드가 가지고 있는 포인터를 사용하면 된다. 데이터 필드와 링크 필드로 구성되어 있다.
데이터 필드> 저장하고 싶은 데이터가 들어간다. 데이터는 정수가 될 수 도 있고 구조체와 같은 복잡한 데이터가 될 수도 있다.
링크 필드> 다른 노드를 가리키는 포인터가 저장된다. 이 포인터를 이용해서 다음 노드로 건너갈 수 있다.
> 연결 리스트에서는 첫 번째 노드를 알아야 전체의 노드에 접근할 수 있다. 따라서 연결 리스트는 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터(head pointer)라고 한다. 또 마지막 노드의 링크 필드는 null로 설정하는데 이는 더 이상 연결될 노드가 없다는 것을 의미한다.
> 연결 리스트들의 노드들은 필요할 때마다 malloc()을 이용하여 동적으로 생성된다.
- 연결리스트의 종류
- 단순연결 리스트(singley linked list): 하나의 방향으로만 연결되어 있는 연결 리스트. 체인(chain)이라고 한다. 연결 리스트에서 마지막 노드의 링크는 null을 가진다
- 원형 연결 리스트(circular linked list): 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킨다
- 이중 연결 리스트(doubly linked list): 각 노드마다 2개씩 링크가 존재한다. 하나의 링크는 앞에 있는 노드를 가리키고 또 하나의 링크는 뒤에 있는 노드를 가리킨다
- 단순 연결 리스트
> 단순 연결 리스트는 원칙적으로 헤드 포인터만 있으면 된다.
ListNode *head;> 단순 연결 리스트에서는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있다. 또한 마지막 노드의 링크 필드 값은 NULL이 된다.
- 노드는 자기 참조 구조체를 이용해서 정의한다
- 노드는 malloc()을 호출해서 동적 메모리로 생성한다
- 노드는 free()를 호출해서 동적메모리를 해제한다.
「공백 리스트」
> 단순 연결 리스트는 헤드 포인터만 있으면 노드를 찾을 수 있다. 따라서 노드를 가리키는 포인터 head를 정의하면 하나의 단순 연결 리스트가 만들어졌다고 불 수 있다. 현재는 노드가 없으므로 head의 값은 NULL이다
> 어떤 리스트가 공백인지 알고 싶으면 헤드 포인터가 NULL인지 검사하면 된다.
ListNode *head=NULL;
- 노드 생성
- 리스트에서는 필요할 때마다 동적 메모리 할당을 이용해서 노드를 동적으로 생성한다. malloc() 함수를 이용해서 노드의 크기만큼의 동적메모리를 할당받는다. 이 동적메모리는 하나의 노드가 되고 동적 메모리의 주소를 헤드 포인터인 head에 저장한다.head=(ListNode*) malloc(sizeof(ListNode));
- 새로 만들어진 노드에 데이터를 저장하고 링크 필드를 NULL로 설정한다. head->data=10; head->link=NULL:
- 노드의 연결
여러개의 노드가 연결되어 있고 동일한 방식으로
두번째 노드를 동적으로 생성하고 노드에 20을 저장하는 방법
ListNode *p;
p=(ListNode *)malloc(sizeof(ListNode));
p->data=20;
p->link=NULL;
「단순 연결리스트의 연산」
- insert_first: 리스트의 시작 부분에 항목을 삽입하는 함수
- insert(): 리스트의 중간 부분에 항목을 삽입하는 함수
- delete_first(): 리스트의 첫 번째 항목을 삭제하는 함수
- delete(): 리스트의 중간 항목을 삭제하는 함수
- print_list(): 리스트를 방문해서 모든 항목을 출력하는 함수
삽입 연산
insert_first (head, value): //L=연결 리스트, value=추가할 값
1. p <- malloc() // 동적 메모리할당을 통해서 새로운 노드 p를 생성한다
2. p -> data < -value // p->data에 value를 저장한다
3. p -> link <- head // p->link를 현재의 head값으로 변경한다
4. head <- p //head 값을 p값으로 변경한다
5. return head //변경된 헤드 포인터 반환
ListNode *insert_first (ListNode *head, element value){
ListNode *p==(ListNode*)malloc(sizeof(ListNode));
p->data=value;
p->link=head;
head=p;
return head;
}삽입 연산
insert (head,pre, value): //list=연결 리스트, value=추가할 값, pre= 선행 노드
1. p <- malloc()
2. p -> data < -value
3. p -> link <- pre -> link
4. pre -> link <- p
5. return head
ListNode *insert (ListNode *head, ListNode *pre, element value){
ListNode *p==(ListNode*)malloc(sizeof(ListNode));
p->data=value;
p->link=pre->link;
pre->link =p;
return head;
}삭제 연산
delete_first(head):
remove<-head //헤드 포인터의 값을 remove에 복사한다
head<- head -> link // 헤드 포인터의 값을 head->link로 변경한다
free(remove) //removed가 가리키는 동적 메모리를 반환한다
return head //변경된 헤드 포인터를 반환한다
ListNode *delete_first(ListNode *head){
ListNode *removed;
if(head==NULL) return NULL;
removed=head;
head=removed -> link;
free(removed);
return head;
}삭제 연산
delete_first(head, pre):
remove <-pre ->link //삭제할 노드를 찾는다
pre-> link <- removed -> link
free(remove) //removed가 가리키는 동적 메모리를 반환한다
return head //변경된 헤드 포인터를 반환한다
ListNode *delete(ListNode *head, ListNode* pre){
ListNode *removed;
removed=pre->link;
pre->link=removed->link;
free(removed);
return head;
}
- 전체 테스트
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
// 오류 처리 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
ListNode* insert_first(ListNode *head, int value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p->data = value;
p->link = head; // 헤드 포인터의 값을 복사
head = p; // 헤드 포인터 변경
return head; // 변경된 헤드 포인터 반환
}
// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode *head, ListNode *pre, element value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p->data = value;
p->link = pre->link;
pre->link = p;
return head; )
}
ListNode* delete_first(ListNode *head)
{
ListNode *removed;
if (head == NULL) return NULL;
removed = head;
head = removed->link;
free(removed);
return head;
}
// pre가 가리키는 노드의 다음 노드를 삭제한다.
ListNode* delete(ListNode *head, ListNode *pre)
{
ListNode *removed;
removed = pre->link;
pre->link = removed->link;
free(removed);
return head;
}
void print_list(ListNode *head)
{
for (ListNode *p = head; p != NULL; p = p->link)
printf("%d->", p->data);
printf("NULL \n");
}
// 테스트 프로그램
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;
}
- 다항식
> 다항식을 단순 연결 리스트로 표현이 가능하다.
typedef struck LinkNode{ //노드타입
int coef;
int expon;
struct ListNode *link;
}ListNode;
> 다항식의 첫 번째 항은 포인터로 가리킨다
ListNode *A, *B;
> 항의 지수에 따라 3가지 경우로 나누어서 처리할 수 있다.
- p.expon==q.expon: 두 계수를 더해서 0이 아니면 새로운 항을 만들어 결과 다항식 C에 추가한다. 그리고 p와 q는 다음 항으로 이동한다
- p.expon <q.expon: q가 지시하는 항을 새로운 항으로 복사하여 결과 다항식 C에 추가한다. 그리고 q만 다음 항으로 이동한다
- p.expon> q.expon: p가 지시하는 항을 새로운 항으로 복사하여 결과 다항식 C에 추가한다. 그리고 p만 다음 항으로 이동한다.
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode { // 노드 타입
int coef;
int expon;
struct ListNode *link;
} ListNode;
// 연결 리스트 헤더
typedef struct ListType { // 리스트 헤더 타입
int size;
ListNode *head;
ListNode *tail;
} ListType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 리스트 헤더 생성 함수
ListType* create()
{
ListType *plist = (ListType *)malloc(sizeof(ListType));
plist->size = 0;
plist->head = plist->tail = NULL;
return plist;
}
// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수,
// expon는 지수
void insert_last(ListType* plist, int coef, int expon)
{
ListNode* temp =
(ListNode *)malloc(sizeof(ListNode));
if (temp == NULL) error("메모리 할당 에러");
temp->coef = coef;
temp->expon = expon;
temp->link = NULL;
if (plist->tail == NULL) {
plist->head = plist->tail = temp;
}
else {
plist->tail->link = temp;
plist->tail = temp;
}
plist->size++;
}
// list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
ListNode* a = plist1->head;
ListNode* b = plist2->head;
int sum;
while (a && b) {
if (a->expon == b->expon) { // a의 차수 > b의 차수
sum = a->coef + b->coef;
if (sum != 0) insert_last(plist3, sum, a->expon);
a = a->link; b = b->link;
}
else if (a->expon > b->expon) { // a의 차수 == b의 차수
insert_last(plist3, a->coef, a->expon);
a = a->link;
}
else { // a의 차수 < b의 차수
insert_last(plist3, b->coef, b->expon);
b = b->link;
}
}
// a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두
// 결과 다항식으로 복사
for (; a != NULL; a = a->link)
insert_last(plist3, a->coef, a->expon);
for (; b != NULL; b = b->link)
insert_last(plist3, b->coef, b->expon);
}
//
//
void poly_print(ListType* plist)
{
ListNode* p = plist->head;
printf("polynomial = ");
for (; p; p = p->link) {
printf("%d^%d + ", p->coef, p->expon);
}
printf("\n");
}
//
int main(void)
{
ListType *list1, *list2, *list3;
// 연결 리스트 헤더 생성
list1 = create();
list2 = create();
list3 = create();
// 다항식 1을 생성
insert_last(list1, 3, 12);
insert_last(list1, 2, 8);
insert_last(list1, 1, 0);
// 다항식 2를 생성
insert_last(list2, 8, 12);
insert_last(list2, -3, 10);
insert_last(list2, 10, 6);
poly_print(list1);
poly_print(list2);
// 다항식 3 = 다항식 1 + 다항식 2
poly_add(list1, list2, list3);
poly_print(list3);
free(list1); free(list2); free(list3);
}