자료구조 - 데이터 구조

자료구조 - 데이터 구조

2020. 8. 29. 19:51ㆍ알고리즘과 자료구조/자료구조

베열과 연결리스트(후 리스트)는 후에 복잡한 데이터구조 설계의 기본이 되기 때문에 기초부터 탄탄하게 잡고 가야한다.

배열

배열(Array)는 같은 자료형을 가진 연속된 메모리 공간으로 이루어진 자료구조이다.

다음은 1차원 배열에 관한 용어 정리이다

-배열명 V : 배열 전체를 가리키는 기호

-배열크기 N : 원소를 저장하는 셀의 수

-배열첨자 i : 셀의 순위

- 시작은 0

- 끝은 N-1

-배열원소 V[i] : V배열에서 i번째 저장된 원소를 가리킴

연결리스트(linked list)는 동적할당을 기반으로 만들어진 노드들로 링크에 의해 연결되어있다. 배열에 비해 메모리 관리가 가능하고 특정 데이터를 삽입 삭제는 쉽지만 탐색이 느린 단점이 있다. 다음은 연결리스트의 종류이다

 typedef struct node{ int elem; struct node* link; }Node;

원소(element) : 데이터 원소 링크(link) : 다음 노드를 가리킴, 없으면 NULL를 가리킴

리스트의 전체에서 첫번째 노드를 헤드 노드라고 한다.

typedef struct node{ int elem; struct node* next; struct node* prev; }Node;

원소(element) : 데이터 원소 다음 링크(next link) : 다음 노드를 가리킴 이전 링크(prev link) : 이전 노들르 가리킴

헤드와 테일을 통해 이중연결리스트의 데이터를 접근한다. 리스트가 비어있다면 헤드와 테일은 NULL을 가리킨다

마지막 노드의 링크가 NULL로 지정되어있는 단일연결리스트와 달리 원형연결리스트는 마지막 노드가 헤드노드를 가리킨다.

단일 연결리스트에서 헤더라는 추가적인 노드를 만드면 리스트를 관리하기 쉽다. 마찬가지로 이중연결리스트에서도 헤더노드와 트레일러노드를 만드면 리스트 관리가 쉬워진다.