저도 현재 배우는 입장이지만 같이 스터디를 하는 마음으로
권오흠 교수님의 강의를 참고하여 공부하겠습니다. 그럼 시작합니다.!
하나가 아닌 여러개가 일렬로 나열되어있을 때 리스트라고 합니다.
리스트와 집합이 있는데 , 집합은 순서와 상관없이
동일한 데이터들이 있으면 순서상관없이
{1,2,3} == {3,2,1} 같다고 정의하지만
리스트에서는 [0,1,2] != [2,1,0]은 같지 않습니다.
순서의 영향을 받냐 안받냐에 따라 구분됩니다
o리스트
:기본적인 연산: 삽입(insert), 삭제(remove), 검색(search)등
대표적인 예로 배열과 연결리스트가 있습니다.
o배열
:랜덤접근이 가능하고 크기가 고정 - reallocation
reallocation으로 크기를 해당 배열이 꽉차면 늘릴 필요가 있습니다.
리스트의 중간에 원소를 삽입,삭제할 경우 데이터를
새로운 배열을 만들어 (strcpy) 데이터를 옮깁니다.
o연결리스트
:다른데이터의 이동없이 리스트 중간에 삽입,삭제가 가능하고,
길이의 제한이 없다, 하지만 연속적인 자료이기 때문에 랜덤 엑세스가 불가능합니다.
Linked List
*node *node
head -> data Monday data Tuseday data Friday Saturday
next 105 next 102 -> next 107 -> next 103 -> next null
그림보며 머리속으로 그려보면 도움이 됩니다.
데이터를 여러개 저장하고 싶으면 데이터필드를 여러개 만들어서 저장합니다
지켜야 할것은 링크 필드는 다음 노드의 주소를 저장해야 합니다.
만약에 연결리스트에 맨 앞에 새로운 노드를 삽입할 때는
순서를 지켜서 노드를 삽입 해야합니다.
1 , 2 , 3이라는 순서가 있으면.
1. 새로운 노드를 생성한다
2. 그 노드는 다음 노드의 주소를 저장한다
3. 헤드는 링크필드의 주소를 새로운 노드를 가리킨다.
#include <stdio.h>
#include <stdlib.h>
strcut node{ /*각 노드 저장될 데이터는 하나의 문자열이라 가정한다*/
char *data;
struct node *next; /*다음 노드 주소를 저장할 필드.
자신과 동일한 구조체에 대한 포인터를 가진다는 의미에서
"자기참조형 구조체"라고 부르기도 한다.*/
}
typedef struct node Node;
Node *head = NULL; //첫번째 노드의 주소를 저장할 포인터이다.
int main()
{
head = (Node *)malloc(sizeof(Node));
head->data = "Tuseday";
head->next = NULL;
Node *q = (Node *)malloc(sizeof(Node));
q->data = "Thursday";q->next = NULL;
head -> next = q;
q = (Node *)malloc(sizeof(Node));
q->data = "Monday";
q->next = head;
head = q;
Node *p = head;
while(p!= NULL) {
printf("%s\n", p->data);
p = p->next;
}
}
만약 순서를 지키지 않는다면 현재의 next 노드주소를 잊어버려 찾을 수 없게된다.
그래서 새로운 노드를 만들고 데이터를 저장하는데 거기에 현재의 head노드를 가리키도록해야 한다. 그다음 Head노드는 새로운 노드를 가리킨다
1)오늘 배운 내용 :
:연결리스트의 기초개념과 프로그램 작성할 때 주의사항,
교수님이 알려주신 부분에는 연결리스트를 다루는 프로그램에서 가장 주의할 점은
내가 작성한 코드가 일반적인 경우만이 아니라 특수한 경우에도 문제 없이 작동하는지
확인하는 것이다. 이 경우에는 기존의 연결 리스트의 길이가 0인 경우, 즉 head가 NULL인 경우에도 문제가 없는지 확인해야한다.
나도 가끔 코드를 작성하다보면 예외처리를 제대로 안해줘서 버그를 일으키는 경우가 많다. 이런점을 인지해서 작성해서 더 나은 코드를 만들도록 해야겠다.
:연결리스트를 헷깔리는게 아니라 포인터 개념이 아직 익숙치 않아서 어떤 노드가 어떤 노드를 가르키는지 불분명할 때가 있다.
3)오늘 파트에 대해서 궁금한 부분?
:head 부분이 만약 NULL이라면 어떻게 처리 될것인가?
만약에 head부분이 맨 뒤를 가리킨다면 맨 앞에있는 노드는 주소를 잃어버려 오류처리가 되지 않을까?
0 comments:
Post a Comment