어읽로꾸거
자료구조 - 연결 리스트(Linked List) with C 본문
선형 리스트란?
그냥 리스트 즉 배열과 다른 점은 아마도 데이터를 다루는데 있어서 더 효율적이므로 선형 리스트를 사용하겠죠? 아마 그냥 배열(vector)에 비해서 자료를 중간에 끼워넣거나 할때 더 빠르기 때문입니다. 그냥 배열은 다음과 같은 문제를 갖게됩니다. 😥
-
쌓이는 데이터의 크기를 알아야 합니다.
-
데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않습니다.(한칸씩 앞당겨지거나 뒤로 밀리는거는 시간이 O(n) 나옴)
리스트는 자료를 줄지어 나열한 자료구조를 의미합니다.
가장 단순한 구조인 선형 리스트(linear list) 또는 연결 리스트(linked list)는 다음과 같이 생겼습니다.
이때 각각의 데이터를 노드(node) 또는 요소(element)라고 합니다. 각각의 노드(요소)는 데이터와 다음 노드를 가리키는 포인터(c기준)를 가지고 있습니다. 처음에 있는 노드를 머리 노드(head node), 끝에 있는 노드를 꼬리 노드(tail node)라고 합니다. 또한 하나의 앞에있는 노드를 앞 노드(prodecessor node), 뒤에 있는 노드를 뒷 노드(successor node)라고 합니다. 그림의 노드는 단방향 노드입니다.
연결 리스트와 배열 비교
연결 리스트 장점
- 삽입과 제거가 간단합니다. O(1)
연결 리스트 단점
- 데이터에 접근하려면 직접 탐색을 해야해서 시간이 오래걸려요. O(n)
- 메모리를 배열보다 많이 잡아먹어요.
배열 장점
- 데이터에 접근하기에 편리합니다. 바로 접근할 수 있어서 O(1)
배열 단점
- 크기가 고정되어있어서 추가하려면 재할당 해줘야함
- 추가/제거가 복잡해요. 할때마다 데이터가 한칸씩 앞이나 뒤로 밀리니까 O(n)
노드 알아보기
C기준으로 해서 죄송합니다. 전 자바를 할줄 몰라요. 🤔
typedef struct {
Data data;
struct Node *next; //앞에 struct가 붙는 이유는 Node가 완전히 정의가 안되서 그래요 😬
}Node;
data는 노드에 넣고싶은 자료를 의미합니다. *next 는 다음에 연결하고 싶은 노드를 의미합니다. 노드들이 이 각각의 포인터에 의해 줄줄이 연결되는 구조입니다. 맨 처음이나 맨 마지막엔 이 노드들이 각각 어디를 가리킬까요? 맨 처음엔 head포인터 부터 시작해 맨 마지막 포인터는 NULL을 가리킵니다.
그래서 만약에 중간에 새로운 정보를 추가하고 싶다! 그러면 배열은 한 칸씩 뒤로 밀면서 중간에 자리를 확보하겠지만, 연결 리스트는 그냥 앞의 노드의 포인터를 새로 추가할 정보로 다시 연결하고, 해당 노드를 다음 노드로 연결시켜주면 됩니다. 시간이 별로 안걸리겠죠? 실제로요 끼워넣는 과정 자체는 O(1)입니다. 끼워넣을 곳을 찾는 것은 O(n)이겠지만...
노드들로 간단한 연결 리스트를 만들어 보자
일단 연결리스트에는 노드들을 총괄(?)하는 List 구조체가 필요합니다. 머리노드 포인터와 현재 노드를 선택하는 포인터를 가집니다.
typedef struct {
Node *head; //머리노드
Node *crnt; //현재선택노드
}List;
이를 이용해서 간단한 함수들을 만들고 역시 간단한 연결 리스트 예제를 만들어 보았습니다. char을 list에 추가하고 출력해보는 예제입니다.
이 예제에선 crnt는 tail이 새로 생성될 때 마다 움직여서 사실 큰 의미는 없습니다.
🙄
#include<stdio.h>
typedef struct {
char data;
struct Node *next;
}Node;
typedef struct {
Node *head;
Node *crnt;
}List;
//노드 동적생성
Node *AllocNode(void) {
return calloc(1, sizeof(Node));
}
//list 초기화
void Initialize(List *list) {
list->head = list->crnt = AllocNode();
}
//생성된 노드에 정보 입력
void setNode(Node *n, const char *x, const Node *next) {
n->data = *x;
n->next = next;
}
//list 의 crnt 에서 add
void add(List *list, const char *x) {
Node *ptr = AllocNode();
if (list->crnt->next == NULL) { //꼬리 노드인지 확인
setNode(ptr, x, NULL);
list->crnt->next = ptr;
list->crnt = ptr; //새로 생성한 노드로
}
else { //꼬리노드 아님
setNode(ptr, x, list->crnt->next);
list->crnt->next = ptr;
list->crnt = ptr; //새로 생성한 노드로
}
}
//list 의 head 부터 시작해 출력
void print(List *list) {
list->crnt = list->head->next;
//head 는 데이터 비었으니까 넘어감
while (list->crnt->next != NULL) {
printf("%c ", list->crnt->data);
list->crnt = list->crnt->next;
}
printf("%c ", list->crnt->data);
}
int main() {
freopen("input.txt", "r", stdin);
List list;
Initialize(&list);
char str[20];
scanf("%s", str);
for (int i = 0; str[i] != '\0'; i++) {
add(&list, &str[i]);
}
print(&list);
}문제도 풀어보자 💯
사실 이론만 알면 재미가 없죠. 문제도 풀어보겠습니다. (위에서 노드 데이터를 char로 한 이유는 사실 이거 때문 🤣)
백준 5397 키로거 링크 : https://www.acmicpc.net/problem/5397
연결 리스트를 만들어서 구해주면 됩니다. 하지만 여기서 추가로 응용해야할 점은 crnt 를 앞뒤로 움직일 수 있도록 해야합니다. 그러러면 이중 연결 리스트를 만들어주면 됩니다. 지금까지 만든 연결 리스트는 단방향 리스트이고 이중 연결 리스트는 양방향 리스트입니다. Node를 조금 바꿔줍시다.
typedef struct {
char data;
struct Node *next, *prev; //prev 추가
}Node;
이제 남은건 바뀐 struct Node와 문제에 맞게 함수를 구현하기만 하면 됩니다.
전 -> 를 막 쓰고 예외처리 이상하게 하고 하니까 에러가 나서 고치느라 힘들었네요 ㅋㅋ 와 징그러워 나중에 다시 다듬어 볼게요
코드
#include<stdio.h>
typedef struct {
char data;
struct Node *next, *prev;
}Node;
typedef struct {
Node *head;
Node *crnt;
}List;
//함수
//노드 동적생성
Node *AllocNode(void) {
return calloc(1, sizeof(Node));
}
//list 초기화
void Initialize(List *list) {
list->head = list->crnt = AllocNode();
}
//생성된 노드에 정보 입력
void setNode(Node *n, const char *x, const Node *next, const Node *prev) {
n->data = *x;
n->next = next;
n->prev = prev;
}
//list 의 crnt 에서 add
void add(List *list, const char *x) {
Node *ptr = AllocNode();
if (list->crnt->next == NULL) { //꼬리 노드인지 확인
setNode(ptr, x, NULL, list->crnt);
list->crnt->next = ptr;
list->crnt = ptr; //새로 생성한 노드로
}
else { //꼬리노드 아님
Node *back = list->crnt->next;
Node *front = list->crnt;
setNode(ptr, x, list->crnt->next, list->crnt);
front->next = ptr;
back->prev = ptr;
list->crnt = ptr; //새로 생성한 노드로
}
}
//list의 crnt 에서 remove
void remover(List *list) {
if (list->crnt == list->head) { //맨앞의것?
return;
}
else if (list->crnt->next == NULL) { //꼬리임?
Node *ptr = list->crnt->prev; //crnt 앞에꺼 불러옴
Node *t = list->crnt;
list->crnt = ptr;
ptr->next = NULL;
free(t);
}
else { //그냥 중간
Node *t = list->crnt;
Node *ptr = list->crnt->next;
ptr->prev = list->crnt->prev;
ptr = list->crnt->prev;
ptr->next = list->crnt->next;
list->crnt = ptr;
free(t);
}
}
//crnt 왼쪽으로 한칸
void Lm(List *list) {
if (list->crnt == list->head) {//맨 왼쪽?
return;
}
else {
list->crnt = list->crnt->prev;
}
}
//crnt 오른쪽으로 한칸
void Rm(List *list) {
if (list->crnt->next == NULL) { //맨 오른쪽?
return;
}
else {
list->crnt = list->crnt->next;
}
}
//list 의 head 부터 시작해 출력
void print(List *list) {
if (list->crnt == list->head && list->crnt->next == NULL) {
return;
}
list->crnt = list->head->next;
//head 는 데이터 비었으니까 넘어감
while (list->crnt->next != NULL) {
printf("%c", list->crnt->data);
list->crnt = list->crnt->next;
}
printf("%c", list->crnt->data);
}
int main() {
// freopen("input.txt", "r", stdin);
int n; scanf("%d", &n); getchar();
while (n--) {
List list;
Initialize(&list);
char c; c = getchar();
while (c != '\n') {
if (c == '<') {
Lm(&list);
}
else if (c == '>') {
Rm(&list);
}
else if (c == '-') {
remover(&list);
}
else {
add(&list, &c);
}
c = getchar();
if (c == -1)
break;
}
print(&list);
printf("\n");
}
}'정리' 카테고리의 다른 글
| [Java] HashMap, HashTable, ConcurrentHashMap 비교 (0) | 2019.07.01 |
|---|---|
| [python] Queue.Queue vs collections.deque (0) | 2019.04.22 |
| 자료구조 - 힙(Heap) with C (0) | 2019.04.13 |
| 자료구조 - 트리(Tree) with C (0) | 2019.04.07 |
| JAVA 인터페이스 정리 (0) | 2019.03.21 |
