리스트
- 리스트의 항목들은 순서 또는 위치를 가진다.
- cf) 집합 : 각 항목 간에 순서의 개념 x
- ADT
- 객체 : n개의 element형으로 구성된 순서 있는 모임
- 연산:
insert(list, pos, item) ::= pos 위치에 요소를 추가insert_last(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) ::= 리스트의 모든 요소 출력
배열로 구현된 리스트
- 장점
- 단점
- 리스트의 크기가 고정됨 → 동적으로 크기를 늘리거나 줄일 수 없다.
- 리스트 중간에 새로운 데이터를 삽입하거나 삭제하기 위해서는 기존의 데이터를 이동해야 함
- 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST 100
//ArrayList 구조체 만들기
typedef struct{
int data[MAX_LIST];
int size; // 요소의 개수 체크
}ArrayList;
void init(ArrayList* l){
l ->size = 0; // 개수 0개로 초기화
}
void error(const char* msg){
printf("%s\n",msg);
exit(1);
}
int isEmpty(ArrayList* l){
return l->size == 0;
}
int isFull(ArrayList* l){
return l->size == MAX_LIST;
}
int get_entry(ArrayList* l,int pos){
// pos 범위가 인덱스를 넘어가나 체크
if(pos < 0 || pos >= MAX_LIST) error("범위 벗어남");
return l->data[pos];
}
void print(ArrayList* l){
for(int i = 0; i< l->size; i++){
printf("%d ",l ->data[i]);
}
printf("\n");
}
//리스트 마지막에 추가하는 함수
void insert_last(ArrayList* l, int item){
if(isFull(l)) error("리스트 초과");
l ->data[(l -> size)++] = item; // 해당 사이즈 인덱스 자리에 item 할당 후 사이즈++
}
//pos 자리에 item 할당
void insert(ArrayList* l,int item, int pos){
if(isFull(l) || pos < 0 || pos >= MAX_LIST) error("에러");
// pos위치를 비워두기 위해 한칸씩 뒤로 옮기기
// pos위치 ~ 마지막 리스트 위치까지
for(int i = l->size-1; i >= pos; i--){
l -> data[i+1] = l -> data[i];
}
l -> data[pos] = item; // 비워둔 위치에 아이템 값 할당
l -> size++; // 사이즈++
}
// 리스트 첫번쩨에 값 넣어주는 함수
void insert_first(ArrayList* l, int item){
insert(l,item,0);
}
//pos위치의 값 삭제하는 함수
int del(ArrayList* l, int pos){
if(isEmpty(l) || pos < 0 || pos >= MAX_LIST) error("에러");
// 삭제할 pos인덱스 위치의 값 미리 빼두기
int ret = l -> data[pos];
// 하나 삭제됐으니 그 뒤에 있던 것들 한칸씩 앞으로 당기기(insert랑 반대)
for(int i = pos; i < l -> size; i++){
l -> data[i] = l -> data[i+1];
}
(l->size)--; // 하나 없어졌으니 size --
return ret;
}
int main(){
ArrayList l;
init(&l);
insert_first(&l,10); print(&l);
insert_first(&l,20); print(&l);
insert_first(&l,30); print(&l);
insert_last(&l,40); print(&l);
del(&l,0); print(&l);
}
결과
연결리스트로 구현된 리스트
연결리스트 : 물리적으로 흩어져있는 자료들을 서로 연결하여 하나로 묶는 방법
- 장점
- 단점
- 구현이 복잡
- 임의의 항목 추출할 때 배열 리스트보다 시간이 오래 걸림
- 연결리스트 구조
노드(node) : 연결리스트는 노드의 집합, 메모리의 어떤 위치에나 존재가능, Data+Link링크 필드(Link) : 다른 노드를 가리키는 포인터가 저장. 다음 노드로 건너갈 수 있다.헤드포인터 : 연결리스트마다 첫 번째 노드를 가리키고 있는 변수(꼭 필요)NULL : 더 이상 연결된 노드가 없다 → 마지막 노드를 의미
연결 리스트 구조
단순 연결 리스트
- 노드들이 하나의 링크 필드를 가지며 이 링크 필드로 모든 노드들이 연결되어 있다.
- 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST 100
//연결리스트 구조체
typedef struct LinkedList{
int data;
struct LinkedList* link; //자기 참조 구조체
}LinkedList;
//가장 앞에 노드를 넣는 함수
LinkedList* insert_first(LinkedList* head,int item){
LinkedList* p = (LinkedList *)malloc(sizeof(LinkedList));
p ->data = item;
p -> link = head; //새로운 노드의 링크가 헤드(첫번째 노드)
head = p; // 새로운 노드를 헤드로
return head;
}
//원하는 위치에 노드를 넣는 함수(이전 노드(pre)를 알아야함)
LinkedList* insert(LinkedList* head, LinkedList* pre, int item){
LinkedList* p = (LinkedList *)malloc(sizeof(LinkedList));
p -> data = item;
p -> link = pre -> link; // 새로운 노드의 링크는 이전 노드가 원래 가리키던 노드(다음노드)
pre -> link = p; // 이전 노드의 링크가 새로운 노드를 가리키도록 수정
return head;
}
//첫번째 노드를 삭제하는 함수
LinkedList* delete_first(LinkedList* head){
LinkedList* removed;
if(head == NULL) return NULL;
removed = head; // 헤드(첫번째 노드를 복사)해서 따로 담아둠
head = removed -> link; //헤드를 두번째노드로 변경
free(removed);
return head;
}
//원하는 위치의 노드 삭제(이전 노드 pre를 알아야함)
LinkedList* del(LinkedList* head, LinkedList* pre){
LinkedList* removed;
if(head == NULL) return NULL;
removed = pre -> link;
pre -> link = removed-> link;
free(removed);
return head;
}
// 노드 출력
void print(LinkedList* head){
//노드가 NULL일때까지 즉, 마지막 노드까지 반복
for(LinkedList* p = head; p != NULL; p = p->link){
printf("%d ",p->data);
}
printf("NULL\n");
}
int main(){
LinkedList *head = NULL;
for(int i = 0; i < 5; i++){
head = insert_first(head,i);
print(head);
}
for(int i = 0; i < 5; i++){
head = delete_first(head);
print(head);
}
}
결과