[10] C review < 연결리스트의 개념 >

[10] C review < 연결리스트의 개념 >

연결리스트 개념과 기본동작

리스트

컴퓨터 프로그램은 대부분 리스트

- 기본적인 연산 : 삽입(insert),삭제(remove),검색(search)등

- 리스트를 구현하는 대표적인 두 가지 방법 : 배열, 연결 리스트

배열은 랜덤엑세스가 가능한 자료구조다

랜덤엑세스 ?

배열은 각 칸의 타입이 같고 즉, 크기가 동일하다. 예를 들어 배열의 5번재 칸은 배열의 시작 주소 + 4*(1칸의 크기) n번째 칸에 대한 접근의 차이가 없다. > 랜덤엑세스 몇번째 칸이든 상관 없다. >> 배열의 장점

배열의 단점

- 크기가 고정 - reallocation이 필요

= 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야

연결리스트

- 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며,

- 길이의 제한이 없음

- 랜덤 엑세스가 불가능

배열과 연결리스트의 구조적 차이

연결리스트는 데이터와 다음 데이터의 주소를 묶어서 저장한다. 즉 105번지에 Monday와 2번째 데이터인 Tuesday의 주소값102가 묶여서 저장된 것을 알 수 있다.

연결리스트의 삽입과 삭제.

각각의 노드는 필요한 데이터필드와 하나 혹은 그 이상의 링크필드로 구성된다.

링크 필드는 다음 노드의 주소를 저장

첫 번재 노드의 주소는 따로 저장해야 한다.

< 연결리스트의 생성 >

하나의 노드를 만들기 위한 구조체를 만들어야 한다.

#include #include #include typedef struct node { char *data; struct node *next; } Node; Node *head = NULL; // 연결리스트의 첫번째 노드의 주소를 저장할 포인터 int main() { Node *head = (Node *)malloc(sizeof(Node)); head->data = "Tuesday"; head->next = NULL; Node *q = (Node *)malloc(sizeof(Node)); q->data = "Thursday"; q->next = NULL; head->next = q; Node *k = (Node *)malloc(sizeof(Node)); k->data = "Monday"; k->next = head; head = k; Node *p = head; while (p != NULL) { printf("%s

", p->data); p = p->next; } return 0; }

코드의 흐름.

from http://returnclass.tistory.com/103 by ccl(A) rewrite - 2021-11-26 00:00:37