Array? List?
Array 와 List는 개발 언어에 대해 아는 사람이라면 무조건 들어 봤을 말이다.
Array 와 List는 비슷하다고 생각할 수 있지만 엄연히 다르다.
배열(Array)
Array는 우리가 흔히 대부분의 언어에서 사용하는 배열로 C언어에서의 배열과 같다.
배열은 고정된 크기를 가지고, 같은 자료형끼리 연속적인 형태를 가진다.
배열의 가장 큰 특징은 데이터마다 인덱스(index)라는 고유한 번호를 부여되어진다.
이러한 점은 특정 인덱스에 바로 접근하여 데이터를 가져올 수 있다는 장점이있다.
리스트(List)
앞서 배열은 고정된 크기를 가지고 있는다고 하였다. 리스트의 경우에는 고정된 크기를 가지지 않고 데이터가 들어오거나 줄어들 때마다 리스트의 크기가 그에 맞춰 변동된다. 리스트는 여러 항목이 나열되어 있는 순서가 있는 데이터들의 모임이다.
배열과 리스트의 차이점은 배열에서 인덱스는 고유한 식별자를 가지지만 리스트는 데이터 몇번째인지 알 수 있는 순서정도로의 의미가 있다.
아직까진 정확히 구분히 안된다면 이후 나올 ArrayList와 LinkedList에 대해 알아보자.
그간 스택, 큐, 덱의 경우 전단 혹은 후단에서만 삽입과 삭제가 일어났다. 하지만 리스트는 특정한 순서에 삽입, 삭제가 가능하다.
ArrayList vs LinkedList
앞서 배열과 리스트에 대해 간단히 이야기 해보았다. 아직 array와 list의 차이에 대해 대답하지 못하겠다면 이 부분을 잘 읽어보자. 보통 Array와 List의 차이를 묻는 것은 일반적으로 Array와 LinkedList를 묻는 것이다. 그만큼 LinkedList는 list의 특징을 잘 담고 있다.
배열리스트(ArrayList)
ArrayList는 말 그대로 배열로 구현한 리스트이다. array와는 달리 배열의 크기가 변경될 수 있다. 배열처럼 인덱스를 사용하여 항목에 바로 접근할 수 있다. 그러나 삽입이나 삭제 연산시에 최악의 경우 O(n)의 시간 복잡도를 가진다.
ArrayList 연산 및 구현
리스트는 현재 리스트에 존재하는 항목들의 개수를 나타내는 size와 현재 배열의 크기인 capacity를 가진다.
동적할당을 사용하여 배열의 크기가 작으면 동적으로 변경한다.
init_list
size를 0으로 초기화한다. capacity는 배열의 크기이다. 처음에는 10정도 할당한다.
void init(ArrayList *L)
{
L->capacity = 10;
L->size = 0;
L->array = (element *)malloc(L->capacity * sizeof(element));
}is_empty
리스트가 비어있는지 확인한다. 리스트가 비어있으면 1을 반환한다.
int is_empty(ArrayListType *L)
{
L->size == 0;
}is_full
리스트가 가득차 있는지 확인한다. 리스트가 가득차있으면 1을 반환한다.
int is_full(ArrayListType *L)
{
return L->size == L->capacity;
}insert
리스트의 원하는 위치(pos)에 항목을 삽입한다. 여기서 항목 삽입시 pos를 기준으로 항목들을 한칸씩 뒤로 이동시킨다. 배열의 크기가 가득찰 경우 현재 크기의 두배로 하여 배열을 크기를 늘린다.
void insert(ArrayListType *L, int pos, element item)
{
if(is_full(L)) // 배열 크기 늘리기
L->capacity *= 2;
L->array = (element *)realloc(L->array, L->capacity * sizeof(element));
if ((pos >= 0) && (pos <= L->size))
{
for (int i = L->size; i > pos; i--) // 한칸씩 밀기
L->array[i] = L->array[i - 1];
L->array[pos] = item;
L->size++;
}
}delete
리스트의 원하는 위치에 항목을 삭제한다. 항목 삭제시 현재 위치의 항목을 저장하고 pos를 기준으로 한칸씩 앞으로 이동후 제거한 후 저장된 항목을 반환하는 것이 필요하다.
element delete(ArrayListType *L, int pos)
{
if (pos < 0 || pos >= L->size)
error("위치 오류");
element item = L->array[pos];
for (int i = pos; i < L->size - 1; i++)
L->array[i] = L->array[i + 1];
L->size--;
return item;
}get_entry
원하는 위치의 항목을 반환한다. 항목에 해당 위치에 없을 경우 오류를 반환한다.
element get_entry(ArrayListType *L, int pos)
{
if (pos < 0 || pos >= L->size)
error("위치 오류");
return L->array[pos];
}get_length
리스트의 현재 길이를 반환한다.
int get_length(ArrayListType *L)
{
return L->size;
}ArrayList 전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct
{
element *array;
int size, capacity;
} ArrayListType;
void init(ArrayListType *L)
{
L->capacity = 1;
L->size = 0;
L->array = (element *)malloc(L->capacity * sizeof(element));
}
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
int is_empty(ArrayListType *L)
{
return L->size == 0;
}
int is_full(ArrayListType *L)
{
return L->size == L->capacity;
}
void insert(ArrayListType *L, int pos, element item)
{
if (is_full(L))
L->capacity *= 2;
L->array = (element *)realloc(L->array, L->capacity * sizeof(element));
if ((pos >= 0) && (pos <= L->size))
{
for (int i = L->size; i > pos; i--)
L->array[i] = L->array[i - 1];
L->array[pos] = item;
L->size++;
}
}
element delete(ArrayListType *L, int pos)
{
if (pos < 0 || pos >= L->size)
error("위치 오류");
element item = L->array[pos];
for (int i = pos; i < L->size - 1; i++)
L->array[i] = L->array[i + 1];
L->size--;
return item;
}
element get_entry(ArrayListType *L, int pos)
{
if (pos < 0 || pos >= L->size)
error("위치 오류");
return L->array[pos];
}
int get_length(ArrayListType *L)
{
return L->size;
}
void print_list(ArrayListType *L)
{
for (int i = 0; i < L->size; i++)
printf("%d->", L->array[i]);
printf("\n");
}
int main(void)
{
ArrayListType list;
init(&list);
insert(&list, 0, 10); print_list(&list);
insert(&list, 0, 20); print_list(&list);
insert(&list, 0, 30); print_list(&list);
insert(&list, 0, 40); print_list(&list);
delete (&list, 0); print_list(&list);
return 0;
}연결리스트(LinkedList)
항목들이 서로가 연결되어 있는 것을 LinkedList라고 한다. C언어에서 연결리스트는 포인터를 사용하여 구현한다.
ArrayList와 LinkedList의 가장 큰 차이는 구현방식에서 나타난다.
ArrayList는 공간이 부족하면 공간을 2배 늘려서 구현하지만 LinkedList는 항목을 담는 공간 하나를 만들고 이를 연결 시켜주면 된다. 특히 연결리스트에서 포인터를 활용해 데이터를 연결하는 것은 다른 자료구조에서도 자주 사용할 수 있으니 잘 기억해두자.
LinkedList 연산 및 구현
연결리스트는 데이터 항목을 담는 node와 이를 연결하는 link가 있다. 아래 이미지에서 상자 하나가 node 하나이다.
가장 앞의 항목을 가리키는 포인터는 head 라고 하고 리스트의 맨 마지막 항목의 link에는 null 값을 가진다.
🌠노드가 다음 노드를 연결하기 때문에 삽입, 삭제시 이전 노드의 값을 받아와 수정해 주어야한다.
insert_first
리스트의 맨 앞에 항목을 삽입한다. 연결 순서가 매우 중요하다. 먼저 node의 link를 현재 head가 가리키는 곳에 연결 시킨후 head가 node를 가리키게 한다. head의 값이 계속 바뀌기 때문에 head를 반환하여 이를 저장한다.
ListNode *insert_first(ListNode *head, element item)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = item;
node->link = head;
head = node;
return head;
}insert
이전 노드인 pre의 다음 위치에 node를 삽입한다. 이전 노드가 없으면 오류를 반환한다. 첫 노드 삽입시에는 insert_first를 사용하자.
1. 추가될 노드가 현재 이전 노드가 가리키는 다음 노드를 가리키게 한다.
2. 이전 노드의 다음 노드가 추가될 노드를 가리키게 한다.
void insert(ListNode *pre, element item)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = item;
if (pre == NULL)
error("리스트 이전 노드 오류");
node->link = pre->link;
pre->link = node;
}delete_first
리스트의 맨 앞 항목을 삭제한다. head를 삭제노드로 설정하고 삭제노드의 다음 노드를 헤드 노드로 변경한다. 이후 삭제노드를 할당 해제한다. 마찬가지로 head값이 변경되기 때문에 head를 최신화시켜 주어야한다.
ListNode *delete_first(ListNode *head)
{
ListNode *removed;
if (head == NULL)
error("리스트 공백 오류");
removed = head;
head = removed->link; // head = head->link;
free(removed);
return head;
}delete
이전 노드의 다음 노드가 삭제노드이다. 삭제할 노드의 다음 노드를 이전 노드의 다음 노드로 설정한다.
삭제 되는 곳에 연결하지 않게 순서를 유의하자.
void delete(ListNode *pre)
{
ListNode *removed;
if (pre == NULL)
error("리스트 이전 노드 오류");
removed = pre->link;
pre->link = removed->link; // pre = (pre->link)->link; 주의! 삭제되는 곳에는 연결되선 안됌.
free(removed);
}LinkedList 전체 코드
#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, element item)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = item;
node->link = head;
head = node;
return head;
}
void insert(ListNode *pre, element item)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = item;
if (pre == NULL)
error("리스트 이전 노드 오류");
node->link = pre->link;
pre->link = node;
}
ListNode *delete_first(ListNode *head)
{
ListNode *removed;
if (head == NULL)
error("리스트 공백 오류");
removed = head;
head = removed->link; // head = head->link;
free(removed);
return head;
}
void delete(ListNode *pre)
{
ListNode *removed;
if (pre == NULL)
error("리스트 이전 노드 오류");
removed = pre->link;
pre->link = removed->link; // pre = (pre->link)->link; 주의! 삭제되는 곳에는 연결되선 안됌.
free(removed);
}
void print_list(ListNode *head)
{
ListNode *node;
for (node = head; node != NULL; node = node->link)
printf("%d->", node->data);
printf("NULL\n");
}
ListNode *search_list(ListNode *head, element item)
{
ListNode *node;
for (node = head; node != NULL; node = node->link)
if (node->data == item)
return node;
return 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;
}마무리
리스트의 개념과 ArrayList, LinkedList의 차이에 대해 알아보았다. 두 가지를 모두 설명하느라 코드가 길어져서 복잡해 보일 수 있다. 천천히 개념을 생각해보고 이해가 잘 안되면 직접 노트에 그려보면서 과정을 생각해보는 것도 좋은 방법이다.
📕 참고 문헌
다음의 책을 참고했습니다.
C언어로 쉽게 풀어쓴 자료구조 [ 개정3판 ]
천인국, 공용해, 하상호 저 | 생능출판사 | 2021년 08월 20일
