자료구조

1. 자료구조

• 자료구조는 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.
• 저장 공간의 효율성과 실행 시간의 단축을 위해 사용한다.

 

<자료구조의 분류>

선형 구조 : 선형 구조는 말 그대로 선같이 일렬로 되어있는 구조이다.

• 배열(Array)
• 선형 리스트(Linear List) [연속 리스트(Contiguous List), 연결 리스트(Linked List)]
• 스택(Stack)
• 큐(Queue)
• 덱, 데크(Deque)

 

비선형 구조 : 비선형 구조는 말 그대로 선형이 아닌 것이다.

• 트리(Tree)
• 그래프(Graph)

 

<여기서 Tip!>

비선형은 트리와 그래프밖에 없다. 나머지는 전부 선형.

위 종류들을 아래에 설명하겠다.

 

 

2. 배열(Array)

• 배열은 크기와 형이 동일한 자료들이 순서대로 나열된 자료의 집합이다.
• 반복적인 데이터 처리 작업에 적합한 구조이다.
• 정적인 자료 구조로, 기억 장소의 추가가 어렵다.
• 데이터 삭제 시 기억장소가 빈 공간으로 남아있어 메모리의 낭비가 발생한다.

<여기서 Tip!>

만약 포인터로 코딩을 한다면 주소에 저장된 데이터들로 작업을 할 수 있다.하지만 배열은 데이터가 할당되어 그 공간은 다른 변수가 할당받을 수 없는 공간이므로 만약 이 배열이 빈공간이라면 해당 공간을 못 쓰기 때문에 메모리의 낭비라는 것이다.그래서 연속적인 데이터 처리작업에서 자주 사용하며 계속 추가될 데이터를 고려하면 데이터 저장으로 잘 사용하지 않는다.

 

 

3. 연속 리스트(Contiguous List)

• 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료구조이다.
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
• 삽입, 삭제 시 자료의 이동이 필요하다.

 

<여기서 Tip!>

리스트는 기억장소를 계속 할당하기 때문에 기억장소 이용 효율은 제일 높다.

기억장소 이용 효율 만 좋다.

 

 

4. 연결 리스트(Linked List)

• 자료들을 임의의 기억공간에서 기억시키되, 자료 항목 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다.
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간의 이용 효율이 좋지 않다.
• 접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어렵다.

 

<연결 리스트>

이미지 출처 : 클릭!

 

 

<실제 적제되는 형태>

 

 

5. 스택(Stack)

• 스택은 리스트의 한 쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다.
• 후입선출(LIFO; Last In First Out) 방식으로 자료를 처리한다.
• 저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로우(Overflow)가 발생한다.
• 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로우(Underflow)가  발생한다.

 

<스택 삽입(push), 삭제(pop) 과정>

이미지 출처 : 클릭!

 

 

6. 큐(Queue)

• 큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료구조이다.
• 선입선출(FIFO; First Input First Output) 방식으로 처리한다.
• 시작을 표시하는 프런트(Front) 포인터와 끝을 표시하는 리어(Rear) 포인터가 있다.

 

<큐 삽입(Enqueue), 삭제(Deqeue)  과정>

이미지 출처: 클릭!

 

 

 

7. 그래프(Graph)

• 그래프는 정점(Vertex)와 간선(Edge)의 두 집합으로 이루어진 자료구조이다.
• 사이클이 없는 그래프(Graph)를 트리(Tree)라 한다.
• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.

 

8. 방향 / 무방향 그래프의 최대 간선 수

• 방향 그래프의 최대 간선 수 : n(n - 1)
• 무방향 그래프에서 최대 간선 수 : n(n - 1) / 2

 

 

 

읽어주셔서 감사합니다!

정처기 화이팅!