[Algorithm] 자료구조

[Algorithm] 자료구조

자료구조에 대한 전반적인 내용이 한번에 머릿속에 정리가 되지 않아 다시 공부해보면서 정리한다.

 

자료구조

알고리즘 문제를 풀다보면 linked list, stack, queue 등의 자료구조를 사용한다. 말그대로 자료들의 처리가 효율적으로 수행될 수 있도록 구조를 잡아 구분해 놓은 것이다. 알고리즘 문제를 풀때도 적합한 자료구조로 구현한다면 보다 쉽게 구현할 수 있다.

 

종류를 살펴보자.

 

선형구조: 선형리스트, 연결리스트, 스택, 큐, 덱
비선형구조: 트리, 그래프

 

자료구조는 위와 같이 나눌 수 있다. 각각을 보면 아래와 같다.

---

선형구조

선형구조란 자료를 구성하는 원소들을 순차적으로 나열시킨 형태를 말한다. 

선형리스트

• 이전에 정리해둔 내용
• 배열이라고도 한다.
• 인덱스를 가지고 있다. -> 따라서 검색이 빠르다.
• 순차적으로 데이터가 삽입삭제 된다. -> 따라서 순차적으로 데이터를 삽입삭제하고 싶을 때 효과적.
• 단점: 중간에 삽입 삭제가 어렵다.

연결리스트

• 이전에 정리해둔 내용
• 자료의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시킨 구조 -> 포인터 부분이 필요하기 때문에 선형리스트에 비해 공간 효율이 떨어짐
• 중간에 삽입 삭제가 빠르고 쉬움. 
• 단점: 검색 속도, 접근 속도가 느림. 중간 노드의 연결이 끊어지면 그 다음 노드 찾기 힘듬

스택

• 이전에 정리해둔 내용

큐

• 이전에 정리해둔 내용

덱

• 이전에 정리해둔 내용

---

비선형구조

비선형구조란 자료를 구성하는 원소들이 비 순차적으로 나열되어 있는 형태를 말한다.

트리

• 이전에 정리해둔 내용

그래프

• 이전에 정리해둔 내용