[Data Structure] 자료구조 (Data Structure)

자료구조 : 데이터들의 관계를 구조화한 것

자료구조의 분류

선형 자료구조 : 리스트, 스택, 큐

비선형 자료구조 : 트리, 그래프

●배열(Array)

-타입이 동일한 데이터들의 집합

-연속된 공간의 메모리를 할당

-인덱스를 통하여 자료의 순서와 위치를 표시

-인덱스를 이용하여 직접적으로 자료에 접근 가능

●리스트(List)

-특정원소의 탐색

-머리(Head)부터 꼬리(Tail)까지 순차탐색

-i번째 원소의 삽입, 삭제

배열리스트(Array List)

탐색 : 머리(Head)부터 순차탐색 가능, 인덱스를 이용한 직접 접근 가능

삽입 : 끝에 삽입하면 해당 메모리 주소에 삽입, 중간에 삽입하면 이후의 모든 데이터를 뒤로 밀고 삽입

삭제 : 끝에 있는 자료는 바로 삭제, 중간에 있는 데이터는 삭제 후에 이후의 데이터를 모두 당긴다.

장점 : 인덱스를 이용한 데이터의 직접적인 접근이 가능하다.

단점 : 삽입, 삭제 시에 다른 데이터들의 위치를 바꿔줘야 한다.

연결리스트(Linked List)

탐색 : 인덱스를 이용하여 직접 접근이 불가능하다. 머리(Head)부터 순차적으로 접근해야 한다.

삽입 : 삽입할 노드를 만든 다음 삽입할 위치의 앞의 노드의 포인터가 삽입할 노드를 가리키게한다. 이어질 노드는 삽입한 노드의 포인터가 가르키게한다.터가 가르키게한다.

삭제 : 삭제할 노드가 가르키는 노드를 이전 노드의 포인터가 가르키게한다. 삭제할 노드의 메모리를 해제한다.

장점 : 데이터의 삽입, 삭제 시에 데이터의 이동이 없다.

단점 : 자료에 직접적으로 접근을 할 수가 없다. 또한 노드를 가르키는 포인터로인해 메모리를 더 사용한다.

●스택

-한 쪽에서만 삽입, 삭제가 일어난다.

-가장 위쪽을 가르키는 포인터를 TOP이라고 한다.

-한 쪽 끝에서만 삽입, 삭제가 일어나기 때문에 가장 나중에 삭제된 테이터가 제일 먼저 삭제된다.

스택 - Overflow와 Underflow

오버플로우(Overflow) : 스택이 가득 차 있는 상태에서 Push(삽입)작업을 하면 발생한다.

언더플로우(Underflow) : 스택이 비어 있는 상태에서 Pop(삭제)작업을 하면 발생한다.

●큐

-한 쪽에서 삽입이 일어나고 다른 끝에서 삭제가 일어나는 자료구조

-삽입이 일어나는 끝을 가르키는 포인터를 Rear라고 한다.

-삭제가 일어나는 끝을 가르키는 포인터를 Front라고 한다.

-가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.

큐 - Overflow와 Underflow

오버플로우(Overflow) : 큐가 가득 차 있는 상태에서 Insert(삽입)작업을 하면 발생한다.

언더플로우(Underflow) : 큐가 비어 있는 상태에서 Remove(삭제)작업을 하면 발생한다.

●트리

-계층적 구조를 나타내는 자료구조

-컴퓨터 디스크의 구조, 인공지능의 결정트리에 이용

트리의 객체(Object)

루트노드 : 트리의 최상단 노드

부모노드 : 해당 노드의 위에 연결된 노드

자식노드 : 해당 노드의 밑에 연결된 노드

형제노드 : 같은 부모노드에 연결되어 있는 노드

트리의 종류

이진 트리 : 각 노드의 자식노드의 수가 2이하인 트리

완전이진 트리 : 이진트리 중에 마지막 레벨을 제외한 모든 레벨의 노드가 최대의 수를 충족하고 마지막레벨은 왼쪽부터 마지막 노드까지 가득 차있는 트리

경사 트리 : 왼쪽 혹은 오른쪽으로 노드들이 한 쪽 방향으로 치우친 트리

트리의 표현방법

배열 : 거의 채워져 있는 이진트리를 구현할 때, 탐색이 용이하고 구현이 간편하며 메모리활용이 효율적이다.

연결리스트 : 노드가 거의 채워지지 않은 트리 혹은 경사트리를 구현할 때 효율적이다.

트리의 변형

이진탐색트리

AVL 트리

2-3 트리

2-3-4 트리

●그래프

-연결되어 있는 객체 간의 관계를 표현하는 자료구조

-최단거리나 최대, 최소비용을 구할 때, 그래프를 이용한 신장트리 사용

그래프의 객체(Object)

정점(Vertax) : 그래프의 각 객체, 노드

간선(Edge) : 그래프의 각 객체를 잇는 간선, 링크라고도 부른다.

그래프의 종류

무방향 그래프 : 간선을 통하여 양방향으로 갈 수 있음.

방향 그래프 : 간선을 통해 한 쪽 방향으로만 갈 수 있음.

그래프의 탐색방법

깊이우선탐색(DFS) : 재귀호출을 이용한 묵시적 스택 사용을 이용한 방법

너비우선탐색(BFS) : 큐를 이용한 탐색방법 가까운 정점부터 방문하는 방법