자료 구조(Data Structure)
자료구조의 정의
자료구조란 컴퓨터 과학에서 데이터를 조직적으로 관리하여 구조적으로 표현하는 방식과 이를 구현하는데 필요한 기능을 가능하게 하는 기술이다.
즉, 자료구조는 데이터 값의 집합과 데이터의 관계, 데이터에 적용시킬 수 있는 함수나 명령이 포함되어 있는 것이다.
자료구조의 중요성
잘 짜인 자료구조는 메모리 용량을 최소한으로사용하게 할 수 있고 실행시간을 단축시킴으로써 보다 효율적인 알고리즘을 실행할 수 있는 데에 도움을 준다. 어떤 프로그램을 설계하는지에 상관없이 자료구조를 선택하는 것은 가장 우선적으로 고려되어야 할 내용이고 매우 중요하다.
자료구조 종류
- 배열(Array)
- 배열은 생성되는 순간 설정되는 셀에 인덱스가 부여되고 해당 셀의 개수는 고정된다.
- 인덱스를 통해 원하는 데이터에 접근할 수 있다.
- 생성될 때 셀의 개수가 고정되므로 데이터를 저장할 수 있는 메모리의 크기가 고정되어 있고 데이터를 추가, 삭제하는 과정이 비효율적이다.
- 데이터가 삭제되고 나면 남는 셀은 빈 공간이 되므로 메모리의 낭비가 심하다.
- 연속 리스트(Contiguous List)
- 배열처럼 연속적인 기억 장소에 데이터가 저장되는 자료구조이다.
- 연속적으로 데이터가 저장되어 있어 검색에 용이하다.
- 데이터의 삽입이나 삭제는 용이하지 않다.
- 삽입과 삭제가 일어나는 경우 자료의 이동이 필요하다.
- 연결 리스트(Linked List)
- 데이터를 임의의 기억공간에 기억시키되, 데이터 항목의 순서에 따라 노드의 포인터를 이용하여 서로 연결시킨 자료구조이다.
- 새로운 데이터를 추가하고 삭제하는 것이 용이하고 효율적이다.
- 배열처럼 메모리에 연속적으로 위치하지 않고 구조의 재구성이 필요 없다.
- 메모리를 더 효율적으로 사용할 수 있기 때문에 대용량의 데이터의 처리에 적합하다.
- 연결이 끊어질 경우 다음 노드를 찾기가 어렵고 속도가 느리다.
- 스택(Stack)
- 순서가 유지되는 선형 데이터 구조이다.
- 리스트의 한쪽에서만 데이터의 삽입과 삭제가 일어난다.
- Last In First Out 메커니즘을 갖는다.
- 기억공간이 부족할 때 데이터를 삽입하게되면 오버플로(Overflow)가 발생한다.
- 데이터를 받는 순서대로 정렬되고 메모리의 크기가 동적이지만 한 번에 하나의 데이터만 처리할 수 있는 불편함이 있다.
- 큐(Queue)
- 스택과 비슷하지만 먼저 입력된 요소를 먼저 처리하는 First In First Out 메커니즘을 갖는다.
- 리스트의 한쪽에서는 삽입이 일어나고 다른 쪽에서는 삭제가 일어난다.
- 데이터의 시작 부분을 프런트라고 하고 끝 부분을 리어라고 한다.
- 동적인 메모리 크기와 빠른 런타임을 자랑하지만 가장 오래된 요소만을 가져오고 한번에 하나의 데이터만 처리하는 단점이 있다.
- 그래프(Graph)
- 정점(Vertex)과 간선(Edge)로 이루어진 데이터 구조이다.
- 사이클이 없는 그래프는 트리라고 한다.
- 방향 그래프와 무방향 그래프가 있다.
- 새로운 요소들의 추가나 삭제가 용이하고 구조를 응용하기에 적합하다.
- 데이터 간에 충돌이 일어날 수 있다는 단점이 있다.
- 트리(Tree)
- 노드(Node)로 구성된 계층적인 자료구조이다.
- 최상위 노드(루트, Root)를 만들고 그 아래에 자식을 추가하는 방식으로 트리구조는 다양하게 구현할 수 있다.
- 노드와 노드를 잇는 선을 간선(Edge)이라 한다.
- 같은 부모노드를 가지며 같은 레벨에 있는 노드를 형제노드라고 한다.
- 자식이 없는 노드를 단말(Terminal)노드라고 한다.
Reference
잘 부탁드려요