안녕하세요! 오늘은 저번에 예고했던대로 Linked List에 대해서 포스팅합니다.
Linked List(이하 LL)는 배열의 기능적 업그레이드 버젼이라고 할 수 있습니다!
우선 설명 전 배열의 장단점을 이야기 해봅시다!
1. 배열의 장점
배열은 접근 속도가 빠릅니다! 연속적인 데이터의 나열이기 때문이죠!
또, 배열은 구현이 굉장히 쉽습니다!
2. 배열의 단점
배열은 중간 삽입, 삭제가 매우 어렵습니다! 특히 맨앞의 배열은 삭제시 뒤의 데이터를 일일이 한칸씩 앞당겨줘야합니다!
또한, 크기를 바꾸기 힘듭니다!
왜냐면 배열은 연속된 데이터의 나열이기 때문에 미리 크기를 정하고 메모리에 저장 장소가 잡히기 때문입니다!
그래서 만약에 바꾸고 싶다면 메모리에 새로운 배열을 만들어 데이터를 옮겨줘야합니다!
이러한 단점들을 극복하기 위해서 만들어진 것이 연결리스트입니다!
LL는 배열과 장단점이 서로 정확하게 반대라고 생각하시면 됩니다!
배열은 index로 접근이 O(1)이지만 LL은 O(n)입니다.
LL의 삽입, 삭제는 O(1)로 매우 빠르고 크기는 메모리가 허용하는 범위 내에서 자유롭게 쓸 수 있습니다!
이제 구조를 살펴보겠습니다!
LL은 Node로 이루어져 있습니다. 배열로 치면 배열중 한가지 데이터이죠!
왜 근데 Node라고 부르냐?? Data와 다음 혹은 이전 Node의 주소를 포함하기 때문이죠!
위 그림과 같이 생겨먹었습니다!
이를 코드로 보여드리겠습니다!
typedef struct Node {
struct Node* previousNode;
struct Node* nextNode;
DATA data;
}Node;
코드와 그림을 매치해서 보시면 이해가 편합니다!
다음으로는 LL이 어떻게 생겨먹었고 어떻게 동작하는지 알려주는 그림입니다!
맨 앞의 노드와 맨뒤의 노드는 NULL을 가르킵니다.
안그럼 LL을 통해 앞뒤로 탐색하다가 이상한곳을 발견하고 오류가 나겠죠?
물론 원형 LL은 끝이 없습니다만 오늘은 LL가닥을 잡기위함이니 포함하지 않겠습니다!
맨 앞과 맨 뒤는 코드로 head, tail로 관리합니다.
struct Node* head;
struct Node* tail;
이렇게 관리해야 탐색이 가능합니다!
삽입 삭제에 대해 알아보죠!
삽입은 새로운 노드를 할당하여 기존 Node의 next, or previout pointer와 연결해주고 데이터를 입력해주면 됩니다!
생각보다 간단해요!
코드로 보시죠!
void pushBackNode(DATA value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
tail->nextNode = newNode;
newNode->previousNode = tail;
newNode->data = value;
tail = newNode;
}
void pushFrontNode(DATA value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
head->previousNode = newNode;
newNode->nextNode = head;
newNode->data = value;
head = newNode;
}
다음은 삭제입니다!
반대로 포인터부터 끊어주고 할당된 메모리를 해제해주면 됩니다!
DATA popBackNode() {
DATA returnData = tail->data;
tail = tail->previousNode;
free(tail->nextNode);
tail->nextNode = NULL;
return returnData;
}
DATA popFrontNode() {
DATA returnData = head->data;
head = head->nextNode;
free(head->previousNode);
head->previousNode = NULL;
return returnData;
}
처음엔 보면 어려운데 하다보면 10분이면 연결리스트를 뚝딱하는 자신을 볼 수 있습니다.
다들 꾸준히 연습해보시면 고수가 되실겁니다!
오늘은 여기까지이고 다음에는 연결리스트 추가해서 설명하겠습니다!
'Computing Skills > Data Structure' 카테고리의 다른 글
| [자료구조] 배열 (0) | 2021.11.29 |
|---|---|
| [자료구조] 시작합니다! (0) | 2021.11.27 |